バケットソート

テンプレート:Infobox algorithm バケットソートは、ソートのアルゴリズムの一つ。バケツソート、分布数えソート、計数ソート、ビンソートなどともいう。オーダーはO(n)と高速だが、一般的なソートとは異なり、ソート対象が全順序というだけではなく「取りうる値がm種類である」というような、より強い制限を前提としている非比較ソートに分類される一つである（あるいは事前にスキャンして分布を調べるなど、モディファイを追加する必要がある）。

概念

バケットソートの概念

整列したいデータの取りうる値が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億個のバケツが必要になる。長さに制限のない可変長の文字列の場合は、もはや有限個のバケツでは対応できない。この欠点は、基数ソートと組み合わせることで回避できる場合もある。

スリープソート

バケットソートのバケツをメモリ空間の代わりに時間に置き換えたものである。 そのままの実装では要素の最大値の時間が経過するまで待つ必要があるので実用性はない。

bashによる実装

#!/bin/bash
function f() {
    sleep "$1"
    echo "$1"
}
while [ -n "$1" ]
do
    f "$1" &
    shift
done
wait

example usage:
./sleepsort.bash 5 3 6 3 6 3 1 4 7

関連項目

• 基数ソート
• 鳩の巣ソート

外部リンク

• バケットソートコードテンプレート:リンク切れ