Skip to main content

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:

Initial layout of seven cards before shuffling with the Fisher-Yates shuffle algorithm

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.

Step 1: Start looping through the positions​

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

Highlight of the card at index 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.

Highlight of index 6's card and index number 1

The yellow number 1 indicates the randomly selected index.

Step 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).

Swapping of index 1 and 6's cards

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

The current loop ends after the swap.

Step 3: Move to the next position​

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

Highlight of the card at index 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.

Highlight of index 5's card and index number 4

The yellow number 4 indicates the randomly selected index.

Step 4: Swap cards​

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

Swapping of index 4 and 5's cards

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

The current loop ends after the swap.

Step 5: Move to the next position​

Next, we move to position 4.

Highlight of the card at index 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.

Highlight of index 4's card and index number 4

The yellow number 4 indicates the randomly selected index.

Step 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.

Highlight of index 4's card and index number 4

The yellow number 4 indicates the randomly selected index.

Step 7: Move to the next position​

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

Highlight of the card at index 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.

Highlight of index 3's card and index number 0

The yellow number 0 indicates the randomly selected index.

Step 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).

Swapping of index 0 and 3's cards

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

The current loop ends after the swap.

Step 9: Move to the next position​

Let's now move to position 2.

Highlight of the card at index 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.

Highlight of index 2's card and index number 0

The yellow number 0 indicates the randomly selected index.

Step 10: Swap cards​

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

Swapping of index 0 and 2's cards

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

The current loop ends after the swap.

CodeSweetly ads

Master NPM Package Creation

Elevate your skills, boost your projects, and stand out in the coding world.
Learn more

Step 11: Move to the next position​

Your next step is to move to position 1.

Highlight of the card at index 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.

Highlight of index 1's card and index number 1

The yellow number 1 indicates the randomly selected index.

Step 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.

Highlight of index 1's card and index number 1

The yellow number 1 indicates the randomly selected index.

Step 13: Move to the next position​

Lastly, move to position 0.

Highlight of the card at index 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:

Initial layout of the seven cards before shuffling with the Fisher-Yates shuffle algorithm

The image shows an array of seven cards before shuffling.

And here is the shuffled cards:

Shuffled layout of the seven 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.

Overview​

Although we've used JavaScript to illustrate the Fisher-Yates shuffle algorithm, the same principles apply to other programming languages.

Your support matters: Buy me a coffee to support CodeSweetly's mission of simplifying coding concepts.

Join CodeSweetly Newsletter