カウントソート（Counting Sort）徹底ガイド：仕組み・疑似コード・計算量・実装上の注意点

カウントソートとは（概要）

カウントソート（Counting Sort）は、入力配列の各要素が比較可能な整数キー（あるいは整数に写像できるキー）であり、その値の取りうる範囲がそれほど大きくない場合に有効な整数ソートアルゴリズムです。比較に基づくソート（例えばクイックソートやマージソート）が持つ Ω(n log n) の下限に縛られない非比較ソートの一種で、基本的には「要素の出現回数を数える」ことでソートを実現します。

アルゴリズムの基本手順

典型的なカウントソートは以下の3段階で行われます。

• 1) カウント配列（count）を用意し、入力配列の各値の出現回数を数える。
• 2) count 配列を累積和（prefix-sum）に変換し、ある値が出力配列中で最終的にどの位置に配置されるかを示す情報を得る。
• 3) 元の入力配列の要素を走査して、累積和に従って出力配列の適切な位置に要素を置き、対応する count をデクリメントする（出力中での安定性を保つには入力を右から左に走査する）。

重要な点は、count 配列のインデックスがキーの値に対応するため、キーの取り得る範囲（最小値から最大値まで）が幅 k としてメモリや時間に直接影響を与えることです。

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

CountingSort(A, k)  // A は長さ n の配列、キーは 0..k-1 の整数範囲と仮定
  let B be an array of length n    // 出力配列
  let C be an array of length k    // カウント配列
  for i = 0 to k-1
    C[i] = 0
  for j = 0 to n-1
    C[A[j]] = C[A[j]] + 1         // 出現回数を数える
  for i = 1 to k-1
    C[i] = C[i] + C[i-1]          // 累積和に変換
  for j = n-1 downto 0            // 安定性を保つため右から左へ走査
    B[C[A[j]] - 1] = A[j]
    C[A[j]] = C[A[j]] - 1
  return B

具体例（短いステップ）

入力 A = [2, 5, 3, 0, 2, 3, 0, 3] とし、キーの範囲を 0..5 とすると：

• 出現回数 C（初期）: [0,0,0,0,0,0]
• 出現回数カウント後 C: [2,0,2,3,0,1]
• 累積和に変換後 C: [2,2,4,7,7,8] → 例えば値 3 は出力配列の位置 4..6 に割り当てられる
• 入力を右から左に配置すると出力 B = [0,0,2,2,3,3,3,5]

計算量と空間計算量

• 時間計算量: O(n + k)
• 空間計算量: O(n + k)（出力配列 B とカウント配列 C を用いる場合）

ここで n は入力サイズ、k はキーの取りうる値の個数（max-min+1）です。k が小さい（あるいは k = O(n)）場合、カウントソートは線形時間で効率的に動作します。一方、k が非常に大きい（例えば最大値が非常に大きいが n は小さい）場合、k に比例したメモリと時間のオーバーヘッドが問題となり現実的でないことが多いです。

安定性とインプレース性（副次的性質）

カウントソートは上記の方法（累積和を使い、入力を右から左に走査して出力に配置する）で実装すると「安定（stable）」です。安定性とは、等しいキーを持つ要素の相対順序がソート後も保たれることを指します。安定であるため、基数ソート（Radix Sort）など他のアルゴリズムの安定なサブルーチンとして頻繁に使われます。

ただし、典型的なカウントソートは追加の出力配列を必要とするため「インプレース（in-place）」ではありません。インプレースな変種やメモリを節約する工夫は研究・実装されていますが、複雑になり安定性を失うことがあるため注意が必要です。

負の整数や任意の整数への拡張

標準の説明ではキーが非負整数（0 以上）であることを仮定しますが、最小値 m を求めて各キーから m を引いてオフセットを付けることで負の整数にも対応可能です。すなわち、インデックスを value - min_value に変換して count 配列を使います。

用途と長所・短所

• 長所
  • キーの範囲 k が小さい場合に非常に高速（線形時間）。
  • 安定な実装が容易で、基数ソートの安定なサブルーチンとして重要。
  • 実装や理解が比較的単純（出現回数→累積和→配置）。
• 短所
  • キーの範囲 k が大きい場合にメモリ消費が大きく、非現実的になる。
  • キーが連続でない大きな値（例: 32 ビットの散らばった整数）では直接適用しにくい。
  • 通常は追加の出力配列を必要とし、インプレースではない。

実装上の注意点・現実的な課題

• count 配列の初期化コスト: k が大きいとゼロクリアのコストが無視できない。
• メモリ割当ての影響: 実際のランタイムでは count や出力配列の確保・解放がボトルネックになり得る。
• 整数オーバーフロー: n が非常に大きい場合、count の累積和が格納型（例えば 32-bit int）で溢れる可能性があるため注意が必要（適切な整数型を選ぶ）。
• キーの圧縮: キーの範囲が大きくても実際に現れるキーが少ない場合、辞書（ハッシュ）を使ってキーを圧縮してからカウントソート的処理を行う方法がある。ただし、これによりアルゴリズムの単純性や定数因子が変わる。

応用例

• 基数ソート（Radix Sort）の安定なサブルーチン：各桁ごとに安定なカウントソートを適用して多桁整数を効率的に整列する。
• ヒストグラム作成や頻度分析：出現回数を数える処理そのものが目的となる場面。
• 限定された値域のデータ（投票データ、色インデックス、バケット化された統計データなど）の高速ソート。

正当性（簡単な議論）

累積和 C[i] を「値 i 以下の要素数」を表すように構成すると、C[A[j]] は値 A[j] を持つ要素のうち、出力配列中で置かれるべき最右位置（1-based）を示します。入力を右から左に走査して C[A[j]] の位置に要素を置き、値 A[j] のカウントをデクリメントすれば、等しいキー間の相対順序が維持される（安定）ことが示せます。したがって、出力配列は正しくソートされます。

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

カウントソートは「キーの値域が限られている」か「値の種類が少ない」状況で最も適しており、その場合は非常に高速かつ実装も単純です。ただし、値域が大きくなるとメモリと初期化のコストが問題になり、一般的な用途ではマージソートやヒープソート、クイックソートの方が現実的です。キーが大きいが桁数（ビット数）に対する操作で扱えるなら基数ソート＋カウントソートの組合せが有効です。

参考文献

• Counting sort — Wikipedia
• T. H. Cormen et al., "Introduction to Algorithms" (CLRS) — MIT Press
• Radix sort — Wikipedia
• Counting Sort — GeeksforGeeks（実装例・解説）