Help us understand the problem. What is going on with this article?

C言語で基数ソート

More than 1 year has passed since last update.

基数ソートとは

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

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

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

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

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

直接基数法

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

qiita-sort-1.png

(比較的)理解しやすい基数法

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

qiita-sort-2.png

サンプルコード

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$回ソートすれば全体が整列できる。

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした