Hacker News Reader

Comment by tomstuart | Hacker News Reader

  list = list.sort(function() Math.random() - 0.5);

Please don't shuffle an array like this. Array.prototype.sort requires the comparison function to be referentially transparent (i.e. to always return the same result when given the same two elements to compare), otherwise the sort order is undefined. For example, imagine how far from "shuffled" the resulting array will be if a bubble sort is used with a randomised comparison function.

Use a Fisher-Yates shuffle instead.

View on HN

The European Browser Choice screen was a good example of where this style of sorting can come and bite you - the browser choice screen was designed to display a selection of browsers in random order, but the above sorting code unintentionally biased it towards particular browsers.

Here's a good writeup with a bunch of test runs and graphs: http://www.robweir.com/blog/2010/02/microsoft-random-browser...

Fisher-Yates is a better idea, of course, since it is pretty short and runs in linear time, but if someone insists on a sort-based one-linear this should work:

  list.map(function (t) { return [Math.random(), t]; }).sort().map(function (t) { return t[1]; })

Argh, I missed the edit time window: "one-linear", should be, of course, "one-liner". Fisher-Yates is O(n), but the sort makes this algorithm Omega(n log n).

What's 'Omega'?

omega() is like the opposite of O(). it means "at least" rather than "at most". — http://en.wikipedia.org/wiki/Big_Oh_notation#Family_of_Bachm...

Fisher-Yates is also in-place, just like Array.prototype.sort.

While I agree in principle, there are many cases where you don't care about the statistical quality of a random shuffle, where brevity has its benefit.

You don't understant. The code cited isn't even guaranteed to terminate by the spec; browsers could just go into an infinite loop if the comparison function effectively lies to them so the array never looks sorted... and this would be perfectly reasonable behavior.

So it's not that you get a bad random shuffle; it's that your code might never return from that sort() call.

And to be clear, there have been cases of "hang" bugs being reported to browser vendors in situations exactly like this one because people were writing boneheaded script like this.

I think there's also an issue of performance -- it's possible, though unlikely, that the sort could take forever to complete.

Unlikely is an understatement -- the probability of an infinite sequence of PRNG outputs that prevents any sort algorithm from terminating is negligible.

What about 'taking too much time' though?

Touche...

When? It's not like anyone is asking you to write the shuffling code by hand, so when is time so precious, and space so constrained, that it's beneficial to use this "brief" incorrect solution over taking the 5 minutes to google a correct solution and copy-pasting that?

Reply on news.ycombinator.com