About 9 years ago, TechCrunch published this story. Microsoft had this browser ballot screen on browserchoice.eu where Microsoft was supposed to show all the different browser choices to users in random order.
?randomly? sorted
Except, it was far from random. Internet Explorer showed up in the last position about 50% of the time and Chrome was most likely to show up in the top 3. What gives? Well, here?s the code they used for doing the random shuffle:
array.sort(function (a, b) { return 0.5 ? Math.random() })
At first glance, this seems like a reasonable solution. In fact, if you google search ?random shuffle javascript? this code is the top result that pops up. The code uses javascript?s sort function with a custom comparator. This comparator a number between 0.5 and -0.5.
One of the problems with this sorting algorithm, however, is that it does not work. If you want a random shuffle in which every permutation is equally likely. This algorithm fails badly at it. Here?s an interesting statistical analysis on the results of this algorithm.
Other than being wrong, it is also very inefficient. The time complexity of a regular sort function is O(n.logn). But in this case, the sort function is given a very inconsistent ordering. So, this could go into an infinite loop or stop after a few exchanges depending on the algorithm used for sorting.
The Correct Way ? Fisher-Yates Algorithm
Shuffling an array of values is one of the oldest problems in computer science. And the most popular solution to it has been known since 1938. It is the Fisher-Yates shuffle.
Unlike the Microsoft shuffle, this algorithm actually shuffles the array randomly and has O(n) time complexity assuming you have a random number generator with O(1) complexity.
The original fisher yates algorithm, described is 1938 goes something likes this:
1. Write down the numbers from 1 through N.2. Pick a random number k between one and the number of unstruck numbers remaining (inclusive).3. Counting from the low end, strike out the kth number not yet struck out, and write it down at the end of a separate list.4. Repeat from step 2 until all the numbers have been struck out.5. The sequence of numbers written down in step 3 is now a random permutation of the original numbers.Source: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#Fisher_and_Yates’_original_method
The modern version of this algorithm (from the book The Art of Computer Programming by Donald E. Knuth) goes like this:
? To shuffle an array a of n elements (indices 0..n-1):for i from n?1 downto 1 do j ? random integer such that 0 ? j ? i exchange a[j] and a[i]
In javascript, it?d be implemented as:
for(let i = array.length ? 1; i > 0; i–){ const j = Math.floor(Math.random() * i) const temp = array[i] array[i] = array[j] array[j] = temp}
Final Thoughts
When trying to solve a problem, look for tried-and-tested approaches.
We as programmers stand on the shoulders of giants. These algorithms have been polished and refined in the last 7+ decades. There is very little chance that your own implementation is going to be better than that.
