The Fisher-Yates shuffle is used to randomly permute given input (list). The permutations generated by this algorithm occur with the same probability.
The modern method of the Fisher-Yates algorithm is a slightly-modified version of the original. Time complexity of this algorithm is O(n) and it is an in-place algorithm. The steps look something like this:
- GIVEN: A collection of items which we want to randomly sort
- FIRST: Randomly select one of the “unshuffled” items.
- THEN: Swap the selected item with the last item in the collection that has not been selected.
- CONTINUE UNTIL: There are no remaining “unshuffled” items.
Visualizing the Modern Method
Assume that we have the same collection of letters as earlier:
{ A, B, C, D, E, F, G, H }
The first step of the algorithm is to randomly select an item (let’s say we pick D) and swap it with the last “unswapped” item in the array (in this case, H). That move looks something like this:
{ A, B, C, D, E, F, G, H } => { A, B, C, H, E, F, G, D }
Now we need to pick the next random unsorted item (let’s say it’s E) and swap it with the last unsorted item (G):
{ A, B, C, H, E, F, G, D } => { A, B, C, G, E, F, E, D }
We can continue on like this until the array is fully sorted:
{ A, B, C, H, G, F, E, D } => { A, F, C, H, E, B, E, D }
{ A, F, C, H, G, B, E, D } => { A, F, C, G, H, B, E, D }
{ A, F, C, G, H, B, E, D } => { G, F, C, A, H, B, E, D }
{ G, F, C, A, H, B, E, D } => { G, C, F, A, H, B, E, D }
{ G, C, F, A, H, B, E, D } => { C, G, F, A, H, B, E, D }