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.

Using pivot = a_list[high} can end up with infinite recursion using Hoare partition scheme, when high = low+1. In order to use a_list[high] as pivot, I think partition will need to return low, and the recursive calls will use (... low, p-1), (..., p, high), but you'll need to test it. — rcgldr, Mar 30 '20 at 08:48

rcgldr · Accepted Answer · 2020-03-31T05:23:56.107

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

Brilliantly! So this also means if I choose pivot = (low+high)/2 I have to choose the version for pivot=low because pivot will arr[0] when there are 2 elements! Thanks! — Qiulang, Mar 31 '20 at 02:42
Sorry to bother you again I found that if I chose Lomuto partition and set pivot = a[lo] I can't make it work again. :$ Can you help again ? — Qiulang, Mar 31 '20 at 04:10
@Qiulang - If partition returns high, then it is `pivot = (low + high)/2`, which rounds down, avoiding a_list[high]. If partition returns low, then it is `pivot = (1 + low + high)/2`, which rounds up, avoiding a_list[low]. — rcgldr, Mar 31 '20 at 05:18
Thanks again. Now it looks too complicated to worth the trouble. I also google it and found that people suggest to swap the random pivoting to a[hi] and do the "normal" Lomuto partition. — Qiulang, Mar 31 '20 at 06:19
@Qiulang - Hoare partition scheme is normally quicker. [wiki article](https://en.wikipedia.org/wiki/Quicksort#Hoare_partition_scheme) . — rcgldr, Mar 31 '20 at 07:20
Yes I knew. I was practicing both of them to make sure I really understand them, as "the devils is in details" is particularly appropriate in this case. — Qiulang, Mar 31 '20 at 07:27

score 0 · Answer 2 · answered Mar 30 '20 at 08:01

0

It seems enough to make correction:

    _quicksort(a_list, low, p-1)
    _quicksort(a_list, p+1, high)

answered Mar 30 '20 at 08:01

MBo

77,366
5
53
86

1

But isn't that become Lomuto partition scheme then ? – Qiulang Mar 30 '20 at 08:02
1

No. Both Hoare and Lomuto partition might choose any value as partition (first, last, middle, random index). But you have to exclude partition value from the next work (it already stands on the final position), otherwise it takes part in treatment inifinitely, causing stack overflow – MBo Mar 30 '20 at 08:05
No I mean the wiki said "next two segments that the main algorithm recurs on are (lo..p) and (p+1..hi) as opposed to (lo..p-1) and (p+1..hi) as in Lomuto's scheme. " – Qiulang Mar 30 '20 at 08:07
Classic algorithm book texts show the same scheme of recursive calls as I said independently on partition scheme. Perhaps such modification works: `_quicksort(a_list, low, p - 1) _quicksort(a_list, p, high)` but I don't know why we want to reuse partition element. – MBo Mar 30 '20 at 08:29
@MBo - with Hoare partition scheme, the pivot and elements equal to the pivot can end up anywhere. The index returned by Hoare partition doesn't point to the index, so none of the elements can be excluded from the recursive calls. Each pivot isn't guaranteed to be in place until the sub-array size is reduced to 1. Lomuto partition scheme does put the pivot in place and returns an index to the pivot, so the pivot element can be excluded from recursive calls. – rcgldr Mar 31 '20 at 07:23
@rcgldr OK, I see now. That is why some Hoare partition implementations puts pivot into known place (end) and works with the rest – MBo Mar 31 '20 at 07:45

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

2 Answers2