0

このカウントソートの実装における2番目のループの目的を誰か説明してもらえますか?:

short c[RADIX_MAX] = {0};
int i;

for (i = 0; i < LEN_MAX; i++) {
    if (i == len)
        break;
    int ind = a.getElem(i); 
    c[ind]++;
}

for (i = 1; i < RADIX_MAX; i++) {
    if (i == radix)
        break;
    c[i] += c[i - 1];
}

for (i = LEN_MAX - 1; i >= 0; i--) {
    int j = i - LEN_MAX + len;      
    if (j < 0)
        break;
    int ind = a.getElem(j);
    short t = ind;
    ind = --c[ind];
    b.setElem(ind, t);
}
4

2 に答える 2

1

カウントソートは、要素自体の値からソートされる各要素のターゲットインデックスを計算することによって機能します。関連するパスは 3 つあります。

  • 最初のループでは、各要素がカウントされます。たとえば、配列には 6 つの "A" と 2 つの "B"、5 つの "C" などがあります。

  • 2 番目のループでは、各要素のインデックスが計算されます。「A」が 6 つある場合、最初の「B」はインデックス 6 (0 ベースのインデックス) に配置する必要があります。コードを単純にし、ソートを安定させるために、カウントソートが行うことはもう少し複雑です。3 番目のループでは、元の配列を逆の順序でトラバースするため、2 番目のループでは、指定された値の最初のインスタンスではなく、最後のインスタンスのインデックスを計算します。. 上記の例では、最後の「A」はインデックス 5 にある必要がありますが、最後の「B」はインデックス 6 (「A」) + 2 (「B」) - 1 (ゼロ ベース) にある必要があります。 index 7. したがって、各値について、その値の終了インデックスを計算します。以前に計算されたカウントを現在のカウントに追加して、count 配列を前方に移動します。したがって、count 配列では、「A」の値は 6 のまま (前の要素がない)、「B」の値は 6+2=8 (6 つの「A」+2 つの「B」)、C の値は現在は 6+2+5=13 (6 つの「A」+2 つの「B」+5 つの「C」) などです。

  • 最後のループでは、値がその位置に挿入され、進むにつれてインデックスが減少します。したがって、最後の "B" はインデックス 7 に挿入され、その前の "B" はインデックス 6 に挿入されます。これにより、等しい要素の元の順序が保持され、基数ソートに不可欠なソートが安定します。

于 2013-04-08T20:06:02.793 に答える
1

桁ごとに、ソートされた配列の開始位置のインデックスをカウントします。例:
array: 0 0 0 0 2 2 3 3 3 9 9
index: 0 1 2 3 4 5 6 7 8 9 10
次に、c[0] = 0、c[1] = 4、c[2] = 4、c [3] = 6、c[4] = 9、... c[9] = 9
。桁が表示されるソート済み配列は、前の桁のインデックスと前の桁の数によって異なります。2 番目のループはこれをカウントします。

于 2013-04-08T20:54:55.190 に答える