C言語で基数ソート

基数ソートとは

キー値全体を比較せずに、キー値の一部のみを参照・比較行い整列する方法。

データの種類を特定しなければ、クイックソートが計算量$O(n\log{n})$で最速だが、

• ソート順を決めるキー値が整数
• 整数値の範囲があらかじめわかっていて、それほど大きくない

という条件のもとならば、基数ソートで計算量$O(n)$でソート可能

※ビット演算を使えるので、2進数の方が(10進数よりも)扱いやすい

直接基数法

• 右から左にビットを調べる
• 度数分布表を作成して累積度数分布表に従って並び替え
• $n$桁目でソートする場合、$n-1$桁目以下でソート済みならば、ソート可能
  • $n=1,2,\cdots,N$と繰り返して全体をソート

（比較的）理解しやすい基数法

• 上位桁から順にソート対象として、対応するバケツに入れる
• 最上位桁の区分で大まかな大小関係が決まる
• あとは各バケツごとにソート

サンプルコード

int型の配列を基数ソートを用いて整列するコード

radix_sort.c

#include<stdio.h>

/* 値を入れ替える関数 */
void swap (int *x, int *y) {
  int temp;    // 値を一時保存する変数

  temp = *x;
  *x = *y;
  *y = temp;
}

/* xをkビット右シフトし、その左iビットをとりだす */
int bits (int x, int k, int i) {
  return (x >> k) & ~(~0 << i);
}

/* 直接基数法 */
void straight_radix_sort (int array[], int array_size, int data_range) {
  int count[data_range]; // 度数分布表用の配列
  int work[array_size]; // 作業用配列
  int i, j,k;
  int w = 4, s = 4; // このサンプルでは、キー全体w=4ビットで、s=4ビットずつソートする

  for (k = 0; k < w/s; k++) { // 全体がwでsビットずつソートするので、w/s回ソート
    for (j = 0; j < data_range; j++) { count[j] = 0; } // 度数分布表初期化
    for (i = 0; i < array_size; i++) {
      count[bits(array[i], k*s, s)]++;  // 度数分布表作成
    }
    for (j = 1; j < data_range; j++) {
      count[j] += count[j-1];         // 累積度数分布表にする
    }
    for (i = array_size-1; i >= 0; i--) {
      work[count[bits(array[i], k*s, s)] - 1] = array[i]; // 分布表に従って並び替え
      count[bits(array[i], k*s, s)]--; // 分布表更新
    }
    for (i = 0; i < array_size; i++) { array[i] = work[i]; } // 作業用配列からコピー
  }
}



/* 基数ソート */
void radix_sort (int array[], int left, int right, int bit) {
  int i, j;
  if (left < right && bit >= 0) {
    i = left;
    j = right;
    do {
      while (bits(array[i], bit, 1) == 0 && (i < j)) { i++; } // 左端から探索
      while (bits(array[j], bit, 1) == 1 && (i < j)) { j--; } // 右端から探索
      if (i != j) { swap(&array[i], &array[j]); }
    } while (i != j);
    if (bits(array[right], bit, 1) == 0) { j++; }
    radix_sort(array, left, j-1, bit-1);   // 0の部分をソート
    radix_sort(array, j, right, bit-1);    // 1の部分をソート
  }
}

int main (void) {
  int array1[10] = { 2, 1, 8, 5, 4, 7, 9, 0, 6, 3 };
  int array2[10] = { 2, 1, 8, 5, 4, 7, 9, 0, 6, 3 };
  int i;

  /* 直接基数法 */
  printf("straight_radix_sort\n");
  printf("Before sort: ");
  for (i = 0; i < 10; i++) { printf("%d ", array1[i]); }
  printf("\n");

  straight_radix_sort(array1, 10, 10); // 配列、配列のサイズ、キーの値の範囲

  printf("After sort: ");
  for (i = 0; i < 10; i++) { printf("%d ", array1[i]); }
  printf("\n");

  /* 基数法 */
  printf("radix_sort\n");
  printf("Before sort: ");
  for (i = 0; i < 10; i++) { printf("%d ", array2[i]); }
  printf("\n");

  radix_sort(array2, 0, 9, 4); // 配列、左端の添え字、右端の添え字、ビット数
                               // 10 < 2^4 だからビット数は4とした

  printf("After sort: ");
  for (i = 0; i < 10; i++) { printf("%d ", array2[i]); }
  printf("\n");
  return 0;
}

実行結果

straight_radix_sort
Before sort: 2 1 8 5 4 7 9 0 6 3
After sort: 0 1 2 3 4 5 6 7 8 9
radix_sort
Before sort: 2 1 8 5 4 7 9 0 6 3
After sort: 0 1 2 3 4 5 6 7 8 9

この例では、キーの大きさが$0\sim 9$なので、全体が4ビットとしました。
本来は、キー値が$2^{31}$より小さい正整数として、radix_sort(array,1,array_size,30)みたいに使う（30=先頭のbit位置、符号bit＋31bit[0-30]=合計32bitという想定）

備考

radix_sort()関数は、キーの一桁が1ビットの前提なので、小さい数ばかりだと、上位ビットが同じで分割が効果的に機能しない。そこで、straight_radix_sort()では、キーの一桁を$s$ビットとして、全体で$w$ビットあるときに$w/s$回ソートすれば全体が整列できる。