Quicksort using Hoare Partitioning, how I chose pivot affects my python implement

Question

I am trying to implement Quicksort using Hoare Partitioning in python, using the code from https://stackoverflow.com/a/41211360/301513

But when I change pivot = a_list[low] to pivot = a_list[high] I just can't make it work!

Can someone help?

def quicksort(a_list):
    """Hoare partition scheme, see https://en.wikipedia.org/wiki/Quicksort"""
    def _quicksort(a_list, low, high):
        # must run partition on sections with 2 elements or more
        if low < high: 
            p = partition(a_list, low, high)
            _quicksort(a_list, low, p)
            _quicksort(a_list, p+1, high)
    def partition(a_list, low, high):
        pivot = a_list[low] # changing to pivot = a_list[high] breaks the program
        while True:
            while a_list[low] < pivot:
                low += 1
            while a_list[high] > pivot:
                high -= 1
            if low >= high:
                return high
            a_list[low], a_list[high] = a_list[high], a_list[low]
            low += 1
            high -= 1
    _quicksort(a_list, 0, len(a_list)-1)
    return a_list

---- update ----

To make sure I really understand quicksort, I also tried lomuto partitioning with pivot = array[low]. It turned out to another challenge, so check @rcgldr updated answer too.

Answer 1

Changing names to a[], lo, hi, p (pivot)

For the code in the question, the pivot can be any element except a[hi]. For an example of the issue with pivot = a[hi], consider the case where lo = 0, hi = 1, and a[0] < a[1].

a[] = {2,3}
partition:
    p = a[1] = 3
    since a[lo]  < p, lo += 1 = 1
    since a[hi] == p, hi      = 1
    return hi = 1
_quicksort(a, lo, p) == _quicksort(a, 0, 1) (infinite recursion)

---

Switching to returning lo, p-1, p, allows for the pivot to be any element except for a[lo]:

a[] = {2,3}
partition:
    p = a[1] = 3
    since a[lo]  < p, lo += 1 = 1
    since a[hi] == p, hi      = 1
    return lo = 1
_quicksort(a, lo, p-1) == _quicksort(a, 0, 0) (ok)
_quicksort(a,  p,  hi) == _quicksort(a, 1, 1) (ok)

a[] = {3,3}
partition:
    p = a[1] = 3
    since a[lo] == p, lo      = 0
    since a[hi] == p, hi      = 1
    swap(a[lo], a[hi]) a = {3,3}
    lo += 1 = 1
    hi -= 1 = 0
    since a[lo] == p, lo      = 1
    since a[hi] == p, hi      = 0
    return lo = 1
_quicksort(a, lo, p-1) == _quicksort(a, 0, 0) (ok)
_quicksort(a,  p,  hi) == _quicksort(a, 1, 1) (ok)

a[] = {4,3}
partition:
    p = a[1] = 3
    since a[lo]  > p, lo      = 0
    since a[hi] == p, hi      = 1
    swap(a[lo], a[hi]) a = {3,4}
    lo += 1 = 1
    hi -= 1 = 0
    since a[lo]  > p, lo      = 1
    since a[hi] == p, hi      = 0
    return lo = 1
_quicksort(a, lo, p-1) == _quicksort(a, 0, 0) (ok)
_quicksort(a,  p,  hi) == _quicksort(a, 1, 1) (ok)

---

Lomuto with pivot = a[lo], in a single function. After a partition step, it recuses only on the smaller partition, then updates lo or hi and loops back to handle the larger partition. This limits stack space complexity to O(log(n)), but worst case time complexity is still O(n^2).

def quicksort(a, lo, hi):
    while(lo < hi):
        pivot = a[lo]
        i = lo+1
        for j in range(lo+1, hi+1):
            if a[j] < pivot:
                a[i],a[j] = a[j],a[i]
                i += 1
        i -= 1
        a[i],a[lo] = a[lo],a[i]
        if(i - lo <= hi - i):
            quicksort(a, lo, i-1)
            lo = i+1
        else:
            quicksort(a, i+1, hi)
            hi = i-1