Jon Bentleys beautiful quicksort - how does it even work?

Question

I thought I had a good understanding of how quicksort works, until I watched the vid on http://code.google.com/edu/algorithms/index.html where Jon Bentley introduced his "beautiful quicksort code", which is as follows:

void quicksort(int l, int u){
    int i, m;
    if(l >= u) return;
    m = l;
    for(i = l+1; i<= u; i++)
        if(x[i] < x[l])
            swap(++m, i); //this is where I'm lost. Why the heck does it preincrement?

    swap(l, m);

    quicksort(l, m-1);
    quicksort(m+1, u);

}

Another part of the algo that confuses me is the final swap after the FOR loop. Why is that neccessary? Lets assume that the array is already in order. If that is true, no swaps will occur since x[i] > x[l]. At the end, we swap l with m. That screws up the order.

Am I missing something?

Thanks.

Answer 1

On the beginning m is set to l, and the element x[l] is chosen to be partitioning element (pivot).

Next, the algorithm iterates over a list and, whenever it finds an element less than x[l], it moves it just after the current m. That means, when m > l, then elements on all positions from l+1 to m, are lesser than element x[l].

For example:

3 5 4 2 1  l = 0, m = 0, i = 1
  ^
3 5 4 2 1  l = 0, m = 0, i = 2
    ^
3 2 4 5 1  l = 0, m = 1, i = 3
      ^
3 2 1 5 4  l = 0, m = 2, i = 4
        ^

and at the end, we swap the last of the smaller numbers with the first (partitioning) element to get:

1 2 3 5 4

If there are no smaller elements than the first one, the swap does nothing (because m is equal to l).

Answer 2

The element at x[l] is the chosen pivot. The invariant of the for loop is that all elements x[l+1] through x[m] are less than the pivot, and all elements from x[m] through x[i] are bigger or equal to the pivot.

When it finds an element less than the pivot, it moves it down to entry m+1, then bumps up m. (The entry at m+1 was bigger than the pivot, and thus moving it up is fine.)

The last swap is to move the pivot from x[l] to x[m] because it needs to end up between the lower array and the upper array. If no swaps happen (sorted array example), then m==l and the final swap doesn't move anything.

The code would be clearer pedagogically to set m = l + 1 and use m++ instead of ++m.