How to modify Lomuto partition scheme?

Question

Lomuto partition is a simple partition algorithm used in quicksort. The Lomuto algorithm partitions subarray A[left] ... A[right] and assumes A[left] to be a pivot. How to modify this algorithm to partition A[left] ... A[right] using a given pivot P (which differs from A[left]) ?

Answer 1

Lomuto's partioning algorithm depends on the pivot being the leftmost element of the subarray being partitioned. It can also be modified to use the rightmost element of the pivot instead; for instance, see Chapter 7 of CLRS.

Using an arbitrary value for the pivot (say something not in the subarray) would screw things up in a quicksort implementation because there would be no guarantee that your partition made the problem any smaller. Say you had zero as the value you pivoted on but all N array entries were positive. Then your partition would give at zero-length array of elements <= 0 and an array of length N containing the elements >= 0 (which is all of them). You'd get an infinite loop trying to do quicksort in that case. Same if you were trying to find the median of the array using that modified form of Lomuto's partition. The partition depends critically on choosing an element from the array to pivot on. You'd basically lose the postcondition that an element (the pivot) would be fixed in place for good after the partition, which Lomuto's partition guarantees.

Lomuto's algorithm also depends critically on pivoting on an element that is either in the first or last position of the array being partitioned. If you pivot on an element not located at either the very front or very end of the array, the loop invariant that is the core of why Lomuto's partition works would would be a nightmare.

You can pivot on a different element of the array by swapping it with the first (or last if you implement it that way) element as the first step. Check MIT's video lecture on Quicksort for course 6.046J where they go in depth discussing Lomuto's partitioning algorithm (though they just call it Partition) and a vanilla implementation of quicksort based on it, not to mention some great probability in discussing the expected runtime of a randomized form of quicksort:

http://www.youtube.com/watch?v=vK_q-C-kXhs

CLRS and Programming Pearls both have great sections on quicksort if perhaps you're stuck using an inferior book for an algorithms class or something.

Answer 2

depends on how you define P, is P an index or a particular element? if it is an index, then it is easy. you modify your two passes

...
i = left
j = right
while (a[i]<a[p]) i++
while (a[p]>a[j]) j--
if (i <= j)
    swap(a, i, j)
    qsort(a, left,i)
    qsort(a, j,right)
...

if P is not an index, but a particular value, then you would need to search for it first, and only then do the above with the resultant index. Because the array is not sorted yet, you can only search linearly. You could also come up with a more clever scheme (hashtable) for finding your pivot P, but I don't see why you would need to do such a thing.