Truly Understanding Quicksort

In-place partitioning

The main difficulty in implementing quick-sort is doing the partitioning in-place.

If we had additional space, we would walk the array one-by-one and save the elements smaller than the pivot into a second, auxiliary, array and the elements larger into a third array.

      v
    7 2 8 4 3 6 9

        v
    7 2 8 4 3 6 9

          v
    7 2 8 4 3 6 9

         ... (and so on)

                  v
    7 2 8 4 3 6 9

small: 2 4 3 6
large: 8 9

At the end, we would find our partitioning by combining small, pivot, and large, in this order.

To achieve the partitioning in-place, i.e., without using additional storage, there are several strategies and I will show you the simplest one. We use two indices, l and r, that satisfy the following property:

  _ _ _ _ p ? ? ? ? ? ` ` ` `
          ^         ^
          l         r

the pivot is at position l, everything to the left of l is smaller than the pivot and everything to the right of r is larger than the pivot. For the elements marked “?”, we do not know anything yet.

Initially, l is 1 and r is the last element in the array.

    7 2 8 4 3 6 9
    ^           ^ 
    l           r

We now take steps that decrease r or increase l to make the interval [l, r] smaller, until only the pivot is in the interval and thereby l = r.

If there is an element larger than the pivot at position r, we move r towards the left:

    7 2 8 4 3 6 9
    ^         ^  
    l         r

This ensures that to the right of r we only have elements larger than the pivot.

Otherwise, if the element as position l + 1 is smaller than the pivot, we swap the elements at positions l and l + 1 and increment l.

    2 7 8 4 3 6 9
      ^       ^  
      l       r

This ensures that to the left of l we only have elements smaller than the pivot.

If none of the two operations above can be performed, like in the picture above, l + 1 points to an element larger than the pivot and r points to an element smaller than the pivot. It would be useful if it were the other way around, since we would have just skipped over the two elements in the previous steps.

       l+1
        v
    2 7 8 4 3 6 9
      ^       ^  
      l       r

Therefore, in this third case, we simply swap l+1 and r:

       l+1
        v
    2 7 6 4 3 8 9
      ^       ^  
      l       r

The interval [l,r] remains the same in this third case, but we are sure to lower it in the following two steps at least.

We repeat the procedure above until l = r:

Decrease r as long as it contains elements greater than the pivot:

    2 7 6 4 3 8 9
      ^     ^  
      l     r

Increase l and move the pivot towards the right as long as l+1 has elements smaller than the pivot:

    2 6 7 4 3 8 9
        ^   ^  
        l   r

    2 6 4 7 3 8 9
          ^ ^  
          l r

    2 6 4 3 7 8 9
            ^  
           l=r

At this point we are done: all elements smaller than 7 are to the left and all elements larger than 7 are to the right.

Go to the next page to see how to implement quicksort in C.