2

それをよりよく理解するために、独自の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)
4

1 に答える 1

2

lst[left_index] >= pivotと の両方でピボット値との同等性をテストしていますlst[right_index] <= pivot。これにより、両方のインデックスがピボット値の要素をスキップするのを効果的に防ぎます。したがって、ピボット値を持つ 2 つ以上の要素がリストの中央に押し出されleft_index、right_index乗り越えられない障壁によって分離された場合。breakこれらのing 行のいずれかで等号を削除すると、停止しない問題はなくなります。

ただし、この変更の結果として、移動するループがleft_index1 つ上の位置に移動する可能性があり、最初の位置にとどまっているright_indexときに範囲外になることさえあります。right_index同様に、移動するループはright_index1 つ下の位置に移動する可能性があり、最初の位置にとどまっている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
于 2016-07-10T00:23:51.780 に答える