Advertisement
Home Data Structure Arrays Shuffle an Array in Java

Shuffle an Array in Java

0
Advertisement

Title: Shuffle an Array in Java

Shuffling an array means rearranging its elements into a random order so that every possible ordering is equally likely to occur. This comes up constantly in real applications, such as shuffling a deck of cards, randomizing quiz questions, or mixing up a playlist.

In this guide, you’ll learn how to shuffle an array in Java using the Fisher-Yates algorithm, the standard technique that produces an unbiased random permutation in linear time. We’ll walk through the algorithm, trace it step by step, and cover the mistakes that quietly break its fairness guarantee.

Understanding the Problem

Given an array, you need to reorder its elements randomly, in place, so that no ordering is more likely than any other. A naive approach, like repeatedly picking two random positions and swapping them, feels intuitive but does not guarantee a uniform distribution over all permutations.

The Fisher-Yates shuffle (also called the Knuth shuffle) solves this correctly. It visits each index exactly once, from the end of the array to the start, and swaps it with a randomly chosen index from the part of the array that has not been shuffled yet.

Approach: The Fisher-Yates Shuffle

The algorithm processes the array from the last index back to the second index, shrinking the pool of candidates by one on every iteration.

  1. Start a loop with index i set to the last valid index, arr.length - 1.
  2. Generate a random index j such that 0 <= j <= i, using random.nextInt(i + 1).
  3. Swap the elements at arr[i] and arr[j].
  4. Decrement i by one.
  5. Repeat steps 2 through 4 until i reaches 0, since a single remaining element has nowhere left to move.
  6. The array is now shuffled in place, with every possible ordering of the original elements equally likely.

Java Program

The program below implements shuffleArray for an int[] and demonstrates it on a sample array.

Java
import java.util.Arrays;
import java.util.Random;

public class ShuffleArray {

