Fisher yates array shuffle algorithm in JavaScript.

Fisher yates array shuffle algorithm in JavaScript.

Subscribe to my newsletter and never miss my upcoming articles

Listen to this article

The Fisher-Yates shuffle is an algorithm for generating a random permutation of a finite sequence—in plain terms, the algorithm shuffles the sequence. The algorithm effectively puts all the elements into a hat; it continually determines the next element by randomly drawing an element from the hat until no elements remain. The algorithm produces an unbiased permutation: every permutation is equally likely. The modern version of the algorithm is efficient: it takes time proportional to the number of items being shuffled and shuffles them in place.

The Fisher-Yates shuffle is named after Ronald Fisher and Frank Yates, who first described it, and is also known as the Knuth shuffle

The modern version of the Fisher-Yates shuffle, designed for computer use, was introduced by Richard Durstenfeld in 1964.

The algorithm described by Durstenfeld differs from that given by Fisher and Yates in a small but significant way. Whereas a naïve computer implementation of Fisher and Yates' method would spend needless time counting the remaining numbers, Durstenfeld's solution is to move the "struck" numbers to the end of the list by swapping them with the last unstruck number at each iteration. This reduces the algorithm's time complexity to O(n) compared to O(n^2) for the naïve implementation.

pseudo Code

-- To shuffle an array of n elements (indices 0..n-1):
for i from n−1 down to 1 do
     j ← random integer such that 0 ≤ j ≤ i
     exchange a[j] and a[i]

Above pseudo-code implementation in JavaScript(es6)


const swap = (array, i, j) => {
  let temp = array[i];
  array[i] = array[j];
  array[j] = temp;
};

const shuffleArray = array => {
  for (let i = array.length; i > 0; i--) {
    const currentIndex = i - 1;
    const randomIndex = Math.floor(Math.random() * i);
    swap(array, currentIndex, randomIndex);
  }
  return array;
};

console.log(shuffleArray([1, 2, 3, 4, 5, 6]));

Follow me on Github and Twitter

 
Share this
Proudly part of