基数ソート

C.S.R. Wiki トップページ

基数ソート †

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

アルゴリズム †

(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-基数ソートより抜粋)

プログラム †

//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;
  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型にも対応できる

実行速度 †

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