鳩の巣ソート

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索
鳩の巣ソート
クラス ソート
データ構造 配列
最悪計算時間 O(N+n), N はキーのもつ値の取る範囲。 n は入力のサイズ。
最悪空間計算量 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

この情報を使うと、ソートキーの値を見ただけでソート後の位置を示すことができる。

Nn よりずっと大きい場合、より一般的なバケットソートの方が効率的である。

脚注[編集]