基数ソート。配列が最後まで横断するのはなぜですか？

Question

void countingsort(int arr[], int n, int exp) 
{ 

    int count[10] = {0}; 
    int* output = new int[n]; 
    for (int i = 0; i < n; i++) 
     count[(arr[i]/exp) % 10]++; 
    for (int i = 1; i < 10; i++) 
     count[i] += count[i - 1]; 

    for (int i = n - 1; i >= 0; i--)//Why is array traversed from end? 
    { 
     output[count[(arr[i]/exp) % 10] - 1] = arr[i]; 
     count[(arr[i]/exp) % 10]--; 
    } 
    for (int i = 0; i < n; i++) 
     arr[i] = output[i]; 
} 

void radixsort(int arr[], int n) 
{ 
    int m = getMax(arr, n); 
    for (int exp = 1; m/exp > 0; exp *= 10) 
     countingsort(arr, n, exp); 
} 

カウントソート機能では、なぜカウント配列が最後からトラバースされているのかわかりません。私たちが最初からそれを横断すれば、それはどのような違いになりますか？

Answer 1

カウントは終了インデックスに変換されるため、配列は後方にトラバースされます。カウントが開始インデックスに変換され、配列が前方に横断される例：

void countingsort(int arr[], int n, int exp) 
{ 
    int count[10] = {0}; 
    int* output = new int[n]; 
    for (int i = 0; i < n; i++) 
     count[(arr[i]/exp) % 10]++; 
    int sum = 0, tmp;    // convert counts to starting indices 
    for (int i = 0; i < 10; i++){ 
     tmp = count[i]; 
     count[i] = sum; 
     sum += tmp; 
    } 

    for (int i = 0; i < n ; i++) // traverse from beginning 
    { 
     output[count[(arr[i]/exp) % 10]] = arr[i]; 
     count[(arr[i]/exp) % 10]++; // -- => ++ 
    } 
    for (int i = 0; i < n; i++) 
     arr[i] = output[i]; 
    delete[] output; 
} 

Answer 2

あなたはそれをカウントした後に位置

..., u, ..., v, ..., w, ... 

で発生している特定のキーKのために、あなたはこれらのことを判断すると言います、要素は、位置

..., count[K]-2, count[K]-1, count[K], ... 

に行くと、あなたは順番count[K]に保存し、count[K]-1、は（それがcountingsortへの以前の呼び出しによって確立された順序を、保持する）安定で、ご注文wの要素を格納する必要性を得るために

、v、u、すなわちトラバースしなければなりません配列を後方に移動します。