Coding Challenge Practice - Question 25

The task is to implement a shuffle() to shuffle an array so that every possible order is equally likely.

The boilerplate code

function shuffle(arr) {
}

Starting from the end of the array, pick a random index for each position of the array, from the part of the array that hasn't been chosen yet. Swap the current element with the randomly selected one, and repeat till you get to the beginning of the array.

for (let i = arr.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1)); // 0 ≤ j ≤ i

    const tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
  }

This uses the Fisher-Yates algorithm, which produces every permutation with equal probability.

The final code

function shuffle(arr) {

  for(let i = arr.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1)) 

    const tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
  }
  return arr;
}

That's all folks!