Advertisement
Home Data Structure Arrays Shuffle an Array using Fisher-Yates

Shuffle an Array using Fisher-Yates

1
Advertisement

Title: Shuffle an Array using Fisher-Yates

Shuffling an array means rearranging its elements into a random order so that every possible arrangement is equally likely. This comes up in dealing cards, randomizing a playlist, or drawing a fair random sample in a simulation. In this guide, you will learn the Fisher-Yates shuffle, the standard algorithm for shuffling an array in place in O(n) time with a provably uniform distribution over every permutation.

Understanding the Problem

Not every shuffle that looks random is actually random. A common first instinct is to pick two random indices in the array and swap them, repeated some number of times. This produces an array that looks shuffled, but some final orderings end up far more likely than others, which breaks any statistical guarantee a caller might depend on.

The Fisher-Yates shuffle, also called the Knuth shuffle, solves this by processing the array from the last index down to the first. At each step it picks a random index from the still unshuffled portion of the array and swaps that element into place. This guarantees that every one of the n! possible orderings of an n element array is equally likely to appear.

Algorithm Steps

  1. Start a loop with index i set to the last index of the array, 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] using a temporary variable so neither value is lost.
  4. Decrement i by one so the next random pick is confined to the remaining unshuffled prefix of the array.
  5. Repeat steps 2 through 4 until i reaches 0.
  6. Once the loop ends, every element has been moved into a position chosen uniformly at random, and the array is fully shuffled in place.

Java Program

The following program implements the Fisher-Yates shuffle and demonstrates it on a sample array of integers.

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

public class FisherYatesShuffle {

    public static void shuffle(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, 8};
        System.out.println("Before shuffle: " + Arrays.toString(numbers));
        shuffle(numbers);
        System.out.println("After shuffle: " + Arrays.toString(numbers));
    }
}

Explanation of the Program

The shuffle method takes the array to randomize as its only parameter. It creates a single Random instance outside the loop, so every call to nextInt draws from the same generator instead of reseeding repeatedly.

The for loop runs i from arr.length - 1 down to 1. On each iteration, random.nextInt(i + 1) returns a value between 0 and i inclusive, which is exactly the range of indices that have not yet been locked into their final shuffled position.

The three lines that follow swap arr[i] and arr[j] using the temp variable so neither value is overwritten before it is read. Once index i receives its randomly chosen value, the loop never touches that index again.

The main method builds an eight element array, prints it, shuffles it in place, and prints it again so you can see the effect of the algorithm.

Step-by-Step Trace

Consider the array [10, 20, 30, 40, 50] with a fixed, hypothetical sequence of random picks: j = 1, 3, 0, 1 for i = 4, 3, 2, 1 respectively. The trace below shows how the array mutates on each iteration, including two iterations where j happens to equal i and the swap is a no-op.

IterationiRandom j (0..i)Array Before SwapArray After Swap
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]
411[30, 50, 10, 40, 20][30, 50, 10, 40, 20]

At the end of each iteration, every index from i to the end of the array holds a value that will never be touched again, and the indices from 0 to i - 1 still contain a uniformly random arrangement of the remaining original elements.

Examples

Example 1: Shuffling a Deck of Card Numbers

This example builds an array representing card ranks 1 through 13 and shuffles it using the shuffle method defined earlier.

Java
import java.util.Arrays;

public class ShuffleCardNumbers {

    public static void main(String[] args) {
        int[] cards = new int[13];
        for (int i = 0; i < cards.length; i++) {
            cards[i] = i + 1;
        }

        FisherYatesShuffle.shuffle(cards);
        System.out.println("Shuffled cards: " + Arrays.toString(cards));
        // Sample output: Shuffled cards: [11, 3, 7, 1, 13, 5, 9, 2, 12, 4, 8, 6, 10]
    }
}

Example 2: Shuffling an Array of Strings

Fisher-Yates does not care about the element type, only the index positions. This overload swaps Object references instead of int values, so it works for a String[] of names.

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

public class ShuffleNames {

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

    public static void main(String[] args) {
        String[] names = {"Alice", "Bob", "Charan", "Divya", "Elena"};
        shuffle(names);
        System.out.println("Shuffled names: " + Arrays.toString(names));
        // Sample output: Shuffled names: [Divya, Elena, Alice, Charan, Bob]
    }
}

Example 3: Verifying the Shuffle Preserves All Elements

A correct shuffle only reorders elements, it never adds, drops, or duplicates one. Sorting a copy of the original and a copy of the shuffled array and comparing them confirms this.

Java
import java.util.Arrays;

