Fisher-Yates Shuffle Algorithm – How to Shuffle an Array

Fisher-Yates shuffle is an algorithm for generating random arrangements of an array. In other words, the algorithm does an unbiased and sequential shuffle of a list of items.

How Does the Fisher-Yates Shuffle Algorithm Work?

Consider the following pieces of cards:

Seven cards with each one’s index printed on them.

The numbers on the card (0 to 6) represent the positions you may place each card.

Suppose you wish to shuffle the seven pieces of cards. In that case, you can use the Fisher-Yates algorithm to generate an unbiased shuffle. The steps below explain how.

1. Start looping through the positions

   The Fisher-Yates algorithm begins by looping through the seven positions, starting from the last (position 6).

   

   The Fisher-Yates algorithm starts its iteration from the sixth index position.

   At each stage of the loop, you will select a random position among the spots you have not looped.

   Since we have not looped through any position, we can select a random one from the seven spots. Let’s assume we randomly chose position 1.

   

   The yellow number 1 indicates the randomly selected index.

2. Swap cards

   The next step in the fisher-yates algorithm is to swap position 1’s card with the one at the position you are currently looping (that is, position 6).

   

   The image shows a swap of position 1 and 6’s cards.

   Note

   The current loop ends after the swap.

3. Move to the next position

   Now that you’ve finished the first swap, move to the next position (5).

   

   The Fisher-Yates algorithm continues the second loop pass at the fifth index position.

   In this iteration, you will select a random position among all the spots you have not looped (that is, any position from zero to five).

   Let’s assume you randomly selected position 4.

   

   The yellow number 4 indicates the randomly selected index.

4. Swap cards

   Now, swap position 4’s card with the one at the position you are currently looping (that is, position 5).

   

   The image shows a swap of position 4 and 5’s cards.

   Note

   The current loop ends after the swap.

   CodeSweetly ads

5. Move to the next position

   Next, we move to position 4.

   

   The Fisher-Yates algorithm continues the third loop pass at the fourth index position.

   In this iteration, you will select a random position among all the ones you have not looped (that is, any position from zero to four).

   Let’s assume you randomly selected position 4.

   

   The yellow number 4 indicates the randomly selected index.

6. Swap cards

   No swap will occur here because your selected random position is the same as the spot you are looping. Therefore, all the cards will remain in their current positions.

   

   The yellow number 4 indicates the randomly selected index.

7. Move to the next position

   Now, your next step is to move to position 3.

   

   The Fisher-Yates algorithm continues the fourth loop pass at the third index position.

   In this iteration, you will randomly select a position among all the ones you have not looped (that is, any position from zero to three).

   Let’s assume you randomly selected position 0.

   

   The yellow number 0 indicates the randomly selected index.

8. Swap cards

   It’s time to swap position 0’s card with the one at the position you are currently looping (that is, position 3).

   

   The image shows a swap of position 0 and 3’s cards.

   Note

   The current loop ends after the swap.

9. Move to the next position

   Let’s now move to position 2.

   

   The Fisher-Yates algorithm continues the fifth loop pass at the second index position.

   In this iteration, you will randomly select a position among all the ones you have not looped (that is, any position from zero to two).

   Let’s assume you randomly selected position 0.

   

   The yellow number 0 indicates the randomly selected index.

10. Swap cards

    It’s time to swap position 0’s card with the one at the position you are currently looping (position 2).

    

    The image shows a swap of position 0 and 2’s cards.

    Note

    The current loop ends after the swap.

    CodeSweetly ads

11. Move to the next position

    Your next step is to move to position 1.

    

    The Fisher-Yates algorithm continues the sixth loop pass at index position 1.

    In this iteration, you will randomly select a position among all the ones you have not looped (that is, any position between zero and one).

    Let’s assume you randomly selected position 1.

    

    The yellow number 1 indicates the randomly selected index.

12. Swap cards

    No swap will occur here because your selected random position is the same as the spot you are looping. Therefore, all the cards will remain in their current positions.

    

    The yellow number 1 indicates the randomly selected index.

13. Move to the next position

    Lastly, move to position 0.

    

    The Fisher-Yates algorithm continues the seventh loop pass at index position zero.

    You can no longer make any random selection at this stage because only position zero is left. Therefore, the shuffling exercise will end here. In other words, the loop ends whenever the iteration gets to position zero.

Let’s now compare the initial cards with the shuffled ones.

Initial Cards vs. Shuffled Cards

Here is the arrangement we started with:

The image shows an array of seven cards before shuffling.

And here is the shuffled cards:

The image shows an array of seven cards after shuffling with the Fisher-Yates algorithm logic.

Suppose you wish to reshuffle the latest arrangement. In that case, you will repeat the algorithm from step 1 to get a random layout of the cards.

And that’s it! That’s a pictorial depiction of using the Fisher-Yates algorithm to shuffle an array of cards.

Let’s now translate the illustrations above to a JavaScript program.

How to Use the Fisher-Yates Algorithm in JavaScript to Shuffle an Array of Items

Below is the JavaScript version of how the Fisher-Yates shuffle algorithm works.

function shuffleArray(items) {
  // Loop through the array starting from the last index:
  for (let i = items.length - 1; i > 0; i-) {
    // Save a copy of the item at the position you are currently looping:
    const copyOfItemAtPositionBeingLooped = items[i];

    // Select a random index position:
    const randomlySelectedPosition = Math.floor(Math.random() * (i + 1));

    // === The swapping takes place in the two statements below ===
    // Replace the item at the position you are currently looping with the one at the randomlySelectedPosition:
    items[i] = items[randomlySelectedPosition];

    // Replace the item at the randomlySelectedPosition with the copyOfItemAtPositionBeingLooped:
    items[randomlySelectedPosition] = copyOfItemAtPositionBeingLooped;
  }

  // Output the shuffled array:
  return items;
}

// Invoke the function:
shuffleArray([0, 1, 2, 3, 4, 5, 6]);

Here’s what we did in the snippet above:

1. We loop through the array provided as the function’s argument—starting from the last index.
2. We saved a copy of the item at the position currently being looped so we can use it later at the swapping stage.
3. We used Math.floor() and Math.random() to generate a random number between 0 and the number currently being looped (inclusive).
4. We replaced the item at the position currently being looped with the one at the randomly selected position.
5. We substituted the item at the randomly selected position with the one we saved in step 2.
6. After swapping items in steps 4 and 5, the loop will continue to the next position, where it will restart the swapping process from step 2.
7. The loop will end at index zero (0). And the function will return the shuffled array.

Therefore, each time you invoke shuffleArray([0, 1, 2, 3, 4, 5, 6]), you will get an unbiased shuffle of the array like so:

// [ 5, 2, 0, 1, 4, 6, 3 ]
// [ 3, 0, 6, 2, 4, 5, 1 ]
// [ 1, 0, 3, 6, 5, 2, 4 ]
// [ 3, 2, 4, 5, 1, 0, 6 ]

Try Editing It

Note

Although you can also use the JavaScript sort() method to shuffle an array, the Fisher-Yates shuffle algorithm technique is a better option because it is sequential.

See the comparison section on Wikipedia for more on how the Fisher-Yates shuffle compares with other shuffling algorithms.

This article illustrated the Fisher-Yates shuffle algorithm using JavaScript. However, the same principles apply to other programming languages.