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

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

More than 1 year has passed since last update.

分布数え上げソートとは

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

手順

以下、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点
    2. 累積度数分布表の3を見る$\to$5
    3. 作業用配列(配列$a$と同サイズ)の前から5番目に8番の学生のデータを格納
    4. 累積度数分布表の3の値を1減らす($5\to 4$)
    5. 続いて、7番の学生の点数は1点
    6. 累積度数分布表の1を見る$\to$2
    7. 作業用配列の前から2番目に7番の学生のデータを格納
    8. 累積度数分布表の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

性能

  • ソート対象のキーの範囲が既知でないといけない
  • 作業領域が必要
    • 分布表用の配列、コピー用の配列
  • データの比較を行わないので高速
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
ユーザーは見つかりませんでした