The Fisher-Yates Shuffle in Action

Let’s visually walk through the Fisher-Yates Shuffle algorithm for the array [1, 2, 3, 4, 5].

Step 1: We point to the first index in the array:

Step 2: We randomly choose one of the indexes from our pointer and rightward. For now, this can be any index of our array.

We’ll indicate the random index with a die. Say that our randomly chosen number is a 3:

The number the die lands on represents the index that we’re going to swap with. In this case, the index is 3 (and that slot happens to contain the value 4). In the diagram, I’ve placed the die under its corresponding index.

Step 3: We then swap the values of the current index (the arrow) and the random index (the die):

Step 4: We point to the next index of the array:

Step 5: We randomly choose a number between 1 and 4 inclusive since we’re choosing an index from the current pointer and to the right. Say we roll a 4:

Step 6: We swap the values:

Step 7: We point to the next value:

Step 8: We pick a random value from 2 to 4. Let’s say that our computer chooses a 2:

Step 9: In this case, we “swap” the value at index 2 with itself, leaving us with the same array as before.

Step 10: We point to the next value:

Step 11: We choose a random index. At this point, there are only two to choose from, 3 and 4. Let’s say we roll a 4:

Step 12: We swap the current index’s value with the random index’s value:

There’s no point in moving our pointer to the final index. Remember, according to this algorithm, we only swap a value with either itself or any value to its right. Since the final value can’t be swapped with anything other than itself, we end our shuffle here:

Code Implementation: The Fisher-Yates Shuffle

Here’s a Python implementation of the Fisher-Yates Shuffle:

Note that our loop stops before len(array) - 1 since we aren’t going to perform a swap for the final index.