サイトマップ / Ｃ言語講座＞出入り口＞総目次＞目次：ソート＞ビンソート
/* 今日はビンソートについて、学びます。ビン ( bin ) とは、”セサミストリート”でよく見かけるゴミなどを入れておく大きな容器のことです。
ビンソートは、整数の配列で、かつ、配列の要素の値の取る範囲が、前もってわかっている時にしか使えません。例えば、要素数が4０で、０から９９までの正の整数を取る配列、x[ ] があるとします。値は互いに等しくないとします。
作業用の配列として、要素が１００の int 型の配列を用意します。この配列が、ビンソートにおけるデータを一時的にしまう"ビン" になります。Bin[ ] の各要素は、０ に初期化しておきます (注１、２) 。
x[ ] の要素を順番に読んで、Bin[ その値 ] を１インクリメントします。この作業を全ての x[ ] の要素について行った後、Bin[ ] の要素を順番に読んで、Bin[ ] の値が０でなければ、x[ ] に書き戻します。
ビンソートは、ソート対象のデータに制約がありますが、データのばらつきかたに影響されない、高速なソートです。
注１：データがないという意味で、- 1 に初期化する場合もあります。
注２：Bin[ ] は外部変数なので、コンパイル時に、０に初期化されてますが、ビンソートを複数回呼び出すような変更を予想して、呼び出される度に初期化したほうが、安全でしょう。
*/
#include <stdio.h>
#define MAX_DATA 100
int Bin[MAX_DATA]; /* 作業用配列 */
void BinSort(int x[ ], int n);
void ShowData(int x[ ], int n);
void main(void);
/* ビンソートを行う */
void BinSort(int x[ ], int n)
{
int i, j;
if (n > MAX_DATA) {
printf("データが多すぎます!\n");
return;
}
else {
for (i = 0; i < MAX_DATA; i++)
Bin[i] = 0; /* 作業用配列の初期化 */
for (i = 0; i < n; i++) /* x[i] の値の */
Bin[x[i]]++; /* Bin[ ] の要素の値を */
/* インクリメント */
j = 0; /* x[ ] の添字として使用 */
for (i = 0; i < MAX_DATA ; i++)
if (Bin[i]) /* ０でなければ */
x[j++] = i; /* 書き戻す */
}
}
/* n 個のデータを表示する */
void ShowData(int x[ ], int n)
{
int i;
for (i = 0; i < n ; i++)
printf("%d\t", x[i]);
}
void main(void)
{
/* ソートするデータ */
int x[MAX_DATA] = {89, 1, 78, 58, 48, 18, 9, 21, 56, 11,
62, 23, 38, 96, 4, 45, 73,14, 30, 27,
6, 35, 2, 25, 69, 41, 8, 51, 0, 32,
98, 12, 33, 72, 19, 52, 28, 86, 17, 99
};
int n = 40; /* ソートするデータの数 */
/* ソート前のデータを表示 */
printf("ソート前:\n");
ShowData(x, n);
printf("\n");
BinSort(x, n);
/* ソート後のデータを表示 */
printf("\n\nAソート後:\n");
ShowData(x, n);
}
|
/* ビンソートの欠点として、配列の取りうる値の範囲が広いと、メモリ効率が悪くなり、更に広いと、作業用の配列を事実上取れなくなります。例えば、０から100,000 までの値を取りうる、要素数 10 の配列のソートなどが、これに当たります。
実は、以前に、ビンソートの文字版について学んでいます( ファイル中の英文字の出現頻度を調べる ) 。これは char のサイズの数の要素を持った配列を用意して、ファイルの中で現れるアルファベットの値を添字として使い、その配列の要素をインクリメントして、アルファベットの出現頻度を調べるプログラムです。 */
/* (C) 2000- ＹＦプロ. All Rights Reserved. */ 提供：Ｃ言語講座−それ自体コンパイルできる教材を使った講座です−