Question regarding Hoare's partitioning scheme and a slight modification to it

Question

This is the pseudocode on wikipedia for Hoare's partitioning scheme:

algorithm partition(A, lo, hi) is
    pivot := A[lo]
    i := lo - 1
    j := hi + 1
    loop forever
        do
            i := i + 1
        while A[i] < pivot   //Question here

        do
            j := j - 1
        while A[j] > pivot 

        if i >= j then
            return j

        swap A[i] with A[j]

This code finds an inversion and swaps it. Now, the problem of partitioning about a pivot is to divide an array such that all elements <= pivot fall in one partition, and all elements > pivot fall in the other.

My question is simple: why not use while a[i] <= pivot ?

As far as I can tell, it will work correctly, infact it would align better with the previous definition of partitioning.

If it does work, the big question is why wasn't it used in the original paper? It makes more sense and seems to be slightly faster as well (less number of swaps required).

Infact, while we're on the subject: would it be incorrect to also use while A[j] >= pivot that could further reduce the number of swaps.

I know that if I'm too worried about multiple elements repeating I should use 3 way partitioning, but I'm curious about how this algorithm would work nonetheless.

Answer 1

Why not use while a[i] <= pivot ?

You could. It's arbitrary. Either way will work fine. We just have to choose one of those two choices. They both have the same asymptotic running time.

Answer 2

The code you cited will find first element >=pivot at left and first element <=pivot at right and swap them. So, after partitioning, left part will include elements <=pivot and right part will include elements >=pivot, i.e. elements =pivot may end up in any part. In particular, original a[lo] element will end up as a[hi].

Now you should see the catch! If you will replace first comparison to A[i] <= pivot, the a[lo] element will never be moved and used time and again as the threshold in the left recursive calls! At least if partition is followed by simplest recursive calls to qsort:

qsort(lo,hi):
    if (lo>=hi) exit
    j = partition(lo,hi)
    qsort(lo,j)
    qsort(j+1,hi)

In this case, with proper implementation of the partition algorithm that puts everything <=pivot to the left part, you will just get nice infinite recursion.

Now, while we are here, let's consider 3 remaining possibilities:

• allow <=pivot on the left and >=pivot on the right: the same. a[lo] will remain in its place, and in the left recursive call all elements are <=pivot so they all be placed in the left part again.
• put <pivot to the left and >=pivot to the right: if ALL elements =pivot you will end up in infinite recursion.
• allow only <pivot on the left and only >pivot on the right, so elements =pivot on each occurence will be moved into opposite part. If at least one swapping occured, both parts are no more empty. If any of remaining elements is <=pivot, it will happen. If all remaining elements >pivot, then logic of returning j will effectively put first element into the left partition (even without any swapping!), and the rest into the right one.

So, it seems that their strange code is the only one that guarantees termination of sorting when combined with oversimplified qsort driver. It also shuffles a[lo] elements on each pass so you get enough chances to get non-quadratic behavior.

Note that this code is still not entirely correct, it should be:

    do
        j := j - 1

        if i >= j then
            return j

    while A[j] > pivot