鳩の巣ソート

鳩の巣ソート（はとのすソート、）はソートアルゴリズムの一種であり、要素数 ("n") とソートキーの値の個数 ("N") がほぼ同じ場合に適した手法である。必要な時間計算量は Θ("n" + "N") である。
概要.
鳩の巣ソートは次のように動作する。
例えば、以下のような値の対を、それぞれの先頭の値をキーとしてソートする。
キーの値は3から8なので、それぞれについて鳩の巣を設定し、各要素を鳩の巣に移動する。
次に鳩の巣の配列を順次走査し、出現順に元の配列に戻していけばよい。
バケットソートに似ているが、バケットソートでは補助配列にはキーごとの要素数のみを格納し、要素そのものは格納しない。上の例では、次のようになる。
この情報を使うと、ソートキーの値を見ただけでソート後の位置を示すことができる。
"N" が "n" よりずっと大きい場合、より一般的なバケットソートの方が効率的である。