JavaScript shuffling algorithm explanation

Question

I've found shuffling algorithm seems work fine.

const questions = [
  { name: "Ananda or Nalanda" },
  { name: "Sunny or Rainy" },
  { name: "Facebook or Instagram" },
  { name: "IOS or Android" },
  { name: "Mc or KFC" }
];

questions.sort(() => Math.random() - 0.5)

questions.forEach(e=>{
    console.log(e.name)
})

But I couldn't think how this work in the syntax. I know that Math.random() will generate a number between 0 and 1. Also sort is standard function to sort. But how do these two functions shuffle my array? Why does it deduct 0.5 from Math.random()?

Answer 1

The return value from the .sort callback is expected to be a positive number, 0, or a negative number. So, subtracting 0.5 from a variable with a range of [0, 1) results in a range of [-0.5, 0.5) - an equal distribution of randomly sorting a before b, and of sorting b before a (where a and b are the elements being compared). This kind of randomly sorts the array, by randomly determining whether an a comes before or after a b.

If you didn't subtract 0.5, or subtracted something other than 0.5, the results would be significantly biased.

BUT, this is not a good way to randomly sort an array; the results here will be somewhat biased as well:

// an array of 'a' to 'f'
const questions = Array.from(
  { length: 6 },
  (_, i) => String.fromCharCode(i + 97)
);

const positionFrequency = {};
for (let i = 0; i < 1e5; i++) {
  const sorted = questions.slice().sort(() => Math.random() - 0.5);
  sorted.forEach((char, i) => {
    if (!positionFrequency[char]) {
      positionFrequency[char] = {};
    }
    positionFrequency[char][i] = (positionFrequency[char][i] || 0) + 1;
  });
}
console.log(positionFrequency);

Please run the snippet - it is very biased! In Chrome, a occurs in the first position some 28% of the time, despite the fact that it should occur there only 1/6th (16.667%) of the time. In Firefox 56, it's even more biased than that.

This is because the sorting algorithm is not stable - the results depend on which elements are compared against which other elements first (which is implementation-dependent). You can read more details about how exactly this kind of random-sorting is biased here:

http://www.robweir.com/blog/2010/02/microsoft-random-browser-ballot.html

Answer 2

Array.sort sorts an array given a compare function. The sort function compares all the items in the array using the compare function to determine which ones should go before other ones. The compare function must return a negative, zero, or positive value. It uses this value to determine which value should go first.

For example, when comparing values a and b, the sort function will call compare_function(a, b) and if it returns a negative value, sort will place a before b in the final sorted array. If the compare function returns a positive value, sort will place a after b.

So in your example, Math.random() - 0.5 is the compare function. Because Math.random() normally returns a value between 0 and 1, Math.random() - 0.5 will return a random number between -0.5 and 0.5. Therefore, the chance that the compare function (which is Math.random() - 0.5) will return a positive number is the same as the chance that the compare function will return a negative value.

In other words, a random number between -0.5 and +0.5 is used to determine whether an arbitrary item a in your array goes before or after an item b. And because the chances of a positive versus negative number being used are the same, the chances of a before b versus b before a, in the sorted array, are the same.

I hope this answer is helpful!