Fully Random Array Sort
Join the Discussion
Related Resources
In demonstrating how to get different sort orders in JavaScript by overriding the comparison function used by the sort one alternative I showed was using a random comparison to "sort" the array into random order. With the particular sort algorithm that JavaScript uses I had expected that would be sufficient to sort the array into a completely random order. More recently, I actually tested it by running the same sort a million times using an array of ten entries and comparing the results only to find that there is in fact a bias in the results when you "sort" an array that way with entries being less likely to move to positions further from where they started than they are to stay put. In fact entries were about three times as likely to stay put as to move from one end of the array to the other.
It was only once I had run the million tests several times over getting very similar results each time that I could actually see the bias directly. I then ran further tests to see if I could change the sort processing to reduce or eliminate the bias.
One thing that I found was that by repeating the sort step multiple times the array results became more random. By the time I had sorted the ten element array fifteen times the bias was almost unnoticeable.
Obviously sorting an array fifteen times is a very inefficient way to get the entries into a random order.
The next thing I tried was to change the comparison itself to change what fraction of the entries would swap position when compared. I found that by changing from 0.5 to 0.25 that the bias after one sort was dramatically reduced and had almost disappeared after four sorts. This is an improvement but still isn't really fixing the problem. The bias is still there, just reduced to a much smaller amount by doing a much larger amount of processing.
Now of course if JavaScript were using an appropriate sort algorithm then we could get an unbiased result from our sort even when we want the results to be random.
Of course the obvious solution to this is to not use the sort algorithm built into JavaScript but to instead write a sort algorithm in JavaScript that doesn't display any bias when "sorting" into random order.
One way of sorting that is usually not very efficient is to set up a second array and to sort the elements by moving them from the onhe array to the other usually by grabbing the next element from the unsorted array and inserting it into the appropriate spot in the new array. The alternative approach is to search through the unsorted array to find the next element to be moved and to then move that to the end of the new array. This second way is even less efficient than the first in most circumstances but just happens to be an ideal way of handling a sort into random order.
Since the order we want is to be random we do not need to find the lowest entry in the array to move it to create an ascending result or to find the highest entry and move that to produce a descending result. Instead we simply need to grab entries from the array at random to load into the new sorted array. Instead of who knows how many passes through the array in order to perform a single random sort with the built in sort algorithm we need just two passes through the array - one to move the elements in random order from the original array to a temporary array and a second pass to move them back into our original array ready for subsequent processing.
The resultant code is slightly longer than the earlier biased solution since we are no longer overriding just the comparison operation of the sort but instead are replacing the entire sort algorithm however this new version will genuinely treat all entries in the array equally and produce unbiased results. Now that does not of course mean that the results will be completely even but whereas when I ran the tests I ran with changing the comparison and got it to where there was only a minor difference between the possible results, repeating the test would show the same small bias, with this version any differences from one run were in no way related to the differences in a subsequent run.
So what is this code that you need to "sort" an array properly into an unbiased random order? Well, the following will add it to all your arrays for you as a new method called shuffle(). So instead of using sort() to get a specific order in your array you use shuffle() to change the ordering in the array to be completely random.
var s = [];
while (this.length) s.push(this.splice(Math.random() * this.length, 1));
while (s.length) this.push(s.pop());
return this;
}