分配ソートとは？カウント・基数・バケットの仕組みと計算量、実装・最適化ガイド

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

分配ソートとは — 概観

分配ソート（ぶんぱいソート、distribution sort）は、キーの値域や桁の構造を利用してデータを「分配（バケット／カウント）」し、その後に各グループを整理して全体をソートする一群の非比較ソート手法の総称です。比較ソート（例：クイックソート、マージソート）が要素間の比較に基づいてソートするのに対し、分配ソートはキーのビットや桁、値の範囲に直接アクセスすることでソートを高速化します。

代表的な分配ソートの種類

  • カウントソート（Counting Sort）：要素の取りうる値の範囲が有限（0..k）である場合に、出現回数を数えることで安定にソートします。計算量は O(n + k)、追加の作業領域は O(k + n)（安定化のため出力配列が必要）です。

  • バケットソート（Bucket Sort）：値域を複数のバケットに分割し、各バケット内を別のソート法（一般には挿入ソートなど）で整列します。平均的には O(n + m)（m はバケット数＋バケット内コスト）で、値が均等に分布することが前提です。

  • 基数ソート（Radix Sort）：キーを桁（またはビット群）ごとに部分的にソートしていく方法です。各桁の安定ソート（通常はカウントソート）を繰り返します。d 桁、基数 b とすると計算量は O(d*(n + b))、一般に O(d·n) と表現されます。

  • 一般化された分配ソート（Multiway/Distribution Sort）：キー域を多数のグループに分割し、再帰的に各グループをソートする方法で、クイックソートの多分岐版や外部ソートの分配段階として用いられます。

なぜ分配ソートを使うか — 長所と短所

  • 長所

    • 比較に依存しないため、特定条件下で理論上より高速（例えばカウントソートは O(n + k)）。
    • キーが整数や固定長のビット列、桁で表現される場合に非常に効率的。
    • 基数ソートは安定であり、複数キーのソート（MSD/LSB法）に有利。
    • 外部ソート（大規模データ）で分配→マージの戦略が使える。

  • 短所／制約

    • 値域が広い（k が大きい）と空間・時間コストが跳ね上がる（カウントソートの O(k) が問題）。
    • キーの分布に強く依存する（バケットソートは均等分布が前提）。
    • 比較ソートの下限（Ω(n log n)）を破るのは「比較以外の操作」を使う場合に限られるため、一般的な比較ベースのソートに比べ適用条件が限定される。
    • メモリ使用量や一時データの割当てが増えやすく、実装が複雑になる場合がある。

アルゴリズム詳細と計算量

以下に主要な手法の概略と計算量、安定性、メモリ要件を整理します。

  • カウントソート

    • 時間計算量：O(n + k)（n は要素数、k は値域の大きさ）。
    • 空間計算量：O(k + n)（カウント配列と出力配列）。
    • 安定性：工夫すれば安定（累積和を使う実装）。
    • 備考：k が n と同程度以下なら実用的。負の数や任意の整数はオフセットで扱える。

  • バケットソート

    • 平均時間：O(n + m)（m はバケット関連のコスト）。
    • 最悪時間：バケットに偏りが生じると O(n^2) になることも（各バケット内を挿入ソートする場合）。
    • 空間：追加でバケット領域が必要。バケットに使うデータ構造次第で変動。
    • 備考：数値が [0,1) に一様分布する場合の理論解析がよく示される。

  • 基数ソート

    • 時間：O(d·(n + b)) または簡略に O(d·n)（d：桁数、b：基数）。
    • 空間：各桁の安定ソート（多くはカウントソート）に一時配列 O(n + b)。
    • 安定性：桁ごとの安定ソートを行うため全体として安定。
    • 備考：整数や固定長の文字列のソートに向く。LSB（下位桁）からの処理か、MSD（上位桁、再帰）かで実装が分かれる。

  • 一般化分配ソート（多分岐分配）

    • 理想的には分配数を工夫すれば比較ソートより低い深さで分割が進むため、実行時間を低く抑えられる。
    • 外部ソート用途ではディスクI/Oを最小化するための「分配→合併」戦略が使われることが多い。

