Hack of the day: Random sort
February 2, 2011

@dennisosimon and myself are currently prototyping various things using haxe.

Today we wanted to shuffle the elements of an array around. As haxe doesn’t support a shuffle-method for arrays out of the box, we came up with a very simple workaround:

Haxe provides an easy way to sort items. You can use the sort-method with a function pointer as parameter to sort the elements according to your own comparison function.

What we’ve done is, that we simply just returned random values to achieve some kind of random sort algorithm:

var indices:Array<Int> = new Array<Int>();
for (i in 1...13) {
    indices.push(i);
}
indices.sort(randomSort);

private function randomSort(x:Int, y:Int):Int {
    return Math.random() > 0.5 ? 1 : -1;
}

While this seems like a very easy solution with only a few lines of code, Pimm Hogeling and @43ryn pointed out, that it isn’t a good idea to use it, because in the worst case it could end in an infinite loop. You can read about the details here.

A better and also fast way is to implement the Fisher–Yates shuffle:

public function shuffleArray(arr : Array<Int>) { 
    var tmp : Int, j : Int, i : Int = arr.length;
    while (i > 0) {
        j = Std.int(Math.random() * i);
        tmp = arr[--i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}
  1. Pimm Hogeling (2011-02-02 06:13)

    The algorithm you’re using has been labelled the "Microsoft Shuffle", and actually does not randomise the input.For more information check out this article by Rob Weir: http://bit.ly/9zOEsw

  2. joe (2011-02-02 07:47)

    Thanks for clearing that up. The link you provided was great and very useful!

Add your comment now