How does this W3Schools code for shuffling an array with .sort() work?

Question

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>

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
– Jaromanda X, Commented May 22, 2017 at 2:34

Mark Amery · Accepted Answer · 2017-10-21 18:25:06Z

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.

See also robweir.com/blog/2010/02/microsoft-random-browser-ballot.html as a backup reference

deceze · Accepted Answer · 2017-05-22 02:37:37Z

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.

answered May 22, 2017 at 2:37

deceze♦

525k89 gold badges807 silver badges954 bronze badges

2 Comments

Mark Amery Over a year ago

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.

Bergi Over a year ago

Not just inefficient, but also simply incorrect.

Collectives™ on Stack Overflow

How does this W3Schools code for shuffling an array with .sort() work?

2 Answers 2

1 Comment

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related