Hoare partitioning scheme in Quicksort

Question

I'm reading about Quicksort algorithm, specifically using the Hoare partitioning scheme.

Wikipedia page says, that when choosing a pivot element one can use both hi and lo indexes. However, when implementing the same code in Python, my code fails in a very specific circumstances. My python code is a translation of the pseudo-code from Wikipedia.

def swap(A, i, j):
   A[i], A[j] = A[j], A[i]


def quick_sort_hoare(A, lo, hi):
    if lo < hi:
        p = hoare_part(A, lo, hi)
        quick_sort_hoare(A, lo, p)
        quick_sort_hoare(A, p + 1, hi)


def hoare_part(A, lo, hi):
    i = lo - 1
    j = hi + 1

    pivot = A[lo]

    while True:
        while True:
            i += 1
            if A[i] >= pivot:
                break

        while True:
            j -= 1
            if A[j] <= pivot:
                break

        if i >= j:
            return j

        swap(A, i, j)

This particular code works for many-many test-cases generated at random. However if I put pivot = A[hi] in partitioning, sometimes it fails. Specifically, when the last element(i.e. pviot) appears to be the largest in the array at hand. In that case i appears to be equal the length of the array and everything goes to the infinite recursion.

Furthermore, in Introduction to Algorithms by Cormen et al., we see the following pseudo-code for the same partitioning:

This piece of code seems to be identical to the one from Wikipedia. Moreover, seems like the code would fail on their example. Because I understand this very unlikely to be the case for them to make this mistake, I'm wrong somewhere.

So my questions are:

1. What am I getting wrong?
2. Can hi be used for pivoting or there is a very specific fundamental reason to pick A[lo]?

Answer 1

"The devil is in the details". Algorithms and programming, fortunately and unfortunately, needs the greatest attention to detail.

The part of code that are critical here are the following three groups of the code interleaved with comments. The first two lines of code is how to do the recursion. The middle one line of code is how to choose the pivot. The last two lines of code is how to determine the index that will be used by that first two lines of code to split the part of array between lo and hi.

#
# code skipped here
#
        quick_sort_hoare(A, lo, p)
        quick_sort_hoare(A, p + 1, hi)
#
# code skipped here
#
    pivot = A[lo]
#
# code skipped here
#    
        if i >= j:
            return j  

The above version, as in OP's post and as in Wikipedia, is correct.

However, as mentioned by OP, the above version with its middle line of code changed to pivot = A[hi] will run into an infinite loop if given an array of more than one element whose unique largest element is its last element. A simple example of such an array is $[0,1]$ or $[1,0,2]$.

When the Wikipedia page says "there are many variants of this algorithm, for example, selecting pivot from A[hi] instead of A[lo]", it means the following variant. On first look, nobody would expect this change of pivot would require code at two other places be changed. However, it is natural from the point of symmetry. The above version is NOT symmetric with respect to lo and hi. In fact, since only one splitting index is returned when two indices iand j crosses, there is no way to be symmetric! The only way to restore symmetry is creating a mirroring variant like below.

#
# code skipped here
#
        quick_sort_hoare(A, lo, p - 1)
        quick_sort_hoare(A, p, hi)
#
# code skipped here
#
    pivot = A[hi]
#
# code skipped here
#    
        if i >= j:
            return i 

The posted code as in problem 7.1 of CLRS's Introduction To Algorithms, third edition is correct, too, since it is the same as your code and the code in Wikipedia. In particular, it works correctly on their example, $[13, 19, 9, 5, 12, 8, 7, 4, 11, 2, 6, 21]$. I suspect that you missed the part e of that problem, "Rewrite the QUICKSORT procedure to use HOARE-PARTITION". The expected result of the rewrite will be a procedure that is just like your Python function quick_sort_hoare . In fact, that problem is written in great detail in order to prove its correctness. I would like to encourage you to go over that problem closely.