鳩の巣ソートのソースを表示

{{Infobox algorithm
|class=[[ソート]]
|image=
|data=[[配列]]
|time=<math>O(N+n)</math>, ''N'' はキーのもつ値の取る範囲。 ''n'' は入力のサイズ。 
|space=<math>O(N+n)</math>
|optimal=If and only if <math>N=O(n)</math>
}}
'''鳩の巣ソート'''（はとのすソート、{{lang-en-short|pigeonhole sort}}）は[[ソート]][[アルゴリズム]]の一種であり、要素数 (''n'') とソートキーの値の個数 (''N'') がほぼ同じ場合に適した手法である<ref>[http://www.nist.gov/dads/HTML/pigeonholeSort.html NIST's Dictionary of Algorithms and Data Structures: pigeonhole sort]</ref>。必要な時間計算量は [[ランダウの記号|Θ]](''n'' + ''N'') である。

== 概要 ==
鳩の巣ソートは次のように動作する。
# 初期状態で空の「鳩の巣」の配列を用意する。個々の鳩の巣にはソートキーの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'' よりずっと大きい場合、より一般的な[[バケットソート]]の方が効率的である。

== 脚注 ==
{{Reflist}}

{{ソート}}
{{DEFAULTSORT:はとのすそと}}
[[Category:ソート]]

[[ru:Сортировка подсчётом#Алгоритм со списком]]