Quicksort Function

Take a random list and quicksorts it.

by Hugh Chapman

HTML

<div></div>

CSS

div {
    word-wrap: break-word;
}

JavaScript

var uSet = [35, 2, 51, 52, 99, 30, 91, 47, 29, 54, 11, 15, 56, 100, 79, 60, 90, 16, 24, 48, 66, 94, 68, 45, 34, 27, 77, 46, 38, 39, 83, 74, 23, 19, 85, 12, 9, 53, 67, 20, 25, 87, 98, 44, 82, 81, 1, 80, 61, 93, 65, 43, 92, 89, 36, 84, 28, 75, 97, 3, 86, 7, 31, 57, 69, 10, 22, 62, 41, 42, 32, 33, 37, 5, 71, 58, 49, 73, 17, 88, 70, 13, 40, 21, 95, 78, 4, 59, 96, 14, 50, 72, 18, 64, 26, 76, 6, 63, 55, 8];

function quicksort(m, left, right) {
    if (typeof (left) === 'undefined') left = 0;
    if (typeof (right) === 'undefined') right = m.length - 1;
    // If the list has 2 or more items
    if (left < right) {
        // Use a random index for a Pivot such that left ≤ pivotIndex ≤ right
        var pivotIndex = left + (Math.floor(Math.random() * (right - left)));
        // Get lists of bigger and smaller items and final position of pivot
        var pivotNewIndex = partition(m, left, right, pivotIndex);
        // Recursively sort elements smaller than the pivot (assume pivotNewIndex - 1 does not underflow)
        m = quicksort(m, left, ((pivotNewIndex - 1 >= 0)? pivotNewIndex - 1: 0) );
        // Recursively sort elements at least as big as the pivot (assume pivotNewIndex + 1 does not overflow)
        m = quicksort(m, ((pivotNewIndex + 1 <= m.length-1)? pivotNewIndex + 1: m.length-1), right);
    }
    return m;
}
// left is the index of the leftmost element of the subarray
// right is the index of the rightmost element of the subarray (inclusive)
// number of elements in subarray = right-left+1
function partition(subArray, left, right, pivotIndex) {
    var pivotValue = subArray[pivotIndex],
        storeIndex = left;
    subArray = swap(subArray, pivotIndex, right); // Move pivot to end
    for (var i = left; i < right; i++) { // left ≤ i < right
        if (subArray[i] <= pivotValue) {
            subArray = swap(subArray, i, storeIndex);
            console.log(subArray);
            storeIndex++; // only increment storeIndex if swapped
        }
    }
  ...