ピジョンホールソートとは？仕組み・擬似コード・計算量・実践での使いどころ解説

2025年11月20日 最終更新日時 : 2025年11月20日 エバープレイ編集部

ピジョンホールソートとは

ピジョンホールソート（pigeonhole sort）は、与えられた要素のキーが比較的狭い範囲（レンジ）に収まる場合に非常に効率的に動作するソートアルゴリズムです。名前は「ハトの巣（pigeonhole）」の原理に由来し、各キー値に対応する「穴（pigeonhole）」を用意して要素を格納し、最後に穴を順番に取り出してソート済み配列を作るという手順で動作します。別名ではバケットソートの特殊ケースとして扱われることもありますが、ピジョンホールソートは各整数値に1対1で穴を割り当てるのが特徴です。

基本的なアイデアと手順

  • 最小値 min と最大値 max を調べ、必要な穴の数 range = max − min + 1 を決定する。
  • range 個の穴（通常は配列、各穴はカウントまたはリスト）を用意する。
  • 入力配列の各要素を走査し、要素のキーに対応する穴へ移動またはカウントをインクリメントする（負数を扱う場合はオフセットとして min を引く）。
  • 穴を小さいキー順に走査し、穴に入っている要素を（元の順序を保持しつつ）出力配列へ書き出す。

擬似コード（典型的な実装）

function pigeonholeSort(A):
    minVal = min(A)
    maxVal = max(A)
    range = maxVal - minVal + 1

    // 各穴にリストを置く(安定化のため)
    holes = array of empty lists of size range

    for x in A:
        holes[x - minVal].append(x)

    result = empty array
    for i from 0 to range-1:
        for x in holes[i]:
            result.append(x)

    return result

上の実装では各穴はリストで、入力順にappendするため安定性（同一キー間で元の順序が保たれる）が保たれます。簡易版では各穴を整数カウントだけで持ち、後でキーを繰り返し出力する実装もありますが、その場合は安定性が失われるか別途工夫が必要です。

計算量解析

  • 時間計算量: O(n + range)。ここで n は要素数、range は max − min + 1。range が O(n) であれば線形時間 O(n) で動作します。
  • 空間計算量: O(range + n)（穴の合計サイズと要素格納用）。典型的には range 個のデータ構造（配列やリスト）を確保するため、range が大きいとメモリ消費が激しくなります。
  • 最良/平均/最悪: 上記の O(n + range) が基本で、range に依存するため range が大きいと非現実的になります。

比較ソートとの関係

ピジョンホールソートは比較ソートではありません。比較ベースのソートは情報理論的下限である Ω(n log n) を超えることはできませんが、ピジョンホールソートはキーのドメインが限定されている前提（多くの情報があらかじめ与えられている）により、線形時間でのソートが可能になります。したがって、用途に応じて比較ソートではなく非比較ソート（例: counting sort、radix sort、bucket sort、pigeonhole sort）を選ぶと良いケースがあります。

安定性について

ピジョンホールソートは実装次第で安定にも不安定にもなり得ます。各穴にリスト（配列や連結リスト）を用意して要素を入力順に追加し、その順序で出力すれば安定です。一方で、各穴に単にカウント（個数）を置き、後でキー値を繰り返して書き出すだけでは元の順序情報が失われ安定ではありません。

利点と短所（実用面）

  • 利点
    • range が狭く、range = O(n) の場合は非常に高速（O(n)）に動作する。
    • 実装が単純で分かりやすい。
    • 安定な実装が容易（穴にリストを使う）。
  • 短所
    • range が大きいとメモリを大量に消費し現実的でない（例えば range が数百万〜数十億になると不適切）。
    • 整数キーやマッピング可能なキーに限定される（浮動小数点や複合キーは前処理が必要）。
    • 空の穴を全て巡るため、range が大きく要素が散らばる場合は時間的にも非効率。

実用上の工夫と変形

  • 負の値の取り扱い：min を引くことでオフセットを取り、インデックスを非負にする。
  • メモリ節約：穴に固定長のカウントだけ置いておき後で要素を再走査して出力する方法（ただし安定性を失う）。
  • スパースなキー集合：range が広くスパースな場合はハッシュマップでキー→リストのマッピングを行う（要素数 n に対して期待 O(n) の時間）。ただしハッシュのオーバーヘッドや順序保証の問題がある。
  • 浮動小数点や文字列キー：前処理で整数に写像（スケーリング、ビット解釈、ハッシュではなく明確なマッピング）してから適用する。ただし正確さや精度に注意が必要。
  • 並列化：穴への書き込みは独立して行えるので、並列に分割して処理しやすい。出力の段階でも各穴を独立に展開できる。

具体例

例: A = [8, 3, 2, 7, 4, 6, 8] のとき

  • min = 2, max = 8, range = 7
  • holes = [[], [], [], [], [], [], []] // indices 0..6 がそれぞれキー 2..8 に対応
  • 各要素を該当の穴へ入れると holes = [[2], [3], [4], [6], [7], [], [8, 8]]
  • 穴を順に展開すると [2, 3, 4, 6, 7, 8, 8]（ソート完了）

典型的な用途・適用場面

  • キーのドメインが既知で狭い（例: 学年、評価スコア（0〜100）、カテゴリラベルなど）。
  • 安定ソートが必要で、かつキーの幅がそれほど大きくない場面。
  • リアルタイムかつ高速に多数の小さなキーをソートする必要がある組み込み系や特定のアプリケーション。

ピジョンホールソートと類似アルゴリズムとの比較

  • Counting sort（計数ソート）: ピジョンホールソートに非常に近い。計数ソートは各キーについて単にカウントを保持する点が主な違い。安定化するには累積和をとるなどの工夫が必要。
  • Bucket sort（バケットソート）: ピジョンホールソートはバケットソートの特殊ケースで、各バケットが単一のキー値に対応する。バケットソートは通常キーを区間に分け、各バケット内を別のソートで並べ替える。
  • Radix sort（基数ソート）: 複数桁のキー（例: 多桁の整数）を桁ごとに安定ソート（しばしば計数ソート）する手法で、pigeonhole 自体とは使われ方が異なるが、計数やバケットの概念を共通にする。

実装上の注意点

  • range の計算でオーバーフローが起きないか確認する（特に 32/64 ビット整数境界）。
  • holes の数が非常に大きくならないように事前にレンジをチェックし、閾値を超えるなら別のアルゴリズム（クイックソートやヒープソート、あるいはハイブリッド）にフォールバックする設計が望ましい。
  • 大きな range を確保する際のメモリ割当や初期化コストを考慮する。例えば多くの言語で大きな配列をゼロ初期化するとコストが高くなる。
  • 並列化する場合、各スレッドが独自の穴領域にアクセスするように分割するか、スレッド間競合を防ぐ同期手段を用いる。

まとめ — いつ使うべきか

ピジョンホールソートは「キーの範囲が狭い／既知である」「n に対して range が小さい／O(n) に近い」といった条件が満たされる場合に非常に有効な選択肢です。メモリ消費が許容でき、安定性が求められる用途に向いています。逆に、キーの範囲が広い、またはスパースである場合は不適切であり、計数ソート、ハッシュを用いた手法、あるいは一般的な比較ソートを検討するべきです。

参考文献

カテゴリー
IT
前の記事
Art Pepper入門 — 名盤・名演でわかるウェストコースト・ジャズの聴きどころとおすすめアルバムNew!!
2025年11月20日
次の記事
アート・ペッパー名盤ガイド：初心者も納得のおすすめアルバム6選と聴きどころ解説New!!
2025年11月20日