1

配列の中央値を返すアルゴリズムを実装する必要があります。そこで、これには効率的であると思われる Quickselect を実装することにしました。3 分割には、Quicksort で使用されているものと同じ分割アルゴリズムを使用できることがわかりました。

私の講義ノート (C コード) で報告されているパーティション アルゴリズムは次のとおりです。

for (i = lo, j = hi;
     (i <= j);)
{
    while (a[i] < pivot)
    {
        i++;
    }

    while (a[j] > pivot)
    {
        j--;
    }

    if (i <= j)
    {
        if (i < j)
        {
            /* exchange values */
            tmp = a[i];  
            a[i] = a[j];
            a[j] = tmp;
        }

        i++;
        j--;
    }

}

ここで、配列が a = [40, 20, 100, 60, 80] で、ピボットとして 80 を選択すると、結果は a = [40, 20, 80 , 60, 100] になりますが、右側のパーティションの値がすべて > 80 ではないことがわかります (60 あります)。他の数値を選択すると、アルゴリズムは適切に機能します。

このアルゴリズムは間違っていますか？

事前に助けてくれてありがとう！

4

2 に答える 2

1 
[40, 20, 100, 60, 80]
          i ... #while (a[i] < pivot)

[40, 20, 100, 60, 80]
          i        j ... #while (a[j] > pivot)

[40, 20, 80, 60, 100]
          i        j ... #/* exchange values */

[40, 20, 80, 60, 100]
             ij ... #i++;j--;

[40, 20, 80, 60, 100]
              j   i  ... #while (a[i] < pivot)

[40, 20, 80, 60, 100] ... exit for-loop .. finish
于 2014-09-09T10:18:23.380 に答える
1

クイック選択の場合、ピボット要素の正しい位置を見つける再帰アルゴリズムを使用する必要があるため、配列全体を 2 つの半分に分割します [ピボット位置の右側にある要素はピボットよりも小さい値を持ち、左側にある要素はピボット位置はピボットよりも価値があります]

あなたのアルゴリズムは、最初のループが終了した後に何をすべきかを考慮していません。最初に選択されたピボット要素の位置のみを見つけます（それはあまりにも間違っています）。見つかったピボット位置が中間位置でない場合 (選択したピボットが中央値でない場合) はどうなりますか?

その後、左側の部分に移動する必要があります (ピボット要素の新しく見つかった位置が中央の位置よりも大きい場合)、そうでない場合は右側の部分に移動し、上記の手順をもう一度実行します。

何もわからない場合はコメントしてください

于 2014-09-09T11:50:31.910 に答える