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
- Start a loop with index
iset to the last index of the array,arr.length - 1. - Generate a random index
jsuch that0 <= j <= i, usingrandom.nextInt(i + 1). - Swap the elements at
arr[i]andarr[j]using a temporary variable so neither value is lost. - Decrement
iby one so the next random pick is confined to the remaining unshuffled prefix of the array. - Repeat steps 2 through 4 until
ireaches0. - 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.
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.
| Iteration | i | Random j (0..i) | Array Before Swap | Array After Swap |
|---|---|---|---|---|
| 1 | 4 | 1 | [10, 20, 30, 40, 50] | [10, 50, 30, 40, 20] |
| 2 | 3 | 3 | [10, 50, 30, 40, 20] | [10, 50, 30, 40, 20] |
| 3 | 2 | 0 | [10, 50, 30, 40, 20] | [30, 50, 10, 40, 20] |
| 4 | 1 | 1 | [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.
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.
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.
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
ifrom0upward while pickingjin a shrinking range looks similar but biases the resulting permutations. Always loopifromarr.length - 1down to1. - Using the full array length as the random bound – calling
random.nextInt(arr.length)instead ofrandom.nextInt(i + 1)letsjland on an index already fixed by an earlier iteration, which breaks the uniform distribution guarantee. Always bound the pick byi + 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 oneRandominstance before the loop starts. - Skipping the temporary variable during the swap – assigning
arr[i] = arr[j]before saving the originalarr[i]overwrites the value you still need, leaving a duplicate in the array and silently dropping an element. Always stash the value in atempvariable first. - Starting the loop at the wrong bound – initializing
itoarr.lengthinstead ofarr.length - 1throws anArrayIndexOutOfBoundsExceptionon 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
ithere are exactlyi + 1equally likely choices forj, so the product of choices across all steps equalsn!, 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.getandlist.set, or simply call the built-inCollections.shuffle. - What if the shuffle needs to be deterministic and reproducible across runs? – construct the
Randomwith an explicit seed, for examplenew Random(42), so the same sequence ofjvalues, and therefore the same final order, comes out every time. - What if the input array must stay unmodified? – copy it first with
Arrays.copyOfand shuffle the copy, tradingO(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/



