Раздел Хора не работает, когда более одного значения равно повороту

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

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)

python sorting algorithm quicksort hoare-logic
person MadRabbit    schedule 09.07.2016    source источник

Ответы (1)


arrow_upward
2
arrow_downward

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

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

Обратите внимание, что разделение будет немного отличаться в зависимости от того, уберете ли вы проверку на равенство для left_index или right_index. Имеет значение для граничных случаев, когда опорный элемент оказывается наименьшим или наибольшим значением в списке. Принимая во внимание, что в начале 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
person Leon    schedule 10.07.2016
comment
Хммм... Несмотря на то, что после удаления знака равенства он больше не входит в бесконечный цикл, он по-прежнему не разделяет список должным образом... даже кажется, что случаи, которые раньше работали хорошо, больше не работают с этим изменением: D Учхх, не могли бы вы взгляните на мой код глубже, так как из этого я думаю, что, возможно, допустил некоторые ошибки в самых основах реализации алгоритма... Спасибо ^^ - person MadRabbit; 10.07.2016