Cover Image by Adina Voicu from Pixabay
Searching online for shuffling an array in JS you will find multiple solutions. I wanted to compare the three of them for fairness and speed.
To test the fairness I shuffled 100,000 lists of 100 elements. Next, I used a heat map to look for a relation between the starting position and the position after shuffling. Ideally, there is none. This is not a static analysis but an easy insight into bias and to find out where the bias might be.
Sort with random
While searching for a shuffle method, I came across this beautiful one-liner; the worst one in this list: StackOverflow answer. And foolishly used it for the game Where the Flag is This!
yourArray.sort(() => Math.random() - 0.5))
Fairness
Looking at the heat map below we find the fairness to be poor. If something starts at position 0 it is twice as likely to end up in position 0 after shuffling compared to fair. While elements 1 and 51 have almost no chance of becoming one of the last elements.
Speed
The speed is a bit harder to determine because of the use of sort. JS will have different sorting algorithms depending on the engine you use. So Firefox and Chrome can have different results. But sorting algorithms are most likely O(n²) or O(n log(n)).
Not the worst but it’s also not great given we only want to shuffle.
Sort by random value
A slightly better idea is to give each number a random value and then sort based on this random value.
Fairness
The fairness looks as good as you will get. No matter the starting position you can end up anywhere.
Speed
The speed is determined by sort. So most likely O(n²) or O(n log(n)).
Fisher-Yates
Maybe AI will help us, let’s ask ChatGPT, and it gives us the Fisher-Yates shuffle. This algorithm you will also find on Stackoverflow most of the time.
Screenshot of ChatGPT, where ChatGPT is asked to give a JavaScript shuffle algorithm and it returns a JavaScript function with the Fisher-Yader shuffle.
Fairness
Once again perfect fairness to the human eye. To repeat: This is not a static analysis just a visualization of the bias.
Speed
We go through a for-loop with no loops inside it, meaning we only do 1 action per item in the list. This gives us an O(n). The best speed we could have.
Conclusion
Use Fisher-Yader if you need to shuffle a list!
Top comments (0)