Раздел 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. Это важно для граничных случаев, когда элемент поворота оказывается наименьшим или самым большим значением в списке. Принимая во внимание, что в начале 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