Shuffling Javascript array elegantly

Question

There are some existing threads about shuffling JS arrays, but they all seem not trivial and not elegant, consisting of many lines of code.

I encountered some blog that suggests the following one line "workaround":

yourArray.sort(function() { return 0.5 - Math.random() });

If you're not familiar with how sorting algorithms work, I'll explain here briefly that it's always about comparing two values of the array, and then making a decision. The proposed solution "overrides" the default comparison function with another function that for every comparison of two cells, generates a random value (on each comparison it randomly decides which is greater than which).

The problem with it, is that I can't know which sorting algorithm is used by each web browser. For some sorting algorithms, e.g. BubbleSort, such a function will probably cause the sorting algorithm to run forever, as it will have 1/2^(length) probability to have a run without any swap. It seems to also be problematic for Quicksort. I think it will finish regularly only if the web browser uses MergeSort or HeapSort

Did anyone try it and can tell whether it is safe or recommend on another solution?

Answer 1

The "workaround" is a terrible idea. It's inefficient (using many more calls to Math.random() than necessary) and, as you noted, is dangerous to use for some sorting algorithms. It's also biased (at least for the version of sort() in my nodeJS installation, although I can't explain why). Here's a typical result of sorting the array [1, 2, 3] 60,000 times and counting how many of each permutation shows up:

[1, 2, 3]: 14,821 times
[1, 3, 2]: 7,637 times
[2, 1, 3]: 15,097 times
[2, 3, 1]: 7,590 times
[3, 1, 2]: 7,416 times
[3, 2, 1]: 7,439 times

For an unbiased shuffle, the six permutations should appear equally often on the average (about 10,000 times for 60,000 repetitions). In my experiments, [1, 2, 3] and [2, 1, 3] occur roughly twice as often as the other four permutations. This is consistent over many runs of the test.

You're much better sticking to the standard Fisher-Yates shuffle (described in this Wikipedia article and many other places on the web). In pseudocode, it looks like this (taken from the Wikipedia article):

-- To shuffle an array a of n elements (indices 0..n-1):
for i from n−1 downto 1 do
     j ← random integer such that 0 ≤ j ≤ i
     exchange a[j] and a[i]

Not too complicated and definitely a better approach. Here's my JavaScript version (which could probably be cleaned up a bit):

function shuffleFisherYates(a) {
    var i, j, tmp;
    for (i = a.length - 1; i > 0; --i) {
        j = Math.floor(Math.random() * (i + 1));
        tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
    return a;
}

P.S. For reference, here's the code I used to test your workaround:

function shuffleRandomSort(a) {
    a.sort(function() { return 0.5 - Math.random() });
    return a;
}

function score(scores, result) {
    var index;
    if (result[0] === 1) {
        index = result[1] === 2
            ? 0  // [1, 2, 3]
            : 1; // [1, 3, 2]
    } else if (result[0] === 2) {
        index = result[1] === 1
            ? 2  // [2, 1, 3]
            : 3; // [2, 3, 1]
    } else { // result[0] === 3
        index = result[1] === 1
            ? 4  // [3, 1, 2]
            : 5; // [3, 2, 1]
    }
    scores[index]++;
}

function runTest(shuffler, n) {
    var scores = [0, 0, 0, 0, 0, 0],
        a;
    for (var i = 0; i < n; ++i) {
        a = [1, 2, 3];
        score(scores, shuffler(a));
    }
    console.log(scores);
}

console.log(shuffleRandomSort, runTest(60000));

Answer 2

I grabbed some algorithms and tested them with console.time, you can see the results running them:

var smallArray = Array.from({ length: 10 }, (x, i) => i);
var bigArray = Array.from({ length: 1000 }, (x, i) => i);

function shuffle1(array) {
  var currentIndex = array.length, temporaryValue, randomIndex;

  while (currentIndex) {
    randomIndex = (Math.random() * currentIndex) | 0;
    currentIndex -= 1;

    temporaryValue = array[currentIndex];
    array[currentIndex] = array[randomIndex];
    array[randomIndex] = temporaryValue;
  }
}

function shuffle2(arr) {
  return _.shuffle(arr);
}

function shuffle3(arr) {
  for (let i = arr.length - 1; i >= 0; --i) {
    let j = (Math.random() * i) | 0;
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
}

// inconsistent speeds
function shuffle4(arr) {
  arr.sort(function() { return 0.5 - Math.random() });
}

function test(label, fn) {
  console.time(label);
  for (let i = 0; i < 1000; ++i) {
    fn();
  }
  console.timeEnd(label);
}

// time in comments based on Chrome 55

let sa1 = smallArray.slice(0);
let sa2 = smallArray.slice(0);
let sa3 = smallArray.slice(0);
let sa4 = smallArray.slice(0);
test('smallArray shuffle1', () => shuffle1(sa1)); // 0.785ms
test('smallArray shuffle2', () => shuffle2(sa2)); // 1.830ms
test('smallArray shuffle3', () => shuffle3(sa3)); // 5.540ms
test('smallArray shuffle4', () => shuffle4(sa4)); // 3.995ms

let ba1 = bigArray.slice(0);
let ba2 = bigArray.slice(0);
let ba3 = bigArray.slice(0);
let ba4 = bigArray.slice(0);
test('bigArray shuffle1', () => shuffle1(ba1)); // 14.195ms
test('bigArray shuffle2', () => shuffle2(ba2)); // 24.645ms
test('bigArray shuffle3', () => shuffle3(ba3)); // 119.425ms
test('bigArray shuffle4', () => shuffle4(ba4)); // 249.930ms

<script src="https://cdnjs.cloudflare.com/ajax/libs/lodash.js/4.17.4/lodash.min.js"></script>