    public static void shuffleArray(int[] arr) {
        Random random = new Random();
        for (int i = arr.length - 1; i > 0; i--) {
            int j = random.nextInt(i + 1);
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    public static void main(String[] args) {
        int[] numbers = {1, 2, 3, 4, 5, 6, 7};
        System.out.println("Before shuffle: " + Arrays.toString(numbers));
        shuffleArray(numbers);
        System.out.println("After shuffle: " + Arrays.toString(numbers));
    }
}

Explanation of the Program

A single Random instance is created once, before the loop starts, so every swap draws from the same pseudo-random sequence. The loop variable i walks backward from the last index down to 1.

On each iteration, random.nextInt(i + 1) picks j from the inclusive range 0 to i, which is exactly the portion of the array that has not been finalized yet. The three-line swap then exchanges arr[i] and arr[j] using a temp variable.

Because i never revisits an index once it moves past it, each position is finalized exactly once and the loop naturally terminates after arr.length - 1 swaps.

Step-by-Step Trace

Consider shuffling [10, 20, 30, 40, 50]. Suppose random.nextInt(i + 1) happens to return the values 1, 3, 0, and 0 for the four iterations where i is 4, 3, 2, and 1; here is how the array mutates one swap at a time.

IterationijArray beforeArray after
141[10, 20, 30, 40, 50][10, 50, 30, 40, 20]
233[10, 50, 30, 40, 20][10, 50, 30, 40, 20]
320[10, 50, 30, 40, 20][30, 50, 10, 40, 20]
410[30, 50, 10, 40, 20][50, 30, 10, 40, 20]

At the end of each iteration, the elements from index i to the end of the array hold a uniformly random permutation of whatever values originally occupied that range, which is exactly the invariant Fisher-Yates relies on.

Examples

Example 1: Shuffling an Array of Exam Scores

Reuse the same shuffleArray method on a fresh array of exam scores to see the swaps applied to different values.

Java
int[] scores = {72, 85, 90, 64, 78};
System.out.println("Before: " + Arrays.toString(scores));
shuffleArray(scores);
System.out.println("After: " + Arrays.toString(scores));
// Output (one possible run): After: [90, 64, 78, 72, 85]

Example 2: Shuffling an Array of Strings

Fisher-Yates works the same way for any array type. Here it is overloaded for String[] so you can shuffle names instead of numbers.

Java
public static void shuffleArray(String[] arr) {
    Random random = new Random();
    for (int i = arr.length - 1; i > 0; i--) {
        int j = random.nextInt(i + 1);
        String temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

String[] names = {"Alice", "Bob", "Carol", "Dave"};
shuffleArray(names);
System.out.println(Arrays.toString(names));
// Output (one possible run): [Carol, Alice, Dave, Bob]

Example 3: Reproducible Shuffle with a Seeded Random

For tests that must produce the same result on every run, seed the Random instance instead of leaving it unseeded.

Java
Random seeded = new Random(42);
int[] deck = {1, 2, 3, 4, 5};
for (int i = deck.length - 1; i > 0; i--) {
    int j = seeded.nextInt(i + 1);
    int temp = deck[i];
    deck[i] = deck[j];
    deck[j] = temp;
}
System.out.println(Arrays.toString(deck));
// Output: the same permutation every time this runs, because the seed is fixed

Common Mistakes to Avoid

Most shuffle bugs do not throw an exception, they just quietly skew the output, which makes them easy to miss in casual testing.

  • Swapping with a full-range random index - picking j with random.nextInt(arr.length) instead of random.nextInt(i + 1) looks correct but lets already-finalized positions be touched again, producing a biased shuffle where some permutations occur more often than others. Always bound the random index to 0 through i inclusive.
  • Creating a new Random() inside the loop - instantiating new Random() on every iteration reseeds from the system clock each time, and calls landing in the same millisecond can produce correlated draws. Create one Random instance before the loop and reuse it for every swap.
  • Confusing an in-place shuffle with a copy - calling shuffleArray(original) mutates the caller's array, which surprises code that expected the original order to survive. Clone the array first with Arrays.copyOf if the caller needs the original order preserved.
  • Off-by-one in the random bound - using random.nextInt(i) instead of random.nextInt(i + 1) never lets index i swap with itself, which silently skews the distribution away from true uniformity even though no exception is thrown.

Additional Considerations

Fisher-Yates runs in O(n) time, performing exactly one swap per element after the first, and uses O(1) extra space since it shuffles in place and needs no auxiliary array.

For a List<T> instead of an array, Collections.shuffle(list) applies the same algorithm for you. If the shuffle needs to be unpredictable in a security-sensitive context, such as shuffling a deck for real-money card games, replace Random with SecureRandom, since a plain Random's output can be predicted once its seed or internal state is inferred.

Edge Cases to Test

Run through these input shapes before trusting a shuffle implementation.

  • Empty array
  • Single-element array
  • Array with duplicate elements
  • Null array reference
  • Very large array (millions of elements)
  • Array of reference types, such as String[] or custom objects
  • Fixed/seeded Random for reproducible tests
  • Already-sorted input

Interview Follow-up Questions

Once you can explain and implement Fisher-Yates, expect an interviewer to push into these variations.

  • How would you make the shuffle reproducible for a unit test? - seed the Random instance with a fixed value so the same sequence of swaps happens on every run.
  • How would you shuffle a List<Integer> instead of a primitive array? - use Collections.shuffle(list), which implements the same Fisher-Yates algorithm internally.
  • How would you prove your shuffle is unbiased? - run many trials, tally how often each permutation or each element-at-position occurs, and compare the distribution to the expected uniform frequency with a chi-square test.
  • What if the array is too large to fit in memory? - stream the elements and apply reservoir sampling, or shuffle fixed-size chunks that fit in memory and interleave the results, since a true in-memory Fisher-Yates no longer applies.
  • What if the shuffle must be cryptographically unpredictable, such as shuffling a deck for an online card game? - replace Random with SecureRandom, since a plain Random's output can be predicted once its seed or internal state is inferred.

Conclusion

Shuffling an array in Java comes down to the Fisher-Yates algorithm: walk the array backward, pick a random swap partner from the unshuffled prefix, and swap. It runs in O(n) time, needs no extra memory beyond the loop variables, and gives every permutation an equal chance of occurring.

Try adapting shuffleArray into a generic <T> void shuffleArray(T[] arr) method, or swap in SecureRandom for a security-sensitive use case. You can learn more about array algorithms in the Arrays category on this site.