1

ソートされていない配列（またはソートされているかどうかはわかりません）でk番目に小さい要素を選択するアルゴリズムの基本的なコードが与えられました。通常、これには quickselect を使用しますが、関数名として「countingselect」とラベル付けされた別の選択肢が与えられています。

「選択のカウントは、並べ替えのカウントと同様のアプローチを使用します。リスト内のアイテムは、カウントの配列へのインデックスとして使用されます。次に、配列の低い値の終わりから始めて、合計が目的の値を超えるまで、アイテムのカウントが累積されます。」

// return the kth smallest item
int countingSelect(int items[], int first, int last, int k) {
    int counts[cap];
    for (int c = 0; c < cap; c++) {
        counts[c] = 0;
    }
    for (int i = first; i < last; i++) {
        counts[items[i]] += 1;
    }
    int c = 0;
    while (k >= 0) {
        k -= counts[c++];
    }
    return c-1;
}

関数がどのように機能するかを正確に理解できるように、これを疑似コードに分解するのに非常に苦労しています。与えられたコードで最初に混乱したのは、'cap' の値とは何か、そしてその機能とは何かということです。キャップは通常どのような値ですか? 私はこの情報を与えられていません。

アルゴリズムを疑似コードに分解することは、それを理解するための良い方法であり、コードを分解してステップ実行するための支援をお願いします。

前もって感謝します。

4

2 に答える 2

2

カウントソートを理解していれば、これは非常に簡単です。そうでない場合は、カウントソートがどのように機能するかを簡単に説明しましょう。

[0, 15] の範囲に 10 個の数値があるとします。データの境界がわかっているので、入力内容を調べて、各数値が何回表示されたかをマークできます。次に、カウントを反復処理して、番号を順番に取得します。

input numbers
counts[0..15] = 0
for i in numbers
    ++counts[numbers[i]]
for i in counts
    counts[i] times
        print i

例を見てみましょう：

numbers: 1 5 3 13 5 2 0 1 14 2

最初のループはカウントを作成します。

(index) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
counts: 1 2 2 1 0 2 0 0 0 0 0  0  0  1  1  0

2 番目のループでは次のようになります。

1 times 0
2 times 1
2 times 2
1 time 3
0 times 4
2 times 5
0 times 6
...

あれは：

0 1 1 2 2 3 5 5 13 14

アルゴリズムは基本的に同じですが、並べ替えられたリストを出力する代わりに、k 番目に小さい項目を見つけます。

上記の例では、次のことがわかります。

0th smallest numbers is 0
1st and 2nd smallest numbers are 1
3rd and 4th smallest numbers are 2
5th smallest number is 3
6th and 7th smallest numbers are 5
...

よく見ると、次のパターンがあります。

if      k <= 0 => 0
else if k <= 2 => 1
else if k <= 4 => 2
else if k <= 5 => 3
else if k <= 7 => 5
else if k <= 8 => 13
else if k <= 9 => 14

ただし、数字は

0 2 4 5 7 8 9

counts実際には、それ自体の実行中の合計です。

したがって、アルゴリズムの下部で実行されるのは実行中の合計ですが、合計が よりも大きくなったときをチェックしますk。そのとき、前の番号があなたの答えでした。のインデックスcountsは数値そのものであることに注意してください。

int c = 0;
int sum = 0;
while (k >= sum) {
    sum += counts[c++];
}
return c-1;

アルゴリズムは変数を回避しようとしましたがsum、代わりにそれ自体から実行中の合計を差し引きますkが、これは同じ効果があります。

于 2012-06-01T08:37:01.113 に答える
2

cap がリスト内の最大数であると想定します (十分なメモリを割り当てることができます)。

Counts は、リストに表示される各数値の数です。たとえば、count[n] は list 内の n の数を表します。

最初のループは、count の値を初期化します。

2 番目のループが通過し、カウントの適切な位置をインクリメントしてカウントを調整します。このループが終了すると、counts は、リストに表示される各数値の数のカウントになります。たとえば、count[n] は list 内の n の数を表します。

最後のビットが通過し、リストを繰り返し処理し、その数が k より大きくなるまで、count の最初のいくつかのインデックスの要素を合計します。次に、前の数値は k を超えた場所なので、その数値を返します。

于 2012-06-01T08:27:51.537 に答える