ここでは、Haskellでバケットソート(bucket sort)を実装してみましょう。 バケットソートを知らない人は このページ を参照してください。バケットソートは、 ソートするキーの定義域が十分に小さい整数区間でないと、 ソート困難という制限がありますが、計算量が \(O(n)\) と非常に高速な安定ソートです。 Haskell によるバケットソートの実装は以下のようになります。
何だこれは、 ただのリストの内包表記じゃないかと思われるかもしれませんが、 これでバケットソートになっています。 正確には配列を使う手続き型の実装とはアルゴリズムが違いますけどね。
イメージで表現すると手続き型の配列を使うアルゴリズムが、 まずバケツを並べておいて、 ソートしたい要素を一つ一つ手に取り対応するバケツに放り込むのに対して、 上記のアルゴリズムはソートしたい要素の方を並べておいて、 まず、0 番のバケツを持って対応する要素を拾っていき、 次に、1 番のバケツを持って対応する要素を拾っていきと、 全てのバケツで繰り返します。
\(m\) = バケツの数、\(n\) = 要素数とおくと、 このアルゴリズムでは当然 \(mn\) の手間がかかるわけで、\(2n\) の手間しかかからない配列を使うアルゴリズムよりもずいぶん効率が悪いです。 しかし、それでもバケツの数が十分に少なければ、その計算量は \(O(n)\) になります。
よく、 バケツを並べるのに配列の代わりにリストを使っている人を見かけますが、 リスト上の任意の位置へのアクセスには \(O(m)\) の計算量がかかりますので、形式だけ配列版のアルゴリズムに合わせても、 その手間はおよそ \(2mn\) になります。
さて、わざわざ効率の悪いアルゴリズムを使わなくとも、 配列を用いるアルゴリズムを使えば良いのではと思うかもしれません。 もちろん、そのような実装はあります。しかし、 ちょっとだけアクロバチックでアブノーマルなんです。 それでは紹介しましょう。以下のようになります。
私は初めて accumArray という関数を知ったとき、 何に使うのかピンときませんでした。ところが、 これがバケットソートにばっちりはまるんですね。 ひょっとしたら、 バケットソートを実装するために用意された関数ではないかと思われるほどです。 accumArray 等、Haskell の配列について知らない人は このページ を参照してください。
とにかく、このコードはブッチギリに速いです。多分、 ST モナドを使って 副作用を導入するとかしない限り、 このコードに適うバケットソートはまず無いでしょう。腕に自信のある方は、 これを超えるコードに挑戦してみてください。
ところで、ここまでの説明にはウソがあります。 バケットソートは、 キーの定義域が十分小さい整数区間でないとソート困難と紹介しましたが、 BucketSort1.hs の実装を見るとそうではないことが分かります。 BucketSort1.hs の実装ではもっと一般的に拡張できます。
BucketSort1.hs の型変数 a は、ソートのはずなのに Ord のインスタンスですらありません。 (==) 演算子で等値比較さえ出来ればソートできます。では、 順序はどこからくるのかと言えば、keys リストに並べた順番で定義されます。 ただ、これはこの実装が特別なだけで、 配列を用いた実装では、 キーの定義域が十分に小さい整数区間の系列を対象とします。