# 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:

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

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.

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

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

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.

### Step 4: Swap cards

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

The current loop ends after the swap.

### Step 5: Move to the next position

Next, we move to position 4.

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.

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

### Step 7: Move to the next position

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

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.

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

The current loop ends after the swap.

### Step 9: Move to the next position

Let's now move to position 2.

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.

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

The current loop ends after the swap.

### Step 11: Move to the next position

Your next step is to move to 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.

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

### Step 13: Move to the next position

Lastly, move to position 0.

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:

And here is the shuffled cards:

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:

- We loop through the array provided as the function's argument—starting from the last index.
- We saved a copy of the item at the position currently being looped so we can use it later at the swapping stage.
- We used
`Math.floor()`

and`Math.random()`

to generate a random number between`0`

and the number currently being looped (inclusive). - We replaced the item at the position currently being looped with the one at the randomly selected position.
- We substituted the item at the randomly selected position with the one we saved in step 2.
- 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.
- 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 ]

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.