バケットソート

バケットソート

クラス	ソート
データ構造	配列
最悪計算時間	$O(n^{2})$
最良計算時間	$O(n)$
平均計算時間	$O(n+k)$
最悪空間計算量	$O(n\cdot k)$

バケットソート（英: bucket sort）は、ソートのアルゴリズムの一つ。バケツソート、ビンソート（英: bin sort）などともいう。バケツ数 k 個使った場合、オーダーはO(n + k)となり、ソートする要素数nとk を無関係にできる場合線形時間ソートとなるが、要素間の全順序関係を用いるソートとは異なり、キーの取りうる値がk種類である、という入力により強い制限を要求するソートである。

概念

バケットソートの概念

整列したいデータの取りうる値がm種類であるとき、m個のバケツを用意しておき、値ごとに1個のバケツを対応づける。元のデータ列を走査して、各データを対応するバケツに入れていく。この処理が終わった後、整列したい順序に従ってバケツから値を取り出せば、データをソートすることができる。

安定ソートを実現するためには、同じバケツに入っているデータは入れたときと同じ順序で取り出す必要がある。順序が保存されない場合は、ソートはできるが、安定ソートではなくなる。後述するように基数ソートと組み合わせて使うためには、安定ソートになっている必要がある。

実装

バケットソートには、大きく分けて2種類の実装がある。

まずひとつは、可変個の要素を保持できるデータ構造を使ってバケツを表現する方法である。簡単な例としては、m個の線形リストを使う実装が考えられる。直感的に理解しやすい実装だが、単純な配列だけではなく可変長のデータ構造が必要になるため、可変長のデータ構造がない言語の場合、その実装コストを考慮しておく必要がある。

もうひとつは、いったん整列対象のデータを走査して値ごとの出現回数を数えておき、それに応じてひとつの配列の中を値ごとに分割する方法である。 この実装によるバケットソートのみを指して特に分布数えソート、計数ソート(Counting Sort)などと言う。

たとえば以下の入力が与えられたとする。

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]++;
    }
}

バケットソートの分割統治

仮に32ビット整数をソートする場合に、約43億個のバケツを持つことは非現実的である。 バケツは1つの値に対して1つのバケツを用意する必要はなく、範囲を持ったバケツが矛盾なくソートされていれば良い。 この時、各バケツの中身は別ソートアルゴリズムでソートしてやるか、再度バケットソートを適用する必要がある。

冒頭の32ビット整数を1ビットずつ再帰的にバケットソートすると、32階層のバケットソートが必要になる。 これは約43億個に対してのlogであり、バケットソートもまたlogのオーダーから抜け出せていないことが分かる。 （2ビットずつ処理しても4ビットずつ処理しても、やはりlogは消えない。）

通常、各値の取りうる範囲よりも、ソートすべき配列サイズの方が小さいため、バケットソートはO(nlogn)ソートよりも実質低速であることが多い。

また、文字列に対しても、頭から1文字ずつ再帰的にバケットソートを行うことができる。 32ビット整数のソートは、長さ32の1ビット文字からなる文字列をソートしているとみなすこともできる。

利点と欠点

計算量の種明かしは「バケットソートの分割統治」の項で行ったとおりで、利点とはなっていない。

比較を行なわずにソートできる点は利点となる。

しかしながら、その裏返しとして、ソート対象の値のモデルに合わせてプログラムを書く必要が生じてしまう。

スリープソート

バケットソートのバケツをメモリ空間の代わりに時間に置き換えたもので、もともと掲示板4chanに投稿されたアイデアである。

「全要素の最大値×スリープさせる単位時間」で実際にソートできてしまう。それが役に立つ事例は例題程度であろう。

面白いジョークであるが、実際のコンピュータシステムでは、起動したプロセスが意図した時間にピタリと正確に終了するという保証はない。すなわち、非同期に複数プロセスを起動したとき、混雑やOSの制御のために値が返ってくる順序が意図した時刻にこないことがあるのはもちろん、ソートで期待する順序とは異なった順序で返ってくる恐れさえある。したがって、デモや冗談ならともかく、実用には絶対使ってはいけない。

OSは、実は一定時間後に起動する要求を到来時間順の待ち行列につないで管理している。そのとき当然到来時間の大小比較が行われる。タイマで見張り、時間の到来した要求を行列から外して要求元の待ちを解除し結果を通知しているのが実体である。ソートアルゴリズムに不可欠のこの“計算”のコストが計算量に算入されていないので、一見計算が要らないように見えるというトリックがある。時間順に並んだ「バケツ」を用意してデータを出し入れしてくれている“裏方さん”がいるのである。

bashによる実装

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

使用例:

$ ./sleepsort.bash 5 3 6 3 6 3 1 4 7
1
3
3
3
4
5
6
6
7

上の結果は正しい。

ところが処理系（Windows 10, Cygwin bash）で何度か実行しただけで、通常の数倍の時間経過したあと、たとえば以下のように一部追い抜きがあったり入力順そのままだったりと、誤った結果が出てくる例が見られた。

$ ./sleepsort.bash 5 3 6 3 6 3 1 4 7
3
5
6
3
3
6
1
4
7