計数ソート（Counting Sort）とは？原理・時間計算量・実装例と実務での使いどころ
エバープレイ編集部計数ソートとは
計数ソート（Counting Sort）は、整数（あるいは有限個の離散的なキー）を対象にした非比較型の安定ソートアルゴリズムの一つです。配列中の要素の「値の出現回数（頻度）」を数え、その累積和を用いて出現順や目的の順序に再配置することでソートを実現します。比較ベースのソート（例えばクイックソートやマージソート）の下限 O(n log n) に縛られないため、キーの範囲が小さい場合は線形時間でソートできます。
基本アイデア
- 入力配列 A[0..n-1] の各要素は整数（または整数に写像できるキー）で、値の取りうる範囲は有限である（例えば 0..k の範囲）。
- まず各値 v の出現回数をカウントして配列 C[v] に格納する。
- 次に C を累積和に変換して、各値 v がソート後の出力配列における終了位置（あるいは開始位置）を示すようにする。
- 最後に入力配列の要素をその位置に配置することでソートを完了する。安定性を保つために、通常は入力を後ろから走査して出力へ配置する。
アルゴリズムの手順（概要）
典型的な安定計数ソートの手順は次のとおりです。
- 1. カウント配列 C を初期化（長さ k+1、全要素を 0 にする）。
- 2. 入力 A を走査して、各値 v に対して C[v] をインクリメントする（出現回数の計上）。
- 3. C を累積和に変換する：C[i] = C[i] + C[i-1]（これにより値 i がソート後に終端となる位置がわかる）。
- 4. 出力配列 B（長さ n）を用意し、A を後ろから走査して各要素 v を B[C[v]-1] に置き、C[v] をデクリメントする（安定性のため後ろから）。
- 5. B がソート済み配列になる。必要なら A にコピーする。
簡単な例
入力 A = [4, 2, 2, 8, 3, 3, 1]（値の範囲は 1..8 とする）で考えます。
- ステップ1: C = [0,0,0,0,0,0,0,0,0]（0〜8 をインデックスに持つとする）
- ステップ2: 出現回数を数えると C = [0,1,2,2,1,0,0,0,1]
- ステップ3: 累積和を取ると C = [0,1,3,5,6,6,6,6,7]
- ステップ4: A を後ろから走査して B に配置：
- 要素 1 → C[1]=1 → B[0]=1, C[1]→0
- 要素 3 → C[3]=5 → B[4]=3, C[3]→4
- 要素 3 → C[3]=4 → B[3]=3, C[3]→3
- 要素 8 → C[8]=7 → B[6]=8, C[8]→6
- 要素 2 → C[2]=3 → B[2]=2, C[2]→2
- 要素 2 → C[2]=2 → B[1]=2, C[2]→1
- 要素 4 → C[4]=6 → B[5]=4, C[4]→5
- 結果 B = [1,2,2,3,3,4,8]
計算量とメモリ使用量
- 時間計算量（典型）：Θ(n + k)。ここで n は入力の要素数、k はキーの取りうる種類数（最大値と最小値の差 + 1）。
- 空間計算量：追加で O(k + n) のメモリが必要。具体的にはカウント配列 C（長さ k）と出力配列 B（長さ n）を用いるため。
- したがって、k が n と同程度かそれ以下であれば効率的だが、k が非常に大きい（例えば値域が広く、ほとんどの値が使われていない）場合は非効率となる。
- 計数ソートは比較ソートではないため、比較ベースのソートの下界 O(n log n) に縛られず、入力が適合すれば線形時間でソートできる。
安定性について
計数ソートは累積和と後ろ向きの配置を用いれば安定（同じキーの要素の相対順序を保持）になります。これは主にレコード（キーに紐づいた付随情報）を扱うときに重要で、安定なソートを前提にした次段の処理（例えば桁ごとの安定なソートを用いる基数ソート）で必要です。
負の値や任意の整数への対応
計数ソートは配列のインデックスをキーに使うため、負の値があるとそのままでは使えません。対処法は簡単で、全要素の最小値 min を求めて各要素から min を引いて 0 ベースにオフセットします。つまりインデックス = value - min としてカウント配列 C を扱えばよい。
利点と欠点（実用的な観点）
- 利点
- キーの範囲が限られている場合に高速（Θ(n + k)）。
- 安定であり、基数ソートの一段として使用できる。
- 実装が比較的単純。
- 欠点
- キーの範囲 k が大きいとメモリと時間が無駄になる（k が n よりずっと大きい場合は不利）。
- 実数や一般的な比較ベースの順序付け（例えば文字列比較など）には直接適用できない。整数キーに限定される。
- 出力用配列を必要とするため、追加メモリが必要（完全にインプレースにするには工夫が必要で、安定性が失われることもある）。
計数ソートと基数ソートの関係
計数ソートは基数ソート（Radix Sort）の各桁ソートとしてよく用いられます。特に LSD（最下位桁優先）方式の基数ソートでは、各桁を安定にソートするために計数ソートが適しています。これにより、例えば b 進数で d 桁の整数をキーとすると、計数ソートを d 回適用して O(d(n + b)) の時間でソートでき、b を定数とすれば線形時間になります。
実装上の注意点と最適化
- メモリ節約：カウント配列のサイズは実際に使用される値域（max-min+1）にする。可能ならば min と max を事前に探索して k を最小化する。
- 出力の再利用：出力配列 B を入力配列 A にコピーする手間を省くために、必要に応じて A と B を交互に使うなどの工夫ができる（ただし実装が複雑になる）。
- 並列化：出現回数の計算や累積和は並列化しやすく、大きなデータやマルチコア環境で有利。
- キャッシュ効率：カウント配列が非常に大きくなるとキャッシュミスが増えパフォーマンスが落ちるため、可能ならばキーのスケーリングや分割（分割して各チャンクをソート）を考慮する。
変種と応用
- 頻度解析（ヒストグラム作成）：計数ソートのカウント部分だけで頻度分布を取得できる。
- インプレース版：追加メモリを減らすための不安定な in-place 実装が研究されているが、一般にコードは複雑になる。
- キーの圧縮：値域が広いが実際に使われているキーの種類が少ない場合は、連想配列（ハッシュマップや辞書）でキーを圧縮してから計数ソート的な手法を使うことも可能。ただしその場合はハッシュのオーバーヘッドを考慮する必要がある。
典型的な疑問への回答（Q&A）
- Q：計数ソートはいつ使うべきか？
A：キーが整数で、かつキーの取り得る範囲 k が n と比較して十分小さい（例：k = O(n) や定数）場合。例えば年齢分布（0〜120）やバケット分けに適する。 - Q：負の値や大きな値は扱えるか？
A：オフセットを使えば整数範囲なら扱えるが、範囲が大きいとメモリが問題になる。 - Q：計数ソートは安定か？
A：適切に累積和と後ろ向き配置を行えば安定。
まとめ
計数ソートは「整数キーの範囲が限られている」状況において非常に強力なソート手法です。時間計算量が Θ(n + k) であり、比較ソートの下界を回避できる点が最大の利点です。一方で k が大きい場合のメモリと時間の無駄、そして整数キーに限定される点が制約です。実務では基数ソートの一部として多用されるほか、頻度解析などソート以外の用途にも使えます。実装時はキーのオフセット、累積和の取り方、安定性の保持、メモリとキャッシュ効率の考慮が重要になります。
参考文献
- Counting sort — Wikipedia
- How does Counting Sort work? — CS StackExchange (解説と議論)
- Counting Sort — Princeton Algorithms (実装例)
- Counting Sort — GeeksforGeeks
- Cormen, Leiserson, Rivest, Stein — Introduction to Algorithms（計数ソートの説明）
投稿者プロフィール
