A Quick Look at Quicksort

Quicksort is a competitor to mergesort. While the underlying methodology is still recursion based, the approach to sorting is different:

• pivot: an element is chosen around which the rest of the elements are partitioned.
• partition: elements are partitioned around the pivot such that all elements smaller than the pivot are moved to the left side of pivot while all elements larger than the pivot are moved to the right side of the pivot.
• recursive call: once the original array is partitioned, quicksort is recursively called on subarrays to the left and right of the pivot.

In the example below, leftmost element is chosen as the pivot.

Pseudocode

// partition
p = A[l]
i = l + 1
for j = l + 1 to r
    if A[j] < p
        swap A[j] and A[i]
        i = i + 1           // restores invariant
swap A[l] and A[i - 1]      // place pivot correctly
return i - 1                // return final pivot position

// qsort
if l >= r
    return
j = partition(A, l , j - 1) // j = new pivot position
qsort(A, l, j - 1)          // resurse on first part
qsort(A, j + 1, r)          // recurse on second part

JavaScript Implementation

function swap(array, index1, index2)
{
    var x = array[index2];
    array[index2] = array[index1]
    array[index1] = x;
    return array;
}

function partition(a, l, r)
{
    var p = a[l];
    var i = l + 1;
    for (var j = l + 1; j <= r; j++)
    {
        if (a[j] < p)
        {
            swap(a, j, i);
            i += 1;
        }
    }
    swap(a, l, i - 1);
    return i - 1;
}

// quicksort
function qsort(a, l, r)
{
    if (l >= r)
        return;
    var j = partition(a, l, r);
    qsort(a, l, j - 1);
    qsort(a, j + 1, r);
}

Let's test it

a = [5, 4, 10, 9, 8, 1, 2];
qsort(a, 0, a.length - 1);
console.log(a);

[
  1, 2,  4, 5,
  8, 9, 10
]

What I don't know(yet)

• Effect of chosing a different pivot
• Running time comparison with other algorithms, especially MergeSort