4

多くの Web サイトで提供されている疑似コードに従って、私はこのHoare分割アルゴリズムを作成しました。これは、指定されたピボットに基づいて分割されるサブ配列の開始インデックスと終了インデックスである配列を取ります。それは正常に動作しますが、誰かがロジックを説明できますか? コードは次のとおりです。

def hoare(arr,start,end):
     pivot = 4
     i,j = start,end
     while i < j:
        while i < j and arr[i] <= pivot:
            i += 1
        while j >= i and arr[j] > pivot:
            j -= 1
        if i < j:
            arr[i],arr[j] = arr[j],arr[i]
     return j

パーティショニングの別の変形であるLomutoアルゴリズムがあります。Hoareそもそもアルゴリズムを理解していないため、違いを見つけることはできませんが、似たようなことを行います。アルゴリズムで何が起こっているのか、どのケースでどちらがより良いパフォーマンスを発揮するのかを誰かが説明できますか?

4

2 に答える 2

2

カードのデッキと 2 つのポーン/コインを使用してこれをシミュレートすることをお勧めしiますj。基本的に、このアルゴリズムは次の 2 つのことを同時に達成します。

  • この位置の左右に正しい量の「バケット」を配置するために、配列を分割する必要がある場所を見つけます。これは、パーティションの「中間」でiとの値が一致することによって行われます。j
  • ピボットよりも大きいか小さいかに応じて、配列要素を中央の左または右に移動します。

これはi、常に中央または左側にあることを意味します。については逆ですj。これを知っていると、whileループが行うことは、中央の左側にあるが右側にあるはずの要素を見つけることであり、その逆であることがわかります。つまり、間違った半分にある2 つの要素を見つけます。これらはその後交換されます。

とが真ん中で出会うと、左側には によってスキップされた要素がありi、それらは よりも小さいためです。または反対側から交換された要素であり、したがって よりも小さいです。(真ん中より右側の要素についてはその逆です。)jwhilepivotpivot

混乱の原因として考えられるのは、ゼロベースの配列インデックスが要素を指すか、2 つの要素間を指すと考えられることです。たとえば、インデックス0は基本的に「配列の「0番目」と最初の要素の間」を意味し、要素にアクセスするときは、この位置に続くarray[0]ものを取得します-直感的に配列の最初の要素になります。

于 2012-09-22T19:51:35.457 に答える