ビンソート(bin sort)

上の 2つは, 大小関係を判定して並べ変える事により整列が進みます. これに対してビンソートは, データの性質に注目して並べ変える事なしに 整列を実行します. ここで扱われる例のデータの値は, 0から99の間にある事を利用して, 0から99の空の壷(bin)を用意します.

整列過程で時間を使うのは, 比較と入れ換えの2つの操作ですが, ビンソートではそれをやりません. 元の配列を順に読んで行き, 壷のその値の位置に値が存在するという印を付けて行きます. これが終ると, 今度は壷の方を読んで行き, 上で付けた印の ある所だけを出力すれば整列完了です.

このことの拡張として, 度数分布ソートがあります. 例のデータでは, 値の重複がありませんが, 値の重複がある場合に 重複度を記録して行けば, 同じ理屈でソートが完了します.

ビンソートの計算量は, $n$ のオーダーです. したがって, 上の 2つから比べると, とても効率の良いアルゴリズムです. ただし, ビンソートではそのやり方から, データが特定の範囲に 存在する事が要求されます. 現実問題として良く起こる, 不定長文字配列の整列などに使う事はできません. アルゴリズム上, 入力データの数倍の記憶領域を要求しますから, 入力データが大きくなると, ソートのための計算機資源の確保が できなくなります.

次がビンソートの例です.

/* File name 13-3.c */

#include <stdio.h>
#define SIZE 20
#define BINSIZE 100

int data[SIZE]= {99,73,20,32,34,5,64,97,25,12,83,9,21,40,3,44,69,15,58,75};

main()
{
       int bin[BINSIZE];
       int i;
       memset(bin, 0, sizeof(bin));


       for (i=0; i< SIZE; i++){
              bin[data[i]] = 1;
       }

       for (i=0; i< BINSIZE; i++){
              if (bin[i] == 1)
                     printf("%d ", i);
       }
       printf("\n");
}