Is it correct to use JavaScript Array.sort() method for shuffling?

Question

I was helping somebody out with his JavaScript code and my eyes were caught by a section that looked like that:

function randOrd(){
  return (Math.round(Math.random())-0.5);
}
coords.sort(randOrd);
alert(coords);

My first though was: hey, this can't possibly work! But then I did some experimenting and found that it indeed at least seems to provide nicely randomized results.

Then I did some web search and almost at the top found an article from which this code was most ceartanly copied. Looked like a pretty respectable site and author...

But my gut feeling tells me, that this must be wrong. Especially as the sorting algorithm is not specified by ECMA standard. I think different sorting algoritms will result in different non-uniform shuffles. Some sorting algorithms may probably even loop infinitely...

But what do you think?

And as another question... how would I now go and measure how random the results of this shuffling tehnique are?

update: I did some measurements and posted the results below as one of the answers.

Answer 1

It's never been my favourite way of shuffling, partly because it is implementation-specific as you say. In particular, I seem to remember that the standard library sorting from either Java or .NET (not sure which) can often detect if you end up with an inconsistent comparison between some elements (e.g. you first claim A < B and B < C, but then C < A).

It also ends up as a more complex (in terms of execution time) shuffle than you really need.

I prefer the shuffle algorithm which effectively partitions the collection into "shuffled" (at the start of the collection, initially empty) and "unshuffled" (the rest of the collection). At each step of the algorithm, pick a random unshuffled element (which could be the first one) and swap it with the first unshuffled element - then treat it as shuffled (i.e. mentally move the partition to include it).

This is O(n) and only requires n-1 calls to the random number generator, which is nice. It also produces a genuine shuffle - any element has a 1/n chance of ending up in each space, regardless of its original position (assuming a reasonable RNG). The sorted version approximates to an even distribution (assuming that the random number generator doesn't pick the same value twice, which is highly unlikely if it's returning random doubles) but I find it easier to reason about the shuffle version :)

This approach is called a Fisher-Yates shuffle.

I would regard it as best practice to code up this shuffle once and reuse it everywhere you need to shuffle items. Then you don't need to worry about sort implementations in terms of reliability or complexity. It's only a few lines of code (which I won't attempt in JavaScript!)

The Wikipedia article on shuffling (and in particular the shuffle algorithms section) talks about sorting a random projection - it's worth reading the section on poor implementations of shuffling in general, so you know what to avoid.

Answer 2

It is a hack, certainly. In practice, an infinitely looping algorithm is not likely. If you're sorting objects, you could loop through the coords array and do something like:

for (var i = 0; i < coords.length; i++)
    coords[i].sortValue = Math.random();

coords.sort(useSortValue)

function useSortValue(a, b)
{
  return a.sortValue - b.sortValue;
}

(and then loop through them again to remove the sortValue)

Still a hack though. If you want to do it nicely, you have to do it the hard way :)

Answer 3

There is nothing wrong with it.

The function you pass to .sort() usually looks something like

function sortingFunc( first, second )
{
  // example:
  return first - second ;
}

Your job in sortingFunc is to return:

• a negative number if first goes before second
• a positive number if first should go after second
• and 0 if they are completely equal

The above sorting function puts things in order.

If you return -'s and +'s randomly as what you have, you get a random ordering.

Like in MySQL:

SELECT * from table ORDER BY rand()

Answer 4

I think it's fine for cases where you're not picky about distribution and you want the source code to be small.

In JavaScript (where the source is transmitted constantly), small makes a difference in bandwidth costs.

Answer 5

I did some measurements of how random the results of this random sort are...

My technique was to take a small array [1,2,3,4] and create all (4! = 24) permutations of it. Then I would apply the shuffling function to the array a large number of times and count how many times each permutation is generated. A good shuffling algoritm would distribute the results quite evenly over all the permutations, while a bad one would not create that uniform result.

Using the code below I tested in Firefox, Opera, Chrome, IE6/7/8.

Surprisingly for me, the random sort and the real shuffle both created equally uniform distributions. So it seems that (as many have suggested) the main browsers are using merge sort. This of course doesn't mean, that there can't be a browser out there, that does differently, but I would say it means, that this random-sort-method is reliable enough to use in practice.

EDIT: This test didn't really measured correctly the randomness or lack thereof. See the other answer I posted.

But on the performance side the shuffle function given by Cristoph was a clear winner. Even for small four-element arrays the real shuffle performed about twice as fast as random-sort!

// The shuffle function posted by Cristoph.
var shuffle = function(array) {
    var tmp, current, top = array.length;

    if(top) while(--top) {
        current = Math.floor(Math.random() * (top + 1));
        tmp = array[current];
        array[current] = array[top];
        array[top] = tmp;
    }

    return array;
};

// the random sort function
var rnd = function() {
  return Math.round(Math.random())-0.5;
};
var randSort = function(A) {
  return A.sort(rnd);
};

var permutations = function(A) {
  if (A.length == 1) {
    return [A];
  }
  else {
    var perms = [];
    for (var i=0; i<A.length; i++) {
      var x = A.slice(i, i+1);
      var xs = A.slice(0, i).concat(A.slice(i+1));
      var subperms = permutations(xs);
      for (var j=0; j<subperms.length; j++) {
        perms.push(x.concat(subperms[j]));
      }
    }
    return perms;
  }
};

var test = function(A, iterations, func) {
  // init permutations
  var stats = {};
  var perms = permutations(A);
  for (var i in perms){
    stats[""+perms[i]] = 0;
  }

  // shuffle many times and gather stats
  var start=new Date();
  for (var i=0; i<iterations; i++) {
    var shuffled = func(A);
    stats[""+shuffled]++;
  }
  var end=new Date();

  // format result
  var arr=[];
  for (var i in stats) {
    arr.push(i+" "+stats[i]);
  }
  return arr.join("\n")+"\n\nTime taken: " + ((end - start)/1000) + " seconds.";
};

alert("random sort: " + test([1,2,3,4], 100000, randSort));
alert("shuffle: " + test([1,2,3,4], 100000, shuffle));

Answer 6

Interestingly, Microsoft used the same technique in their pick-random-browser-page.

They used a slightly different comparison function:

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

Looks almost the same to me, but it turned out to be not so random...

So I made some testruns again with the same methodology used in the linked article, and indeed - turned out that the random-sorting-method produced flawed results. New test code here:

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

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

function shuffle3(array) {
  var tmp, current, top = array.length;

  if(top) while(--top) {
    current = Math.floor(Math.random() * (top + 1));
    tmp = array[current];
    array[current] = array[top];
    array[top] = tmp;
  }

  return array;
}

var counts = [
  [0,0,0,0,0],
  [0,0,0,0,0],
  [0,0,0,0,0],
  [0,0,0,0,0],
  [0,0,0,0,0]
];

var arr;
for (var i=0; i<100000; i++) {
  arr = [0,1,2,3,4];
  shuffle3(arr);
  arr.forEach(function(x, i){ counts[x][i]++;});
}

alert(counts.map(function(a){return a.join(", ");}).join("\n"));