The Code of No-Code

May 02 2016

Unfortunately there is no simple "one liner" that will shuffle an array in javascript. All to often I see people advising to use:

sort(function() { Math.random() - 0.5 }))

However, this does not shuffle the array. First, let's take a look at what does work. It's called the Fisher-Yates shuffle and looks like this in javascript:

function shuffleSort(a) {
  for(var i = 0; i < a.length; i++) {
    var r = Math.floor(Math.random() * (i + 1));
    var t = a[i];
    a[i] = a[r];
    a[r] = t;
  }
}

Why doesn't sorting with a random comparator work? It all depends on the algorithm and what I found really interesting is how each sort algorithm has a different "order bias" which can be made into an image by mapping original position on the x and final position on the y and shading the probability from 0.0 cyan and max percent magenta. Also, in the images below I've expanded the image size so each original-final is 2x2 pixels and they are seperated by white space. Each test was run on an array initialized to [0..99] sorted and run for 1 million iterations. If you want to play around with the code it's all here and an example page with images here.

Fisher-Yates shuffle

function shuffle(a) {
  for(var i = 0; i < a.length; i++) {
    var r = Math.floor(Math.random() * (i + 1));
    var t = a[i];
    a[i] = a[r];
    a[r] = t;
  }
}

As expected this produces a pretty flat image with a probability range [0.009627, 0.010367] after 1 million iterations.

Fisher-Yates

Random Sort

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

Probability range [0.000965, 0.033447] after 1 million iterations.

Random Sort

Quick Sort

Probability range [0.006287, 0.073966] after 1 million iterations. Just from the looks of it quick sort seems to have the worst performance in the center of the array getting the least shuffle.

Quick Sort

Bubble Sort

function bubbleSort(a) {
  var l = a.length;
  var i, j, s, t;
  for (i = 0; i < l; i++) {
    for (j = 0, s = l-i-1; j < s; j++) {
      if (Math.random() < 0.5) {
        t = a[j];
        a[j] = a[j+1];
        a[j+1] = t;
      }
    }
  }
}

Probability range [0 0.500113] after 1 million iterations, which is amazing that after that many trials there were still positions that certain numbers never made it to.

Bubble Sort

At first I thought my sort was off, but then I realized to move 0 from first position to last position requires the comparator (in this case Math.random() - 0.5 < 0.0) to be less than 0.5 99 times in a row. Also, for 9 to remain in last position is 0.5 percent chance that when i=0 and j=9 that Math.random() < 0.5 is false. I double checked this for arrays size 10 in length and the probability range was as expected [0.001923 0.500352] since Math.pow(0.5, 9) == 0.001953125.

Selection Sort

function selectionSort(a) {
  var i, j, m, t;
  var l = a.length;
  for (i = 0; i < l; i++) {
    m = i;
    for (j = i+1; j < l; j++) {
      if (Math.random() < 0.5) m = j;
    }
    if (i != m) {
      t = a[i];
      a[i] = a[m];
      a[m] = t;
    }
  }
}

Selection Sort

Probability range [0 0.500113] after 1 million iterations. Selection sort has some similar problems that bubble sort does. Consider an array a=[0..9] what is the probability that 9 which started in the last position will end up in the first position? If the array was shuffled it should be 0.1, right? But instead for selection sort it is 0.5. Because the only way for 9 to move to the front is when i=0 and j=9 the comparator (in this case Math.random() - 0.5 < 0.0) is less than zero which happens half the time.

Insertion Sort

function insertionSort(a) {
  var l = a.length;
  var i, j, t;
  for (i = 0; i < l; i++) {
    t = a[i];
    for (j = i-1; j > -1 && Math.random() < 0.5; j--) {
      a[j+1] = a[j];
    }
    a[j+1] = t;
  }
}

Insertion Sort

Probability range [0 0.499359] after 1 million iterations.