Раздел Hoare не работает, когда более чем одно значение равно pivot

Question

Я пытаюсь написать свою собственную функцию разбиения Hoare, чтобы лучше понять это. Я думал, что хорошо следовал его определению и псевдокоду, но, несмотря на то, что во многих случаях он работает, как и ожидалось, он разваливается и входит в бесконечный цикл, когда передается список с несколькими значениями, равными pivot. Где моя ошибка, как я должен изменить это, чтобы исправить ошибку?

def partition(lst, left_index, right_index):
    pivot = lst[right_index]


    while True:
        #Increment left index until value at that index is greater or equal to pivot
        while True:
            if lst[left_index] >= pivot: break
            left_index += 1

        #Increment right index until value at that index is less or equal to pivot
        while True:
            if lst[right_index] <= pivot: break
            right_index -= 1

        if left_index < right_index:
            lst[left_index], lst[right_index] = lst[right_index], lst[left_index]
        else:
            return right_index

return partition(0, end)

Answer 1

Вы проверяете на равенство с опорным значением в обоих lst[left_index] >= pivot а также lst[right_index] <= pivot, Это эффективно предотвращает пропуск обоих индексов по сводным элементам. Поэтому, когда два или более сводных элемента выдвигаются к середине вашего списка, left_index а также right_index быть разделенным непреодолимым барьером. Удалить знак равенства в одном из тех breakЕсли у вас не возникнут проблемы, то проблема без остановок исчезнет.

Однако в результате этого изменения цикл, который перемещается left_index может подтолкнуть его на одну позицию выше right_index и даже выйти за пределы, когда right_index остается в исходном положении. Точно так же цикл, который движется right_index может подтолкнуть его на одну позицию ниже left_index и даже выйти за пределы, когда left_index остается в исходном положении. Чтобы этого не случилось, вы должны изменить while True: в этих циклах while left_index < right_index:,

Обратите внимание, что разбиение будет немного отличаться в зависимости от того, удаляете ли вы проверку равенства для left_index или же right_index, Это имеет значение для граничных случаев, когда элемент pivot оказывается наименьшим или наибольшим значением в списке. Учитывая, что в начале right_index представляет внутреннюю позицию относительно диапазона ввода и left_index указывает на граничную позицию, вы должны разрешить left_index чтобы пропустить сводные значения, тогда как right_index необходимо дать команду остановиться на значениях поворота (противоположная логика позволила бы left_index оставаясь в своей начальной позиции до конца алгоритма, в то время как right_index может быть вытолкнут вплоть до left_index, не производя никакого разделения).

Таким образом исправленный код будет таким:

def partition(lst, left_index, right_index):
    pivot = lst[right_index]

    while True:
        while left_index < right_index and lst[left_index] <= pivot:
            left_index += 1

        while left_index < right_index and lst[right_index] > pivot:
            right_index -= 1

        if left_index < right_index:
            lst[left_index], lst[right_index] = lst[right_index], lst[left_index]
        else:
            return right_index