2

This code snippet is from w3schools JavaScript section. I am trying to figure out what 

points.sort( function(a, b) {
  return 0.5 - Math.random()
});

from the code below does. I understand it is trying to perform a random sort on the numbers stored in the array called points, but I don't understand how it is achieved with return 0.5 - Math.random().

I know that random returns a number between 0 and 1 (not including 1). I supposed that 0.5 is then subtracted from that number, but I am not sure what happens from here. Could you kindly give me a step by step explanation?

<!DOCTYPE html>
<html>
<body>

  <p>Click the button (again and again) to sort the array in random order.</p>

   <button onclick="myFunction()">Try it</button>

   <p id="demo"></p>

   <script>
     var points = [40, 100, 1, 5, 25, 10];
     document.getElementById("demo").innerHTML = points;    

     function myFunction() {
      points.sort(function(a, b){return 0.5 - Math.random()});
      document.getElementById("demo").innerHTML = points;
     }
   </script>

 </body>

Mark Amery
  • 143,130
  • 81
  • 406
  • 459
appletree
  • 57
  • 6
  • 1
    sort callback function returns `-n`, `0` or `+n` depending on the comparison between `a` and `b` - using a random value from -0.5 to +0.5 will basically shuffle the array randomly – Jaromanda X May 22 '17 at 02:34
  • [This is a horrible idea](https://stackoverflow.com/q/962802/1048572). – Bergi Oct 21 '17 at 18:29

2 Answers2

3

Passing a callback to Array#sort() that returns a random value is a bad idea; the ECMAScript spec provides no guarantees about what will happen in that case. Per MDN:

compareFunction(a, b) must always return the same value when given a specific pair of elements a and b as its two arguments. If inconsistent results are returned then the sort order is undefined.

And per the spec itself:

If comparefn is not undefined and is not a consistent comparison function for the elements of this array (see below), the sort order is implementation-defined.

The W3Schools code from the question is demonstrably broken; it doesn't shuffle the array fairly, at least in Chrome. Let's try running it a million times and counting how often each value shows up in the final position in the array after "shuffling":

function shuffleAndTakeLastElement() {
    var points = [40, 100, 1, 5, 25, 10];
    return points.sort(function(a, b){return 0.5 - Math.random()})[5];
}
results = {};
for (var point of [40, 100, 1, 5, 25, 10]) results[point] = 0;
for (var i = 0; i < 1000000; i++) results[shuffleAndTakeLastElement()]++;
console.log(results);

I get the following counts in Chrome:

{1: 62622, 5: 125160, 10: 500667, 25: 249340, 40: 31057, 100: 31154}

Notice how the number 10 is around 16 times more likely to end up in the end position of the array than the numbers 40 or 100 are. This ain't a fair shuffle!

A few morals to draw from this story:

  • You should run a large number of tests and look at the results to help confirm whether any randomness algorithm is fair.
  • It's easy to accidentally write a biased algorithm even if you're starting with a fair source of randomness.
  • For shuffling arrays, use Lodash's _.shuffle method or one of the approaches from How to randomize (shuffle) a JavaScript array?.
  • Never trust anything you read on W3Schools, because they suck and are riddled with errors.
Mark Amery
  • 143,130
  • 81
  • 406
  • 459
  • See also http://www.robweir.com/blog/2010/02/microsoft-random-browser-ballot.html as a backup reference – Bergi Oct 21 '17 at 18:35
2

The sort callback is supposed to return a value <0, 0 or >0 to indicate whether the first value is lower than, equal to or higher than the second; sort uses that to sort the values. 0.5 - Math.random() returns a value between -0.5 and 0.5 randomly, satisfying the expected return values and resulting in an essentially randomly shuffled array.

Note that this shouldn't be the preferred method to shuffle; since the return value is random and not internally consistent (e.g. it tells sort that foo < bar, bar < baz and foo > baz), it may make Javascript's sort algorithm very inefficient. A Fisher-Yates shuffle for instance is pretty trivially implemented and likely more efficient.

deceze
  • 510,633
  • 85
  • 743
  • 889
  • 1
    Efficiency is one consideration, sure. But probably more importantly, the W3Schools shuffle violates the ECMAScript spec and is horribly biased when run on real implementations - see the test in my answer. – Mark Amery Oct 21 '17 at 18:26
  • 1
    Not just inefficient, but also [simply incorrect](https://stackoverflow.com/a/2359667/1048572). – Bergi Oct 21 '17 at 18:31