鳩の巣ソート
鳩の巣ソートは次のように動作する。
初期状態で空の「鳩の巣」の配列を用意する。個々の鳩の巣にはソートキーの1つの値が対応している。それぞれの鳩の巣には、そのソートキーを持つ要素のリストを格納する。
入力配列を順に見ていき、それぞれの要素を対応する鳩の巣のリストに入れていく。
鳩の巣の配列を順に走査し、空でない鳩の巣にある要素を順次並べていく。
例えば、以下のような値の対を、それぞれの先頭の値をキーとしてソートする。
(5, "hello")
(3, "pie")
(8, "apple")
(5, "king")
キーの値は3から8なので、それぞれについて鳩の巣を設定し、各要素を鳩の巣に移動する。
3: (3, "pie")
4:
5: (5, "hello"), (5, "king")
6:
7:
8: (8, "apple")
次に鳩の巣の配列を順次走査し、出現順に元の配列に戻していけばよい。
バケットソートに似ているが、バケットソートでは補助配列にはキーごとの要素数のみを格納し、要素そのものは格納しない。上の例では、次のようになる。
3: 1
4: 0
5: 2
6: 0
7: 0
8: 1
この情報を使うと、ソートキーの値を見ただけでソート後の位置を示すことができる。
N が n よりずっと大きい場合、より一般的なバケットソートの方が効率的である。