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))

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.

	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.

	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.

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.

	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!