バケットソート
出典: フリー百科事典『ウィキペディア（Wikipedia）』
バケットソートは、ソートのアルゴリズムの一つ。バケツソート、分布数えソート、計数ソート、ビンソートなどともいう。計算時間はO(n)と高速だが、要素の定義域分の外部記憶が必要。安定ソートが可能。
目次 |
[編集] 概念
整列したいデータの取りうる値がm種類であるとき、m個のバケツを用意しておき、値ごとに1個のバケツを対応づける。元のデータ列を走査して、各データを対応するバケツに入れていく。この処理が終わった後、整列したい順序に従ってバケツから値を取り出せば、データをソートすることができる。
安定ソートを実現するためには、同じバケツに入っているデータは入れたときと同じ順序で取り出す必要がある。順序が保存されない場合は、ソートはできるが、安定ソートではなくなる。後述するように基数ソートと組み合わせて使うためには、安定ソートになっている必要がある。
[編集] 実装
バケットソートには、大きく分けて2種類の実装がある。
まずひとつは、可変個の要素を保持できるデータ構造を使ってバケツを表現する方法である。簡単な例としては、m個の線形リストを使う実装が考えられる。直感的に理解しやすい実装だが、単純な配列だけではなく可変長のデータ構造が必要になるため、可変長のデータ構造がない言語の場合、その実装コストを考慮しておく必要がある。
もうひとつは、いったん整列対象のデータを走査して値ごとの出現回数を数えておき、それに応じてひとつの配列の中を値ごとに分割する方法である。 後者の実装によるバケットソートのみを指して特に分布数えソートと言う。
例えば以下の入力が与えられたとする。
3 2 2 1 2 2 1 3 3 1 2 3
昇順にソートした結果は以下のようになるはずである。
1 1 1 2 2 2 2 2 3 3 3 3
さて値ごとの出現分布を調べると、1が3個、2が5個、3が4個出現していることがわかる（ソートしなくても元のデータ列に一通りアクセスすればわかる）。出現個数がわかれば、1は結果列の1番から、2は4番から、3は9番から始まることがわかる。
Javaによるサンプルコードは以下のようになる。
/**
* 配列 src 内をバケットソートして配列 dst にコピーする。
* @param src ソート対象となるデータの配列。
* @param dst ソート結果を書き込む配列。
* @param len ソート対象となるデータの個数。src および dst の長さ以下であること。
* @param range とり得る値の範囲。対象の各データは 0 以上 range 未満の値をとる。
*/
public static void bucketsort(int[] src, int[] dst, int len, int range) {
/** 値ごとの出現回数 */
int[] count = new int[range];
/** ソート後配列における値ごとの開始位置 */
int[] offset = new int[range];
/** ループ制御用 */
int i;
/* 出現回数を数える */
for (i = 0; i < len; i++)
count[src[i]]++;
/* 開始位置計算 */
offset[0] = 0;
for (i = 1; i < range; i++)
offset[i] = offset[i-1] + count[i-1];
/* ソート処理 */
for (i = 0; i < len; i++) {
int target = src[i];
dst[offset[target]] = target;
offset[target]++;
}
}
[編集] 利点と欠点
多くのソートアルゴリズムの計算量がO(nlogn)である中、O(n)を実現でき、多数のデータを高速に処理できることが利点である。
欠点は、取りうる値の種類mに対応するバケツが必要な点である。仮にキーが32ビット整数という以外に事前情報がないデータ列をソートする場合、約43億個のバケツが必要にある。長さに制限のない可変長の文字列の場合は、もはや有限個のバケツでは対応できない。この欠点は、基数ソートと組み合わせることで回避できる場合もある。