実装上の注意点と最適化

  • 安定性を意識する：基数ソートのように複数段で行うソートでは、各段が安定であることが必須です。カウントソートを安定に実装する（累積和から配置する手法）ことが多いです。

  • メモリと値域のトレードオフ：カウントソートは k が大きいと不利です。実データで k が大きい場合は基数ソート（ビット幅ごとに分割）やバケットを工夫して用いることを検討します。

  • 基数の選び方：基数 b を大きくすると段数 d は減るが、カウント配列のサイズが増える。例えば 32ビット整数を扱う場合、バイト単位（b=256）で4パスにするか、2進チャンクで8パスにするかなどの選択がある。メモリとキャッシュ効率を考えて決めます。

  • 小配列は比較ソートで処理：バケットソートや再帰的分配ソートでは、ある閾値以下の小さい分割に対しては挿入ソートやクイックソートに切り替えた方が実行速度が良くなることが多いです。

  • 外部ソートでの利用：外部メモリ（ディスク）を使う場合、分配段階で複数の出力ファイルに記録してからマージする「外部分配ソート」戦略がディスクアクセスを減らすために使われます。

  • 並列化：バケット分配は自然にデータ並列にできる（各スレッドが部分配列を担当して集計→再配置）。ただし再配置（書き込み）やバケットのサイズ計算で同期が必要。

サンプル：代表的な擬似コード（説明用）

以下は理解のための擬似コードです。実装時は境界チェックやオフセット処理、メモリの確保・解放を入れてください。

カウントソート（擬似）

function countingSort(A, k):
  // A: 要素配列（整数、0..k）
  // k: 最大値
  C = array[0..k] initialized to 0
  for x in A:
    C[x] += 1
  // 累積和で位置を決める（安定化）
  for i from 1 to k:
    C[i] = C[i] + C[i-1]
  B = array[length(A)]
  for i from length(A)-1 downto 0:
    B[C[A[i]]-1] = A[i]
    C[A[i]] -= 1
  return B

基数ソート（LSB法, 擬似）

function radixSort(A, d): // d は桁数（例：バイト単位なら4）
  for i from 0 to d-1:
    // i 桁目を基準に安定ソート（例：カウントソート）を行う
    A = stableCountSortByDigit(A, i)
  return A

実用上の使い分け

  • 要素が整数で値域が限られている／キーのビット長が固定ならカウントソートや基数ソートが有力。
  • 小数や実数で一様分布が期待できるならバケットソートが有効（各バケットは小さいので簡単にソートできる）。
  • 汎用的な用途や安定性が不要でメモリ制約が厳しい場合は、比較ベースのクイックソートやヒープソートを選ぶ方が無難。
  • 大規模データ（外部記憶）ではディスクI/Oを考慮した外部分配ソートやマルチウェイマージが重要。

応用例・実際の使用場面

  • データベースや統計処理での整数カウント集計（ヒストグラム的処理）。
  • ハッシュテーブルの代替やプリフィックス辞書の構築前処理。
  • 文字列ソート（固定長のバイナリ表現を基にした基数ソート）。
  • 外部ソート（巨大ファイルのソート）でディスク上に分配してからマージする手法。
  • GPUやSIMDを活用した並列分配ソートは大規模な並列環境で有効。

まとめ（実務的な選び方）

分配ソートは「キーの構造（値域・桁・ビット）」を利用して比較を避けることで高速化を図る強力な手法です。しかし利点は適用条件に依存します。値域が小さい・キーが固定長である・分布が予測可能、という状況で真価を発揮します。一方でメモリ使用量、極端な分布への脆弱性、実装の複雑さなどを考慮して、適材適所で選択することが重要です。

参考文献

カテゴリー
IT
前の記事
Warne Marsh入門：トリスターノ直系テナーの経歴・演奏スタイル・名盤と聴きどころNew!!
2025年11月20日
次の記事
Art Pepper入門 — 名盤・名演でわかるウェストコースト・ジャズの聴きどころとおすすめアルバムNew!!
2025年11月20日