並べ替えソート、ソートされた配列のインデックス0

Question

計算ソートアルゴリズムについて質問がありました。私はそれについて読んでいて、例ではコードを段階的に分析していましたが、少し詳細を理解しているとは思いません。正しく理解すれば、アルゴリズムが機能するためには、ソートされた配列、またはそれはアルゴリズムの実装であり、それは使用しません。ここで

実装の次の例である：

/*Lets say that we have the following array initialized, 
    k is the maximum value and n is the length of the array*/ 
int A[] = {4,5,1,3,7}; 
    k = 7; 
    n = 5; 

void Counting_sort(int A[], int k, int n) 
{ 
    /*C is the count array and B is the sorted array*/ 
    int i, j; 
    int B[n], C[k+1]; 
    for(i = 0; i <= k; i++) 
     C[i] = 0; 

    for(j = 0; j < n; j++) 
     C[ A[j] ] = C[ A[j] ] + 1; 

    for(i = 1; i < k+1; i++) 
     C[i] = C[i] + C[i-1]; 

    for(j = 0; j < n; j++) { 
     B[ C [ A [j] ] ] = A[j]; 
     C[ A[j] ] = C[ A[j]] - 1; 
    } 
    //so in this loop I must always traverse from 1 to <= n and leave the Index 0? 
    for (i = 1; i <= n; i++) 
     cout << B[i] << endl; 
} 

は、だから、僕はこれが仕事にソートをカウントするために、順番に見て良い例であれば、ソートされた配列は常になります聞いていますのよ元の配列のサイズ+ 1とインデックス0は変更されませんか？

Answer 1

実装にバグがあります。つまり、Bをサイズnに初期化しますが、アドレスB [n]に初期化します。あなたはB内のインデックス0で開始したい場合は

とにかく、あなたは変更する必要があります。

B [C [A [J]]] = A [j]を、

B [C [A [j]] - 1]〜

[j]を=。

とのため

へのループのためのあなたのその後の（I = 1; I <のn; I ++）

あなたはB内のインデックス1で開始している理由あなたがで最小の要素を配置することです配置する要素の残りの数のカウントに等しいインデックス - つまり、最も小さい要素の最後のものがインデックス1に配置されます。