複数の値がピボットに等しいときにホアレパーティションが機能しない

Question

ホーレパーティション機能をよりよく理解するために、自分自身のホアレパーティション機能を作成しようとしています。私はその定義と擬似コードを順調に進んだと思っていましたが、多くの場面で期待どおりに動作するように見えますが、ピボットに等しい複数の値を持つリストが渡されたときに崩壊して無限ループに入ります。バグを修正するにはどうすればよいですか？

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の両方でピボット値と等しいかどうかをテストしています。これにより、両方のインデックスがピボット値のある要素でスキップすることを効果的に防ぎます。したがって、2つ以上のピボット値の要素がリストの中央に向かってプッシュされると、left_indexとright_indexは克服できない障壁によって分離されます。それらのいずれかの行の等号を削除すると、停止していない問題はなくなります。

しかし、この変更の結果としてleft_indexを動かすループはright_index上記1つの位置でそれをプッシュすることとしてもその初期位置にright_index滞在境界の外に出ます。同様に、right_indexを動かすループは、left_indexの下の1つの位置でそれを押し、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