DEV Community

Cover image for Avoid shuffling with .sort(() => Math.random() — 0.5))
Tom Nijhof
Tom Nijhof

Posted on

1

Avoid shuffling with .sort(() => Math.random() — 0.5))

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))
Enter fullscreen mode Exit fullscreen mode

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.

Heatmap showing the fairness of the first method

let data = []
for (let i = 0; i < 100000; i++) {
data.push([...Array(100).keys()].sort(() => Math.random() - 0.5))
}
const jsonData = JSON.stringify(data);
view raw shuffle1.js hosted with ❤ by GitHub

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.

Heatmap showing the fairness of the second method

function sort(list){
let new_list = []
for (let i =0; i < list.length; i++){
new_list.push( {
random_number: Math.random(),
element: list[i]
})
}
sorted_new_list = new_list.sort((a, b) => a.random_number - b.random_number)
sorted_list = sorted_new_list.map(e => e.element);
return sorted_list
}
let data = []
for (let i = 0; i < 100000; i++) {
data.push(sort([...Array(100).keys()]))
}
view raw shuffle2.js hosted with ❤ by GitHub

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.

A conversation with chatGPT to ask for a shuffle function in javascript

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.

Heatmap showing the fairness of the Fisher-Yader shuffle method

function shuffleArray(array) {
for (let i = array.length - 1; i > 0; i--) {
const j = Math.floor(Math.random() * (i + 1)); // Generate a random index between 0 and i
// Swap elements at i and j
[array[i], array[j]] = [array[j], array[i]];
}
}
let data = []
let new_list = []
for (let i = 0; i < 100000; i++) {
new_list = [...Array(100).keys()]
shuffleArray(new_list)
data.push(new_list)
}
view raw shuffle3.js hosted with ❤ by GitHub

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!

SurveyJS custom survey software

Simplify data collection in your JS app with a fully integrated form management platform. Includes support for custom question types, skip logic, integrated CCS editor, PDF export, real-time analytics & more. Integrates with any backend system, giving you full control over your data and no user limits.

Learn more

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

👋 Kindness is contagious

Immerse yourself in a wealth of knowledge with this piece, supported by the inclusive DEV Community—every developer, no matter where they are in their journey, is invited to contribute to our collective wisdom.

A simple “thank you” goes a long way—express your gratitude below in the comments!

Gathering insights enriches our journey on DEV and fortifies our community ties. Did you find this article valuable? Taking a moment to thank the author can have a significant impact.

Okay