バケットソート
バケットソートには、大きく分けて2種類の実装がある。
まずひとつは、可変個の要素を保持できるデータ構造を使ってバケツを表現する方法である。簡単な例としては、m個の線形リストを使う実装が考えられる。直感的に理解しやすい実装だが、単純な配列だけではなく可変長のデータ構造が必要になるため、可変長のデータ構造がない言語の場合、その実装コストを考慮しておく必要がある。
もうひとつは、いったん整列対象のデータを走査して値ごとの出現回数を数えておき、それに応じてひとつの配列の中を値ごとに分割する方法である。 この実装によるバケットソートのみを指して特に分布数えソート、計数ソート(Counting Sort)などと言う。
たとえば以下の入力が与えられたとする。
昇順にソートした結果は以下のようになるはずである。
さて値ごとの出現分布を調べると、1が3個、2が5個、3が4個出現していることがわかる(ソートしなくても元のデータ列に一通りアクセスすればわかる)。出現個数がわかれば、1は結果列の1番から、2は4番から、3は9番から始まることがわかる。
Javaによるサンプルコードは以下のようになる。