ピジョンホールソート

ピジョンホールソート

クラス	ソートアルゴリズム
データ構造	配列
最悪の場合の パフォーマンス	${\displaystyle O(N+n)}$ここで、Nはキー値の範囲、nは入力サイズです。
最悪の場合の 空間複雑度	${\displaystyle O(N+n)}$
最適	もし、そして、もし、${\displaystyle N=O(n)}$

ピジョンホールソートは、要素数nとキー値の範囲の長さNがほぼ同じである要素のリストをソートするのに適したソートアルゴリズムです。 ^[1] O ( n + N ) 時間が必要です。カウンティングソートに似ていますが、「アイテムを 2 回移動します。1 回目はバケット配列に、2 回目は最終目的地に移動します。[一方、カウンティングソートは補助配列を作成し、その配列を使用して各アイテムの最終目的地を計算し、アイテムをそこに移動します。」^[2]

ピジョンホールアルゴリズムは次のように動作します。

1. ソートする値の配列が与えられた場合、最初は空の「ピジョンホール」（オフィスやデスクのピジョンホール メッセージボックスに類似）の補助配列を設定します。元の配列のキーの範囲内の各キーに対して 1 つのピジョンホールが割り当てられます。
2. 元の配列を調べて、各値をそのキーに対応するピジョンホールに配置します。これにより、各ピジョンホールには最終的にそのキーを持つすべての値のリストが含まれます。
3. ピジョンホール配列をキーの昇順で反復処理し、ピジョンホールごとにその要素を昇順で元の配列に格納します。

これらの値のペアを最初の要素で並べ替えるとします。

• （5、「こんにちは」）
• （3、「パイ」）
• （8、「リンゴ」）
• （5、「王」）

3 から 8 までの各値に対してピジョンホールを設定し、各要素をそのピジョンホールに移動します。

• 3: (3、「パイ」)
• 4:
• 5: (5、「こんにちは」)、(5、「王様」)
• 6:
• 7:
• 8: (8、「リンゴ」)

次に、ピジョンホール配列が順番に反復処理され、要素が元のリストに戻されます。

ピジョンホールソートとカウンティングソートの違いは、カウンティングソートでは補助配列に入力要素のリストが含まれず、カウントのみが含まれることです。

• 3:1
• 4:0
• 5:2
• 6:0
• 7:0
• 8:1

Nがnよりはるかに大きい配列の場合、バケット ソートは空間と時間の面でより効率的な一般化です。

• 鳩の巣原理
• 基数ソート
• バケットキュー、関連する優先キューデータ構造

Wikibookアルゴリズム実装には、ピジョンホールソートに関するページがあります。