基数ソートを説明する

Question

私は基数ソートを理解しようとしています。特に、基数関数、より具体的には、jループとkループを理解することができません。私は正確に何が起きているのか分かりません。私が見ることから、jループはソートされた出力配列を形成するためにkループのインデックスを設定しているようです。誰かがそれの背後にある論理を説明するのを助けることができれば、それは素晴らしいだろう！

// RADIX SORT BEGIN // 

// Get the maximum value in arr[] 
int getMax(int arr[], int size) 
{ 
    int max = arr[0]; // Set max to presumably the first one 
    int i = 1; 
    while (i < size) 
    { 
     if (arr[i] > max) // We have a new max ladies and gents 
      max = arr[i]; 
     i++; 
    } 
    return max; 
} 

// Do a sort of arr[] based off the digit represented by exp 
void radixing(int arr[], int size, int exponent) 
{ 
    int output[size]; 
    int count[10] = {0}; 

    // Tally the amount of numbers whose LSB based off current exponent 
    // is 0-9, represented by each 
    // index in the array 
    for (int i = 0; i < size; i++) 
     count[ (arr[i]/exponent) % 10 ]++; 

    for (int j = 1; j < 10; j++) 
     count[ j ] += count [j - 1]; 

    for (int k = size - 1; k >= 0; k--) 
    { 
     output[ count[ (arr[k]/exponent) % 10 ] -1 ] = arr[k]; 
     count[ (arr[k]/exponent) % 10 ]--; 
    } 

    // Finalize output into the original array 
    for (int o = 0; o < size; o++) 
     arr[o] = output[o]; 
} 

// Main radix sort function 
void radixsort(int arr[], int size) 
{ 
    // Find the max in the array to know the number of digits to traverse 
    int max = getMax(arr, size); 

    // Begin radixing by sorting the arr[] based off every digit until max 
    // Exponent is 10^i where i starts at 0, the current digit number 
    for (int exponent = 1; (max/exponent) > 0; exponent = exponent * 10) 
     radixing(arr, size, exponent); 
} 
// RADIX SORT END // 

Answer 1

ではなく、私はそれはあなたがそれがどのように動作するかを理解するために使用できる達成するつもりで何を伝えるつもりだアルゴリズムの各ステップを打破します。これは、LSD基数ソートと呼ばれるものを実行しているように見えます。

カードソーターを使用したことがある人は（このごろ見つからない）、このアルゴリズムと同じことをします。この考え方は、最下位桁から始まり、最大限に向かって作業することです。カードソーターは、10桁のビンを1桁ごとに1つずつ持っています。列（指数部）が選択され、選択した列の桁数に応じてカードが適切なビンに分類されます。

アルゴリズムが実行しているのは、指定された指数列の各桁のレコード数を数え、その数のレコードを順番に出力することです。実際には、カウントを使用してアウトプット配列へのオフセットを計算します。

今度は、指定された列（指数）の順番でレコードを使用して、次の高い指数に移動します。

編集：多少の装飾。

Answer 2

jループは、カウントを各バケットの終了インデックス（1 +最後の要素のインデックス）に変換します。 kループは、現在の桁に基づいて要素を最後から最初のバケットに移動します。プロセスは最下位桁から始まり、最上位桁で終わります。

代わりに、最初のインデックス== 0、2番目のインデックス== '0'桁の要素数、...（9桁の要素数はありませんそれは使用されません）。ソートの基数部分は、最初から最後まで要素をソートします。

どちらの場合でも、バケットのサイズは可変で、1つのバケットの終わりが次のバケットの始まりです。基数ソート・パスが完了すると、バケット間にギャップはありません。