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
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.
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:
- What am I getting wrong?
hibe used for pivoting or there is a very specific fundamental reason to pick