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

An Alternate Partitioning Technique

In this technique for partioning the elements of an array with respect to some pivot value, we make a single pass through the array from one end to the other, instead of from both ends to the middle as seen in the first technique shown. Again, let us demonstrate with an example.

Suppose we wish to partition the following section of an array:

This time, we first choose the rightmost element (i.e., $E$) to server as the pivot element, which we mark in red.

Starting with the left-most element, we then examine each element of the array until we find something less than or equal to the pivot $S$. We stop at the end of the section, if we don't find any such elements. To make it easier to see the portion of the array found to be greater than the pivot, we color these elements green. Likewise, we color the elements found to be less than or equal to the pivot purple. The elements that have not yet been compared with the pivot are left colored black.

In this case, we find the first element less than the pivot to be $C$. We want to keep elements less than the pivot to the left of those greater than the pivot, so we exchange it with the left-most green element found. If no green elements have been found, we exchange it with the left-most element in our array range.

Picking up where we left off, we continue individually comparing the elements to the right of $C$'s original position with the pivot, noting that $K,S,O,R,$ and $T$ are all greater than the pivot (and hence are colored green), but $A$ is less than or equal to the pivot (and hence colored purple). Again, we exchange the $A$ with our left-most green element. $$\begin{array}{|c|c|c|c|c|c|c|c|c|c|}\hline \color{purple}C & \color{green}U & \color{green}I & \color{green}Q & \color{green}K & \color{green}S & \color{green}O & \color{green}R & \color{green}T & \color{purple}A & W & E & S & O & M & \color{red}E\\\hline & \rightarrow & & & & & & & & \leftarrow & & & & & & \wedge \end{array}$$ $$\begin{array}{|c|c|c|c|c|c|c|c|c|c|}\hline \color{purple}C & \color{purple}A & \color{green}I & \color{green}Q & \color{green}K & \color{green}S & \color{green}O & \color{green}R & \color{green}T & \color{green}U & W & E & S & O & M & \color{red}E\\\hline & & & & & & & & & & & & & & & \wedge \end{array}$$

Again picking up where we left off, we continue individually comparing the elements to the right of $A$'s original position with the pivot, noting that $W$ is greater than the pivot (and thus colored green), while $E$ is less than or equal to the pivot (and thus, purple). We again exchange this purple $E$ with the left-most green element, $I$.

This time when we continue to individually compare the elements to the right of $E$'s original position with the pivot, none of the remaining elements are found to be less than or equal to the pivot. As such, we stop when we get to the right-most element of the array and color the remaining elements green.

It remains to place the pivot between the elements found to be less than or equal to it (purple) and those found to be greater than it (green). This is easily accomplished with a final exchange of the pivot with the left-most green element.

Having done this last exchange, we see that $E$ 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 elements remaining in the section that are to the left of $E$ and then recursively sort the elements remaining in the section that are to the right of $E$, the entire section will be completely sorted.

It should be noted that if the array has duplicate elements -- any elements equal to the pivot are moved to the left of the final pivot position, but moved adjacent to this position in the later sorting done recursively.

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 position of the element currently being compared to the pivot with index j, starting it at low and incrementing it until it reaches hi-1. Additionally, we'll keep track of the position of the left-most green element above with the index i, starting it at lo-1 (since there are initially no green elements) and moving it one element to the right for each exchange.

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 - 1;                   // initially no elements have been found
                                      // to be less than or equal to pivot

    for (int j = lo; j < hi; j++) {   // compare elements working from the left 
                                      // to the right with the pivot...

        if (!less(a[hi],a[j])) {      // when one is found to be less than or 
                                      // equal to the pivot, exchange it with 
            i++;                      // the left-most element found to be less  
            exch(i,j);                // than or equal to the pivot
        }
    }

    exch(i+1,hi);     // final exchange to put the pivot in the proper place between
                      // those elements less than it and those elements greater than it
    
    return i+1;       // return the final position of the pivot
}

Note that the comparison cost of the above method to partition $n$ items is $C(n) = n-1$. To see this, note that the pivot is compared to all of the other $n-1$ array elements exactly once, but never to itself.

Let us call this method "left-to-right" partitioning for clarity, but know it is more widely known as "Lomuto Partitioning" (being attributable to Nico Lomuto). It actually performs slightly worse than Hoare's "ends-to-the-middle" partitioning in the worst case, but has an advantage in that it only traverses the array in one direction, one time. In particular, this means the same basic algorithm can be employed to apply quicksort to a singly-linked list.