鳩の巣ソート

鳩の巣ソート

クラス	ソート
データ構造	配列
最悪計算時間	${\displaystyle O(N+n)}$, N はキーのもつ値の取る範囲。 n は入力のサイズ。
最悪空間計算量	${\displaystyle O(N+n)}$

鳩の巣ソート（はとのすソート、英: pigeonhole sort）はソートアルゴリズムの一種であり、要素数 (n) とソートキーの値の個数 (N) がほぼ同じ場合に適した手法である^[1]。必要な時間計算量は Θ(n + N) である。

鳩の巣ソートは次のように動作する。

1. 初期状態で空の「鳩の巣」の配列を用意する。個々の鳩の巣にはソートキーの1つの値が対応している。それぞれの鳩の巣には、そのソートキーを持つ要素のリストを格納する。
2. 入力配列を順に見ていき、それぞれの要素を対応する鳩の巣のリストに入れていく。
3. 鳩の巣の配列を順に走査し、空でない鳩の巣にある要素を順次並べていく。

例えば、以下のような値の対を、それぞれの先頭の値をキーとしてソートする。

• (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 よりずっと大きい場合、より一般的なバケットソートの方が効率的である。

表 話 編 歴 ソート
理論	計算複雑性理論 ランダウの記号 全順序 リスト 安定性 ソーティングネットワーク 比較ソート（英語版） 整数ソート（英語版）
交換ソート	バブルソート シェーカーソート 奇偶転置ソート コムソート ノームソート クイックソート
選択ソート	選択ソート ヒープソート スムースソート デカルト木ソート トーナメントソート
挿入ソート	挿入ソート シェルソート ツリーソート 図書館ソート ペイシェンスソート
マージソート	マージソート 多層マージソート ストランドソート
非比較ソート	基数ソート バケットソート 計数ソート プロキシマップソート 鳩の巣ソート バーストソート ビーズソート
並行ソート	バイトニックソート バッチャー奇偶マージソート シェアソート
混成ソート	ティムソート イントロソート Jソート アンシャッフルソート（英語版）
その他	トポロジカルソート パンケーキソート スパゲティソート
非効率的/ ユーモラスソート	ボゴソート ストゥージソート スリープソート エラーソート
カテゴリ