基数ソートの変更点

追加された行はこの色です。
削除された行はこの色です。
基数ソートへ行く。
基数ソートの差分を削除
[[C.S.R. Wiki トップページ]]

*基数ソート [#wdbfbebe]
基数ソートは、ソートのアルゴリズムの一つ。計算時間はO(nk)と高速で、かつ安定ソートであるが、O(n)の外部記憶（高速なメモリーでなくてもよい）が必要。（ここで、nはデータの数、kはキーの桁数を意味する。）

**アルゴリズム [#dc828555]
(1)入力の数列は、いくつかのキーに分類する。例えば、3桁の数字であれば、1の位・10の位・100の位に分けて分類する。~
(2)それぞれのキーについて、下位のキーからソートする。~
~
たとえば、~
 170, 45, 75, 90, 2, 24, 802, 66
という数列を1の位についてソートすると、~
 170, 90, 2, 802, 24, 45, 75, 66
となる。さらに、10の位についてソートすると、~
 2, 802, 24, 45, 66, 170, 75, 90
となる。最後に、100の位についてソートすると、~
 2, 24, 45, 66, 75, 90, 170, 802
となり、ソートが完了する。~
~
(Wikipedia-基数ソートより抜粋)
~
**プログラム [#m66e7da7]

 //a[]:整列前配列,work[]:作業領域,n:要素数,bit:基数=2^bit
 void radixsort(unsigned long long a[], unsigned long long work[], int n, int bit)
 {
   int i, shift, range = 1 << bit;//range=2の基数乗
   int i, shift, range = 1 << bit;
   int *count;
   unsigned long long mask = range - 1;
   unsigned long long *a_save = a, *tmp;
   count = (int *)malloc(range * sizeof(int));
 
   for(shift = 0; 0xffffffffffffffff > pow(2.0, bit*shift) ; shift ++){
     for(i = 0; i < range; i++) count[i] = 0;
     for(i = 0; i < n; i++) count[(a_save[i] >> (bit*shift)) & mask]++;
     for(i = 1; i < range; i++) count[i] += count[i - 1];
     for(i = n - 1; i >= 0; i--) work[--count[(a_save[i] >> (bit*shift)) & mask]] = a_save[i];
     tmp = work;
     work = a_save;
     a_save = tmp;
   }
   for( i = 0 ; i < n ; i ++)a[i] = a_save[i];
   free(count);
 }

IEEEフォーマットの場合、double a,b が a > b > 0 であれば *(long long*)&a > *(long long*)&b となるため、引数を与える時にキャストを行えばdouble型にも対応できる

**実行速度 [#ybd6fac1]
bit=5, n=20000000で要素がすべてランダムに与えられている場合 1.098657(s)でソートが完了~
要素数が50以下で挿入ソートに切り替えるクイックソートでは 1.968452(s)~
標準C++ライブラリ <algorithm> の std::sort では1.92701(s)~
~
基数ソート の変更点

基数ソートの変更点
