The Fisher-Yates shuffle algorithm is a very interesting question that you may have heard in your school or college asked in many interviews including FAANG companies.  


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.


Given an array, generate the random permutation of array elements. It is similar to shuffling a deck of cards or randomizing an array and every outcome after shuffling of array elements should likely and equally.


This algorithm performs swapping a random element in the array with the last element in the array over and again.


Example 1:

Input: x = [2, 4, 6, 8, 10]

Output: [4, 10, 6, 2, 8]

              [8, 10, 2, 6, 4]


Let's start with the algorithm,


var fisherYates = function(originalArray) {

  // Clone array from preventing original array from modification (for testing purpose).

  const array = originalArray.slice(0);

  for (let i = (array.length - 1); i > 0; i -= 1) {

    const randomIndex = Math.floor(Math.random() * (i + 1));

    [array[i], array[randomIndex]] = [array[randomIndex], array[i]];

  }

  return array;

}



I hope you understood the algorithm. If you have any doubts, please let us know in the comments.