4

オランダ国旗問題を読んでいたのですが、C++実装の関数のlowとhigh引数が何なのか理解できませんでした。threeWayPartition

それらを並べ替える配列の最小要素と最大要素と仮定すると、ifandelse ifステートメントは意味がなく、(data[i] < low)and(data[i] > high)は常にゼロを返します。

どこが間違っていますか？

4

3 に答える 3

9

lowおよびhighは、3方向パーティションを実行するために定義した値です。つまり、3方向パーティションを実行するには、2つの値のみが必要です。

[bottom] <= low  < [middle] < high <= [top]

C ++プログラムで移動しているのは、パーティションが発生した位置です。ステップバイステップの例：

data = [ 3, 1, 4, 9, 8, 2, 6, 9, 0 ]
low  = 4
high = 8


   [ 3 , 1 , 4 , 9 , 8 , 2 , 6 , 9 , 0 ]
p^  i^                                  q^


   [ 3 , 1 , 4 , 9 , 8 , 2 , 6 , 9 , 0 ]
    p^  i^                              q^


   [ 3 , 1 , 4 , 9 , 8 , 2 , 6 , 9 , 0 ]
        p^  i^                          q^


   [ 3 , 1 , 4 , 9 , 8 , 2 , 6 , 9 , 0 ]
        p^      i^                      q^


   [ 3 , 1 , 4 , 0 , 8 , 2 , 6 , 9 , 9 ]
        p^      i^                  q^


   [ 3 , 1 , 0 , 4 , 8 , 2 , 6 , 9 , 9 ]
            p^      i^              q^


   [ 3 , 1 , 0 , 4 , 9 , 2 , 6 , 8 , 9 ]
            p^      i^          q^


   [ 3 , 1 , 0 , 4 , 6 , 2 , 9 , 8 , 9 ]
            p^      i^      q^


   [ 3 , 1 , 0 , 4 , 6 , 2 , 9 , 8 , 9 ]
            p^          i^  q^


   [ 3 , 1 , 0 , 2 , 6 , 4 , 9 , 8 , 9 ]
                p^         iq^

アルゴリズムがあなたに言うように：

  • 下部の下のすべてがすでにチェックされているため、下部の上の要素を交換します（つまり）、またはp + 1
  • 上部の上のすべてがすでにチェックされているため、上部の下の要素を交換します（つまり ）、またはq - 1
  • 中央に属しているため、要素はそのままにしておきます。

を取得し[3, 1, 0, 2]、それぞれ下部、中間、上部のパーティションとして取得します。[6, 4][9, 8, 9]

于 2012-06-26T19:33:51.810 に答える
1

} else if (data[i] >= high) {あなたが見たものは記事に書かれたものではないかもしれないことを示しています。

于 2012-06-26T18:54:22.810 に答える
0

とは、中間パーティションの値の半開放範囲lowと考えてください。未満のすべての値は、左側のパーティションになります。中央のパーティションには、までの値が含まれますが、これは含まれません。最後に、以上のすべての値が正しいパーティションになります。high[low,high)lowlowhighhigh

于 2012-06-26T19:17:45.510 に答える