• About
• Statistics
• Number Theory
• Java
• Data Structures
• Cornerstones
• Calculus

Quicksort

Quicksort is an incredibly efficient sorting technique that addresses one of the major shortfalls of a merge sort -- it sorts an array in-place. That is to say, it does not require a large amount of memory be allocated for an auxiliary array, accomplishing the sorting through well-chosen exchanges of array elements instead.

Like mergesort, quicksort is a recursive sorting technique.

Starting with the entire array -- and with each recursive pass -- quicksort rearranges the elements in a section of the array so that the section is partitioned into three pieces:

• an element called the pivot (which we really want to end up in the center of the section)
• all of the array elements less than the pivot (all grouped just left of the pivot), and
• all of the array elements greater than the pivot (all grouped just right of the pivot).

Then, choosing new pivots, the same process is applied to the smaller left and right "halves", until the resulting sections are only one element long (a base case for the recursion).

Of course, speaking of "halves" here is just hopeful. The only way for us to ensure the number of elements to the left of the pivot equals the number of elements to the right of the pivot would be to choose the the median value of that section to be the pivot. However, to identify the median requires sorting all of the elements first -- which is the very thing we are trying to do in the first place!

While improvements can be made to how one picks a pivot so that it is closer to the true median value -- in its simplest form, quicksort just chooses the left-most element of the section in question as the pivot for that section. Amazingly, even using this gross approximation of the median, quicksort works remarkably quickly.

One Technique for Partitioning the Array

The partitioning of the rest of the elements involved into a group to the left of the pivot that are all less than the pivot, and a group to the right of the pivot that are all greater than the pivot, is accomplished through a careful sequence of exchanges. One technique that can be used to partition the elements of an array relative to a pivot element is shown below. We will look at another method later.

As an example, suppose we wish to partition the following section of an array:

We first choose the leftmost element (i.e., $Q$) to server as the pivot element, which we color red below.

Then, starting with the element to its immediate right, we traverse the the rest of the section until we find something greater than the pivot $S$. (We stop at the end of the section, if we don't find any such elements.)

To make it clear which elements have been compared with the pivot, we'll color those found to be less than or equal to the pivot purple and those greater than the pivot green. In this case, we find the first element greater than the pivot, $U$, immediately. This element, being bigger than the pivot, should really be on the right side.

However, recall that we wanted all of the movement of array elements during the sort to be accomplished through exchanges, (so that the sorting can be done "in place"). Thus, to move $T$ to the right, we'll need to identify some element on the right side with which we might exchange it.

Ideally, such an element would be one smaller than the pivot, so that when exchanged with $T$ it ends up on the correct side as well.

As such, we now start with the right-most element of the section (i.e., the one with the highest index) and work our way left until we find something less than the pivot. (Again, if there are no such elements, we stop at the left end of the section.)

In this case, we again don't have to go very far -- finding the last element itself (i.e., $E$) smaller than the pivot. We thus exchange these two elements and then continue our search for more elements that need to be moved to opposing sides.

On the left, the next element as we move to the right that is greater than the pivot (and thus, green) is $S$, and on the right, the next element as we move to the left that is less than the pivot (and thus, purple) is $M$. We thus exchange these elements and again continue our search for more elements that need to be moved to opposing sides.

On the left, the next element (as we move to the right) that is greater than the pivot is $R$. On the right, the next element (as we move to the left) that is less than the pivot is $O$. We again exchange these two elements.

We continue in this way -- next finding $T$ and $E$, and exchanging them

However, upon identifying the next pair ($W$ and $A$), we see that the arrows marking them have crossed one another. At this moment -- with the exception of the pivot itself -- all of the elements in the section from $A$ to the left are less than the pivot, and all of the elements in the section to the right of $A$ are greater than the pivot.

One final special exchange of the pivot and the element at the left arrow puts the pivot in the correct position and completes the partition.

Having done this last exchange, we see that $Q$ is now in its final position with regard to the entire sort, and we have set things up so that if we recursively sort the (purple) elements remaining in the section that are to the left of $Q$ and then recursively sort the (green) elements remaining in the section that are to the right of $Q$, the entire section will be completely sorted.

It should be noted that if the array has duplicate elements, then any elements equal to the pivot will stay on their respective sides of the final pivot placement, but are moved adjacent to this pivot as the later recursive sorting takes place.

Partitioning Implementation

Before implementing the above method of partioning, we first give names to some important positions in the array:

• First, we'll assume the the index of the left-most element is lo and the index of the right-most element is hi. This is due to the fact that the partition method we hope to design will need to be called recursively on various subsets of the entire array -- so there is no guarantee that the left-most element is at index $0$.

• Second, we'll keep track of the positions of the elements in the array checked against the pivot that start at lo+1 and move to the right with index i. The positions of the elements in the array checked against the pivot that start at hi and move to the left are tracked by index j.

Assuming the existence of an instance variable array a[] of items to be sorted and our standard helper instance methods of less() and exch(), we can construct the partition method in the following way:

private int partition(int lo, int hi) {

    int i = lo;      // note, this will get incremented to (lo+1) before it is used
    int j = hi+1;    // similarly, this will get decremented to hi before it is used

    while (true) {
        
        while (less(a[++i], a[lo]))   //find position of item on left to swap
            if (i == hi) break;
        
        while (less(a[lo], a[--j]))   //find position of item on right to swap
            if (j == lo) break;
        
        if (i >= j) break;            //check if arrows (positions i and j) cross and we are 
                                      //ready for final exchange
        
        exch(i, j);                   //swap the elements at positions i and j
    }
    
    exch(lo, j);     // final exchange (with pivot)
    
    return j;        // return index of item now known to be in place
}

Note that the comparison cost of partitioning $n$ items using the method above (which for clarity, we'll call "ends-to-the-middle" partitioning" but is actually known as "Hoare's Partitioning" -- named after Tony Hoare, who invented the quicksort algorithm) is always either $C(n) = n+1$ or $C(n) = n$, and thus always $\sim n$.

To see this, note that when the partitioning will result in the pivot element moving anywhere but to the end, the pivot is never compared to itself (j never gets all the way down to lo). However, the last purple and green elements considered (i.e., the $A$ and $W$ in the example above) get compared to the pivot twice each (due to the "crossing of the arrows"), yielding $(n-1)+2 = n+1$ comparisons.

There are two cases when the pivot moves to the end. It might be that we compared the pivot with all $n-1$ elements and never found one to "throw right". In this case, as we search for one to "throw left", we find one with our first comparison on the right. Thus we have a total of $n$ comparisons in this case. It might also be that the first one that should be "thrown right" is the last element on the right. It still takes $n-1$ comparisons to find this element, but as we subsequently look for the element to "throw left", we compare both the last and second to last elements with the pivot -- giving us a total of $n+1$ comparisons.

When the partioning doesn't move the pivot -- such as when the array is already in order -- we again have $n+1$ comparisons are made, as we make exactly one comparison to find the element on the left to swap. However, we then make $n$ more comparisons to find the element on the right to swap, as the above code will ultimately compare the pivot with itself if j manages to decrement all the way to lo.