4 ms·
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 referent
by tomstuart 15y ago
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.
- yid 15y agoWhile 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.
- photon_off 15y agoI think there's also an issue of performance -- it's possible, though unlikely, that the sort could take forever to complete.
- bzbarsky 15y agoYou 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.
- tolmasky 15y agoWhen? 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?
- omaranto 15y agoFisher-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]; })
- tomstuart 15y agoFisher-Yates is also in-place, just like Array.prototype.sort.
- omaranto 15y agoArgh, 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).
- __rkaup__ 15y agoWhat's 'Omega'?
- throw_away 15y agoomega() is like the opposite of O(). it means "at least" rather than "at most". — http://en.wikipedia.org/wiki/Big_Oh_notation#Family_of_Bachmann.E2.80.93Landau_notations http://en.wikipedia.org/wiki/Big_Oh_notation#Family_of_Bachm...
- gmurphy 15y agoThe 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-ballot.html http://www.robweir.com/blog/2010/02/microsoft-random-browser...