『アルゴリズム導論』8.3基数ソート

基数ソート:古いカードリーダーに使用されるアルゴリズムです.1枚のカードは80列あり、各列は12位置のいずれかで穿孔することができる.並べ替え器は機械的に「プログラム化」されて、1枚のカードの各列を検査し、穿孔の位置に応じて12の例に分けることができる.これにより、オペレータは、1番目の位置が最も上に穿孔され、2番目の位置が穴を穿孔された次など、1つずつ収集することができる.
10進数の場合、シリーズでは10個の位置しか使用されません.1つのdビット数がd列を占有する.カードソート器は一度に1つの列しか表示できないため、n枚のカードのd倍数をソートするにはソートアルゴリズムが必要です.
基数ソートアルゴリズムのコードは直感的である.次のプロセスでは、長さnの配列Aにおいて、各要素にはdビット数があり、そのうち第1ビットは最低ビットであり、第dビットは最高ビットであると仮定する.
RADIX-SORT(A, d)

 for i ← 1 to d
     do use a stable sort to sort array A on digit i

 
C++実装では、プログラムが並べ替えられる数値の桁数を同じにする必要がなく、より大きな適用範囲を持つように、補助関数int maxDigit(int*arr,int digit)を使用して、並べ替えられる配列の中で最大の数桁を計算しました.
基数ソートのアルゴリズムは直感的である.1つの配列では、各要素にdビット数があり、そのうち1番目は最低ビット、d番目は最高ビットである.各位置のソートを順番に判断します.基数ソートには、別の安定したソートアルゴリズム(stable sort)が必要である.

#include <iostream>
 
 using namespace std;
 
 //           
 int maxDigit(int* arr,int digit)
 {
     int n = 0;
     int* temp = new int[digit];
     for(int i = 0; i < digit; i++)
         temp[i]= arr[i];
     for(int i = 0; i < digit; i++)
     {
         int counter =1;
         while(temp[i] / 10 > 0)
         {
             counter++;
             temp[i] /= 10;
         }
         if(n < counter)
             n = counter;//      。
     }
     delete[] temp;
     return n;
 }
 
 //    
 void radixSort(int* arr, int digit)
 {
     int n = maxDigit(arr, digit);
     int* temp = new int[digit];
     int* count = new int[10];
     int i, j, k;
     int radix = 1;
     for(i = 1; i <= n; i++)
     {
         for(j = 0; j < 10; j++)
             count[j] = 0;
         for(j = 0; j < digit; j++)
         {
             k = (arr[j] / radix) % 10;
             count[k]++;
         }
         for(j = 1; j < 10; j++)//                  。。    。。。             	
         count[j] = count[j-1] + count[j];
         for(j = digit - 1; j >= 0; j--)
         {
             k = (arr[j] / radix) % 10;
             count[k]--;
             temp[count[k]] = arr[j];
         }
         for(j = 0; j < digit; j++)
             arr[j] = temp[j];
         radix *= 10;
     }
     delete[] temp;
     delete[] count;
 }
 
 int main()
 {
     int a[] = {22, 34, 95, 87, 56, 980, 12, 48};
     radixSort(a, 8);
     for(int i = 0; i < 8; i++)
     {
         cout << a[i] << " ";
     }
     cout << endl;
     return 0;
 }