擬似コードからカウントソートアルゴリズムを実装しました。擬似コードでは、最後のループC[A[j]]は最初のパスの後でデクリメントします。これはすべてを右にシフトしていたので、正しい結果を生成するために、最初のパスの前にデバッグとデクリメントを行いました。しかし、それが機能すること以外に理由がわかりません。なぜ、後ではなく前にデクリメントする必要があるのですか。
後でデクリメントしたときの結果は次のとおりです。
10 1 0 6 8 3 2 0 9 4
0 0 0 1 2 3 4 6 8 9
そして、私が前にデクリメントしたとき：
10 1 0 6 8 3 2 0 9 4
0 0 1 2 3 4 6 8 9 10
明らかに、最初はすべてが右にシフトされていたので、すべてを左に移動しましたが、そもそもなぜ正しい位置に配置されないのでしょうか。
int* counting_sort(int A[], int size, int k)
{
int* B = new int[size];
int* C = new int[k+1];
for(int i = 0; i <= k; i++)
C[i] = 0;
for(int j = 0; j < size; j++) {
C[A[j]]++;
}
for(int i = 1; i <= k; i++) {
C[i] += C[i-1];
}
//print(C,k+1);
for(int j = size-1; j >= 0; j--) {
B[--C[A[j]]] = A[j];
}
delete [] C;
return B;
}
for(int j = size-1; j >= 0; j--) {
B[--C[A[j]]] = A[j];
}
と同等です：
for(int j = size-1; j >= 0; j--) {
int element = A[j];
int pos = C[element] - 1;
B[pos] = element;
C[element]--;
}
配列を想像してみてください1 0 1。これで、要素の数は次のようになります。
0-1回
1-2回
：それらに先行する要素の量によって位置増分カウントの調製
01 -
1- 3
新しい（ソートされた）配列内の要素の位置は（カウント-1）になりました：
位置0= 1 --1 = 0
最初の位置1= 3-1 = 22
番目の位置= 2 --1 1= 1
それを作る0 1 1。
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加