Fisher-Yates Shuffle

In JavaScript, there are many ways to randomly shuffle an array. One such way is below.

const shuffle = (array) => {
  for (let i = array.length - 1; i >= 0; i--) {
         const randomIndex = Math.floor(Math.random() * (i + 1));
         array.push(array[randomIndex]);
         array.splice(randomIndex, 1);
     }
     return array;
}    

In the above code, we loop backward through the length of an array, and get a random index with Math.random. We then push the element at that random index to the array and then splice the array at that index. We then return the array at the end of the function.

This is considered a “dirty” shuffle. We are mutating the input array. It is also possible to have a “pure” shuffle where we create a new array instead of mutating the original array.

const shuffle = function(array) {
  const copy = array.slice();
  let result = [];
  while (copy.length > 0) {
    const randomIndex = Math.floor(Math.random() * copy.length)
    result.push(copy[randomIndex]);
    copy.splice(randomIndex, 1);
  }
  return result;
};

In the above code, we are creating a copy of the input array using slice. In our loop, we still create a random index, push elements of that random index to our result array, and then return that result. In the end, we have a shuffled array that doesn’t mutate our input.

Both of the above functions shuffle an array, and they will work for an array of any size. But there is a downfall to the above functions, especially as arrays grow in size. This downfall is time complexity.

Take a close look at the above function. In each, there is a loop, which has a linear — O(n) — time complexity. But there is also a call of the array method splice. This is a very time-consuming operation. Whenever an item is removed from an array, the entire array must be shifted This means there is a linear time operation being called for each element in the array. If an array is thousands of items large, this type of shuffle will take a very long time.

Luckily, there is a way to shuffle an array without splicing, which only requires one loop. This is known as the Fisher-Yates shuffle.

const shuffle = (array) {
  let oldElement;
  for (let i = array.length - 1; i > 0; i--) {
    let rand = Math.floor(Math.random() * (i + 1));
    oldElement = array[i];
    array[i] = array[rand];
    array[rand] = oldElement;
  }
  return array;
} 

In this code, we loop backwards from the last element of an array to the 2nd element (index of 1). We again create a random index using Math.random(). We then swap the current element with this random element. In the end, we return the array.

The variable oldElement is holding a reference to the current element in our loop. Note, the random index is not just a random for the entire array, but a random index from 0 to the current element’s index in the loop. This way, once we swap a random element with the current element in an array, we don’t touch that element anymore.

This code doesn’t use the time-consuming splice for each change we make. Instead, there is only one loop, and inside that loop, a few linear operations. For a large array, this code is a much better implementation of a dirty shuffle because it takes far less time than the above.

You can also use the Fisher-Yates shuffle in a pure way — just make a copy of the array and swap elements in that array instead of the original.

Does that above explanation make sense? If not, check out the following video — the presenter breaks the code down visually.

Happy coding!