C言語で分布数え上げソート

分布数え上げソートとは

比較を行わなずに、データを整列する方法

手順

以下、10点満点のテストを例にして説明

• 9人の学生の点数は次の通り：次の表を配列$a$とする

学生	0	1	2	3	4	5	6	7	8
点数	5	7	0	2	4	10	3	1	3

• 上表をもとに、度数分布表を作成：各点数の学生が何人いるか

度数分布表	0	1	2	3	4	5	6	7	8	9	10
	1	1	1	2	1	1	0	1	0	0	1

• 累積度数分布表を作成：0点からその点数までに何人の学生がいるか

累積度数分布表	0	1	2	3	4	5	6	7	8	9	10
	1	2	3	5	6	7	7	8	8	8	9

• 配列$a$の末尾から走査し、ソート済み配列を作成する：累積数=格納場所
  1. 配列$a$の末尾=8番の学生の点数は3点
  • 累積度数分布表の3を見る$\to$5
  • 作業用配列（配列$a$と同サイズ）の前から5番目に8番の学生のデータを格納
  • 累積度数分布表の3の値を1減らす（$5\to 4$）
  • 続いて、7番の学生の点数は1点
  • 累積度数分布表の1を見る$\to$2
  • 作業用配列の前から2番目に7番の学生のデータを格納
  • 累積度数分布表の1の値を1減らす（$2\to 1$）

作業用配列	0	1	2	3	4	5	6	7	8
					3

作業用配列	0	1	2	3	4	5	6	7	8
		1			3

• 繰り返して最終的に次のような配列ができる

作業用配列	0	1	2	3	4	5	6	7	8
	0	1	2	3	3	4	5	7	10

サンプルコード

int型の配列を、分布数え上げソートを用いて整列するプログラム

distribution_counting.c

# include<stdio.h>

/* 分布数え上げソート */
void distribution_counting (int array[], int array_size, int data_size) {
  int i, j;
  int count[data_size]; // 度数分布表用の配列
  int work[array_size]; // 作業用配列

  for (j = 0; j < data_size; j++) { count[j] = 0; }   // 分布表初期化
  for (i = 0; i < array_size; i++ ) { count[array[i]]++; }   // 度数分布表作成
  for (j = 1; j < data_size; j++) { count[j] += count[j-1]; }   // 累積度数分布表にする
  for (i = array_size -1; i >= 0; i--) {
    work[count[array[i]]-1] = array[i];   // 度数分布表に従って並び替え
    count[array[i]]--;   // 分布表更新
  }
  for (i = 0; i < array_size; i++) { array[i] = work[i]; }  // 作業用配列からコピー
}

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

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

  distribution_counting(array, 10, 10);

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

  return 0;
}

実行結果

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

性能

• ソート対象のキーの範囲が既知でないといけない
• 作業領域が必要
  • 分布表用の配列、コピー用の配列
• データの比較を行わないので高速