Things I learned while trying to code an array shuffle

#javascript #algorithms #arrays

I was making a memory game. I needed to shuffle the array of the answers. And I did something like this:

let arr = ["The Correct Answer", "Wrong Answer", "Wrong Answer"],
    result = [];

// pick random value, check that it's not picked before, push it to the result array
function randomUniqueValue(arr, result) {
  let index = Math.floor(Math.random() * arr.length);

  !result.includes(arr[index]) 
      ? result.push(arr[index])
      : randomUniqueValue(arr, result);
}

for (let i=0; i < arr.length; i++) {
  randomUniqueValue(arr, result);
}
console.log(result);

OK, This is WRONG! If you care about performance, and you should do, then this function is not for you.

Why?

At first, let's discuss what this function does. It declares a random index and check the value inside the given array. if the value has not picked before and pushed into the result array, then push it to the result array. If picked before, repeat.

But, what is wrong?

Performance, my friend. This is the problem!
While the result array is going bigger and bigger it makes the unpicked values less and less. thus the possibility of picking unpicked values lower and lower. Which means picking the already picked values over and over. which requires the function to repeat over and over. Big O notation!

Solution

Geniuses statistical scientists, Ronald Fisher and Frank Yates, came up with this algorithm:
why picking random indexes each time and losing time checking uniqueness?!
We have to go for each value in the array and make it randomized ourselves!

let arr = [1,2,3,4,5,6,7,8,9];

function shuffle() {
  let m = arr.length, i, t;

  while (m) {
    i = Math.floor(Math.random() * m--);

    t = arr[m];
    arr[m] = arr[i];
    arr[i] = t;
  }

  return arr;
}

This way we don't care about the uniqueness of the picked index. we pick a random index and replace it with the last value of the array. then same thing with the value before the last, then the previous one, etc.

How to measure the difference

Copy each function into a code playground and console.log how many times the program picked an index

This is what i got:

Look at the console, it took the while loop just 9 iterations, the array length, to fully randomize the array.

But, the bad function gave me this:

37 iterations just to randomize 9 length array! and imagine the number's growth while the array length gets bigger!

Conclusion

Your function can run without any bugs and do the job, but under the hood performance will suffer. So, it's always a good idea to search for the best algorithm to do somethings like shuffling arrays.

But this does not mean that you shouldn't try to write an algorithm yourself! You should always try and get bugs to solve! This is how you learn and grow! And when you wrote the algorithm by yourself, go search for the best and compare. That will teach you what was wrong and how to avoid them in the future.