2

「コーメン・ライザーソン・リベスト・スタイン、第3版、問題9-1、ポイントC、ページ224」から、次の課題があります。

n個の数のセット（配列）Aが与えられた場合、順序統計アルゴリズムを使用してi番目に大きい数を見つけ、その数の周りに分割し、i個の最大数を並べ替えます。

i番目に小さい番号を見つけるRandomized-Selectアルゴリズム（同じ本の216ページ-Randomized-Partitionアルゴリズムを使用）を使用しましたが、i番目に大きい番号を見つけたい（これを「混乱を避けるためにk-th"）。基本的に、k番目に大きい数は次のように取得できます。

n-i番目+1

次に、RandomizedSelect（）を呼び出して、k番目に大きい数を見つけます。すべてがうまく機能します。

ここに、4番目に大きい数を見つける方法の例（C）があります：

int A[10] = {3, 20, 15, 4, 1, 9, 18, 64, 22, 5}; // the given A set
int ith = 4; // I want to find the 4-th largest number of A
int kth = 10 - ith + 1; // I do this "conversion" for the reasons I explained above
int i = RandomizedSelect(A, 0, 9, kth); // it returns the index of A pointing to the 4-th largest number

printf("A vector: ");
for (j = 0; j < 10; j++) printf ("%u ", A[j]); // prints the A vector partially "ordered"

printf("\n4-th largest number: %u", A[i]); // prints the 4-th largest number

そして、ここに出力の例があります：

ベクトル：3 1 4 5 9 15 18 64 22 20

4番目に大きい数：18

ここで、4番目に大きい数だけでなく、他の4つの最大数も順番に並べて表示します（例：18 20 22 64）。したがって、たとえば、前に見​​つかったi番目のインデックスから最後までAベクトルでMergeSort（）を実行します。出力は次のようになります：18 202264。

問題は、割り当てでは、i番目（4番目）の最大数を分割し、他のi（4）個の最大数を並べ替えてから、前に説明したようにMergeSort（）を実行する必要があることです。しかし、なぜそれを行う必要があるのか​​理解できません...私の例では、18前後のパーティション分割は何の意味もありません。これは、そのパーティション分割（SelectedPartition（）を呼び出した後）を実行した後のAベクトルの出力であるためです。

3 1 4 5 9 15 18 64 22 20

18

...同じ出力です！

それで、私は割り当てについて何を誤解しましたか？それとも、私はそれをより良い方法でやっていますか？

4

1 に答える 1

2

順序統計を計算するための多くの異なるアルゴリズムがあります。クイックセレクトや中央値の中央値アルゴリズムのように、多くは、実装の一部として、k番目の要素の周りに配列を自動的に分割します。ただし、選択アルゴリズムがこれを実行する必要があるという保証はありません。たとえば、すべての要素を順序統計ツリーデータ構造に配置し、k番目の要素をクエリすることで選択を実装できます。結果として、パーティションが確実に発生するように、明示的なパーティションステップを実行するのが最も適切です。

あなたの場合、すでにパーティションを作成しているアルゴリズムを使用しているので、このステップは無視しても問題ありません。

お役に立てれば！

于 2013-02-04T18:41:24.497 に答える