- 追加された行はこの色です。
- 削除された行はこの色です。
[[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)~
~