public class VerifyShufflePreservesElements {

    public static void main(String[] args) {
        int[] original = {4, 8, 15, 16, 23, 42};
        int[] shuffled = Arrays.copyOf(original, original.length);

        FisherYatesShuffle.shuffle(shuffled);

        int[] sortedOriginal = Arrays.copyOf(original, original.length);
        int[] sortedShuffled = Arrays.copyOf(shuffled, shuffled.length);
        Arrays.sort(sortedOriginal);
        Arrays.sort(sortedShuffled);

        boolean isValidPermutation = Arrays.equals(sortedOriginal, sortedShuffled);
        System.out.println("Original: " + Arrays.toString(original));
        System.out.println("Shuffled: " + Arrays.toString(shuffled));
        System.out.println("Is valid permutation: " + isValidPermutation);
        // Sample output: Is valid permutation: true
    }
}

Common Mistakes to Avoid

These are the mistakes that most often slip into a Fisher-Yates implementation, roughly in the order a candidate tends to hit them.

  • Looping from the front instead of the back – iterating i from 0 upward while picking j in a shrinking range looks similar but biases the resulting permutations. Always loop i from arr.length - 1 down to 1.
  • Using the full array length as the random bound – calling random.nextInt(arr.length) instead of random.nextInt(i + 1) lets j land on an index already fixed by an earlier iteration, which breaks the uniform distribution guarantee. Always bound the pick by i + 1.
  • Creating a new Random inside the loop – constructing new Random() on every iteration reseeds from the system clock, and iterations that run in the same millisecond can draw identical or correlated values. Create one Random instance before the loop starts.
  • Skipping the temporary variable during the swap – assigning arr[i] = arr[j] before saving the original arr[i] overwrites the value you still need, leaving a duplicate in the array and silently dropping an element. Always stash the value in a temp variable first.
  • Starting the loop at the wrong bound – initializing i to arr.length instead of arr.length - 1 throws an ArrayIndexOutOfBoundsException on the very first iteration. Always start from the last valid index.

Edge Cases to Test

A candidate who raises these unprompted demonstrates the kind of boundary thinking interviewers look for.

  • Empty array
  • Single-element array
  • Two-element array
  • Array with all duplicate values
  • Array already in sorted order
  • Array containing negative numbers
  • Very large array
  • Null array reference

Additional Considerations

The Fisher-Yates shuffle runs in O(n) time, visiting each index exactly once, and uses O(1) extra space beyond the input array and a single swap variable, since the shuffle happens in place.

An empty or single-element array needs no swaps at all; the loop condition i > 0 simply never executes, so those cases fall out of the algorithm naturally rather than requiring a special branch. A null array reference, on the other hand, throws a NullPointerException at arr.length, which is why it is worth checking for explicitly if the method is part of a public API.

For a java.util.List rather than an array, Collections.shuffle(list) already implements the same algorithm and should be preferred over hand-rolling it. If the shuffle feeds something security-sensitive, such as drawing a lottery winner or dealing cards for real-money play, swap Random for SecureRandom, since Random is a predictable linear generator once its seed or recent outputs are known.

Interview Follow-up Questions

Once you can implement the base shuffle, interviewers typically push into these variations.

  • How would you argue that Fisher-Yates produces a uniform distribution? – show that at step i there are exactly i + 1 equally likely choices for j, so the product of choices across all steps equals n!, matching the total number of permutations exactly once each.
  • What if you need to shuffle a List<T> instead of an array? – apply the identical index walk using list.get and list.set, or simply call the built-in Collections.shuffle.
  • What if the shuffle needs to be deterministic and reproducible across runs? – construct the Random with an explicit seed, for example new Random(42), so the same sequence of j values, and therefore the same final order, comes out every time.
  • What if the input array must stay unmodified? – copy it first with Arrays.copyOf and shuffle the copy, trading O(n) extra space for leaving the caller’s data untouched.
  • What if the data is too large to fit in memory and arrives as a stream from disk? – shuffle within fixed-size in-memory blocks and randomize block order separately, or use a bounded shuffle buffer as streaming data pipelines do, since a true single-pass Fisher-Yates needs random access to the whole array.

Conclusion

The Fisher-Yates shuffle is the correct, textbook way to randomize an array in Java. It runs in linear time, needs no extra memory beyond a swap variable, and is the only common shuffling approach that gives every permutation exactly equal probability.

Try adapting the shuffle method to other array types, or swap in a seeded Random to make a test suite reproducible. You can learn more about Arrays: https://dailyjavaconcept.com/category/arrays/