Быстрая сортировка с использованием Hoare Partitioning, то, как я выбрал опору, влияет на мой python агрегат

Question

Я пытаюсь реализовать Quicksort, используя Hoare Partitioning в python, используя код из { ссылка }

Но когда я изменяю pivot = a_list[low] на pivot = a_list[high], я просто могу не заставить его работать!

Может кто-нибудь помочь?

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 ----

Чтобы убедиться, что я действительно понимаю quicksort, я также попытался разделить lomuto с помощью pivot = array[low]. Это оказалось еще одной проблемой, поэтому проверьте обновленный ответ @rcgldr.

Answer 1

Изменение имен на [], lo, hi, p (pivot)

Для кода, о котором идет речь, pivot может быть любым элементом, кроме [hi]. Для примера проблемы с pivot = a [hi], рассмотрим случай, когда lo = 0, hi = 1 и a [0]

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)

---

Переключение к возвращению lo, p-1, p, разрешает для pivot быть любой элемент, кроме [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 с pivot = a [lo], в одной функции , После шага раздела он перезаписывается только на меньший раздел, затем обновляет lo или hi и возвращается назад для обработки большего раздела. Это ограничивает сложность стекового пространства O (log (n)), но сложность времени в наихудшем случае все еще составляет 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

Answer 2

Кажется, достаточно внести исправления:

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