The Fisher-Yates Shuffle

We’ve looked at several different sorting algorithms, but now let’s turn our focus to an unsorting algorithm. While sorting makes order out of chaos, shuffling makes chaos out of order.

To shuffle an array, Python uses a variant of an algorithm known as the Fisher-Yates Shuffle, which was named after Ronald Fisher and Frank Yates, who first described it in 1938. This was before computers, so their original description involved using pencil and paper. Here’s how it works as a computerized algorithm:

1. We point to the first index of the array. We’ll eventually point to the others, too, but we start at the beginning. We’ll call this the “current index.”

2. We generate a random (or pseudorandom) number to choose a random index that is either the current index or higher.

   At the beginning of our algorithm, we can choose from all indexes. But if, say, our current index is 2, and the last index is 4, we’ll choose a random index from 2 to 4, inclusive.

3. We swap the value at our current index with the value at our random index.

4. We move our pointer to the next index of the array.

5. We repeat Steps #1 through #4 until we reach the final value. Since there are no values to the right of the final value, swapping the final value with itself would be pointless, so the algorithm ends.