How to randomly permute an array in JavaScript?

Question

Possible Duplicate:
How to randomize a javascript array?

I need to implement a randomized binary search tree (R-BST) out of an array so that the sorted array gives O(n lg n) average time and not the O(n^2) which is the worst case time if the arrays are already sorted or reverse sorted . Now the two steps are :

1. Randomly permute the array A.
2. Call BST sort (A) .

How do I go about doing the first step JavaScript? I want it so that each of the n! permutations is equally likely to happen . I believe the way to do this in Java is Collections.shuffle say something like :

Integer[] arr = new Integer[10]; 

for (int i = 0; i < arr.length; i++) { 
    arr[i] = i; 
} 

Collections.shuffle(Arrays.asList(arr)); 

for (int i = 0; i < arr.length; i++) { 
    System.out.print(arr[i] + " "); 
} 

How would I do this in Javascript ? I can use jQuery.

Answer 1

Just use .sort with random comparer:

var comparer = function(a,b) {
    return 2 * Math.random() - 1;
}
array.sort( comparer );

EDIT Since some people are not satisfied with the solution, then here's more classical approach:

Array.prototype.shuffle = function() {
    var result = [];
    while( this.length ) {
        var index = Math.floor( this.length * Math.random() );
        result.push( this[ index ] );
        this.splice(index, 1);
    }
    return result;
};

Answer 2

You could extend the Array prototype with a shuffle function:

Array.prototype.shuffle = function() {
  var tmp, rand;
  for(var i =0; i < this.length; i++){
    rand = Math.floor(Math.random() * this.length);
    tmp = this[i]; 
    this[i] = this[rand]; 
    this[rand] = tmp;
  }
}

and then call shuffle on any array to do an in-place sorting:

var arr = [1,2,3,4];
arr.shuffle();
console.log(arr);