3 way partitioning by an external element

Question

There is a 3-way partitioning algorithm designed by Bentley-Mcilroy, which runs somewhat like this (partitioning on basis of the first element. Initially i = p = 0 and j = q = n-1):

Scan i from left to right so long as a[i] < a[lo].
Scan j from right to left so long as a[j] > a[lo].
Exchange a[i] with a[j].
If a[i] == a[lo], exchange a[i] with a[p] and increment p.
If a[j] == a[lo], exchange a[j] with a[q] and decrement q.

This continues as long as i <= j. Once this breaks,

Scan j and p from right to left and exchange a[j] with a[p].
Scan i and q from left to right and exchange a[i] with a[q].

Now I want to modify it so that instead of partitioning it about the first element, I can partition it based on any external element, say an integer pivot (it may be that pivot is same as one of the elements in the array, may be the first one too!). How can I do this? I tried doing it by setting p to -1 instead of 0, not working!

Answer 1

You need to replace all references to a[lo] with pivot.