Shuffle JavaScript array with Fisher-Yates algorithm

Posted on Apr 30, 2022

Learn how to shuffle JavaScript array elements using the Fisher-Yates algorithm

Photo from Unsplash

The Fisher-Yates algorithm is named after Ronald Fisher and Frank Yates.

It’s an algorithm used to shuffle a sequence of finite items, like an array for instance.

The algorithm works by swapping a random element from your array with the last element in that array repeatedly.

Here are the steps taken by the algorithm to shuffle an array:

  • Pick a random index number between the first and the last index position in your array
  • Swap the element at the random index with the last index element
  • Repeat step one, but leave the last index out of the random selection
  • Stop the shuffle when only the starting index is left in the random selection

Each time step one is repeated, the last index of the previous repetition is excluded from the selection.

Here’s a visualization of how it works:

Let’s learn how to create a Fisher-Yates algorithm to shuffle JavaScript arrays.

First, create an array of numbers to test the algorithm later.

You also need to store the array length under a variable for easier access later. Let’s reference the array length from the i variable:

let arr = [1, 2, 3, 4, 5, 6, 7];
let i = arr.length;

Next, create a loop using the while statement that will run as long as the i variable is greater than 0:

let arr = [1, 2, 3, 4, 5, 6, 7];
let i = arr.length;
while (--i > 0) {
  // shuffle algorithm here
}

The i variable will be decremented by one each time the while statement is repeated.

The code above reflects the Fisher-Yates algorithm, where the last index is removed from the loop once swapped.

Inside the while statement body, generate a random number for the index from 0 to i as shown below:

let arr = [1, 2, 3, 4, 5, 6, 7];
let i = arr.length;
while (--i > 0) {
  let randIndex = Math.floor(Math.random() * (i + 1));
}

Finally, you need to swap the elements between randIndex and i.

When the while statement stops, print the arr variable to see the result.

Note that the console.log() result will vary each time you run the code:

let arr = [1, 2, 3, 4, 5, 6, 7];
let i = arr.length;
while (--i > 0) {
  let randIndex = Math.floor(Math.random() * (i + 1));
  [arr[randIndex], arr[i]] = [arr[i], arr[randIndex]];
}
console.log(arr); // result will vary

And that’s how you shuffle an array using the Fisher-Yates algorithm!

You can create a custom function named fyShuffle to reuse the algorithm each time you need to shuffle an array:

function fyShuffle(arr) {
  let i = arr.length;
  while (--i > 0) {
    let randIndex = Math.floor(Math.random() * (i + 1));
    [arr[randIndex], arr[i]] = [arr[i], arr[randIndex]];
  }
  return arr;
}

The Fisher-Yates algorithm runs in O(N) time complexity.

The time needed to execute the algorithm rise in proportion to the number of items that need to be shuffled, so it’s not recommended for very large arrays.

Feel free to use the fyShuffle() function above in your JavaScript project when you need it.

Besides the Fisher-Yates algorithm, you can also shuffle JavaScript arrays with the sort() method.

And now you’ve learned how the Fisher-Yates shuffle algorithm works in JavaScript. Nice!

Level up your programming skills

I'm sending out an occasional email with the latest programming tutorials. Drop your email in the box below and I'll send new stuff straight into your inbox!

No spam. Unsubscribe anytime.