In-place shuffle algorithm

in-place-shuffle.js

/**
 * Write a function for doing an in-place shuffle of an array.
 *
 * The shuffle must be "uniform," meaning each item in the 
 * original array must have the same probability of ending up 
 * in each spot in the final array.
 *
 * Must be done in O(n) time and O(1) space
 */

/**
 * In-place shuffle an array. 
 * 
 * Accomplish this by generating a random index in the array 
 * from the available elements left in the array. Once you find
 * this value, swap the two elements and reduce the number of 
 * elements in the array that you can select from.
 *
 * To visualize this, imagine you're selecting item A from a 
 * bag containing the items A, B, and C. The probability of
 * selecting item A is 1/3 (1/n).
 *
 * We guarantee that the probability of an element being in any 
 * given position after the shuffle is 1/n
 */
Array.prototype.shuffle = function () {
    var length = this.length,
        temp,
        base,
        i;

    for (i = 0; i < length; i++) {
        base = getRandom(i, length);
        temp = this[i];
        this[i] = this[base];
        this[base] = temp;
    }
}

function getRandom(floor, ceiling) {
    return Math.floor(Math.random() * (ceiling - floor) + floor);
}

// Usage
var arr = ['a', 'b', 'c'];
arr.shuffle();