バケットソートとは (バケットソートとは) [単語記事]

バケットソートはソートアルゴリズムの一種。

ここで言うバケットはいわゆるバケツのこと。同じ意味でビンソートと呼んだりする。バリエーションが多すぎるため名称が少々混乱しているが、本来バケットソートと呼ぶべき考え方はかなりアブストラクトな部分である。日本語ナニ pediaの記述はちょっと怪しい。度数ソートや分布数え上げソートなどもバケットソート系だが一応別物。

使うためには、配列内の値の種類がある程度限定できて、どのような値が含まれるか事前に分かっていなければならないという条件がつくものの、平均計算時間O(n+k) (k≒値の種類)を叩き出せる特殊な高速ソートとして知られる。基本的には安定ソート。

原理

値の種類の数だけ入れ物を用意する
それぞれの値を自分の種類に応じた入れ物に移す
入れ物は最初から順番通りに並んでいるので、先頭から取り出せばできあがり

トランプのカードを並び替える時、スートや数字別にカードを配って最後に束ねるやり方といえば分かりやすいだろう。

入れ物内の順序に関してはまた別に考える必要があり、典型的な実装では挿入ソートを使うが、大きさによってクイックソートだったりマージソートだったりするかもしれない。種類だけ揃えればいいならここで終了。

性能検討

移動先を種類によって最初から決め打ちできるので、他の値との前後関係を調べなくてよいというのがミソ。他の要素の存在に左右されないので完全に線形時間で分類できる。データ構造的にはハッシュテーブルの動きに近い。

最初に書いた通り、値の種類がそれほど多くない時に真価を発揮する。理屈上は整数一般で分類するような形でも使えなくはないものの、例えば32b it=4,294,967,296個のバケツ用意すんのかよ！という話になるので実用にはならないわけである。まあ分類が大雑把すぎてもバケツで割る効果が出ないので、バケ死せず、かつ下位ソートに負担が掛からない程度に割れてくれるのが理想形である。

弱点はバケツの保存スペースが大きいことと、分布が悪いとバケツ内の並び替えで性能悪化すること。挿入ソートを併用する基本形だとすれば、すべての値が一つのバケツに集中したらただの挿入ソートになってしまうので、わざわざバケツを用意するメリットはゼロである。この辺りはクイックソートと同じく均等な配分になることが望ましく、配列内の値の分布状態が正しく分かっている程有利という、バケットソートならではの特性となっている。