カウントソート｜コードで実践

カウントソート

このレッスンで分かること

一方、カウントソート (counting sort) は 比較を 1 度も使わない 特殊なソートです

[3, 1, 4, 1, 5, 9, 2, 6, 5, 3] をソートする例で、min = 1, max = 9 なので k = 9 です

結果は [1, 1, 2, 3, 3, 4, 5, 5, 6, 9]

カウントソートとは

比較を一切使わず、出現回数を数えるだけで O(n+k) で並べ替えるカウントソートを実装する。本レッスンでは、カウントソートの基本から実際の使いどころまでを整理し、現場で迷わず使える形に落とし込みます。

ここまで見てきた バブル 選択 挿入 マージ クイック はすべて 比較ベース のソートでした。比較で値の大小を確かめる限り、計算量は O(n log n) より速くなれません (情報理論的下限)。

一方、カウントソート (counting sort) は 比較を 1 度も使わない 特殊なソートです。値の出現回数を数える バケット を用意し、小さい値から順に書き出すだけで整列が完了します。整数のように値域 k が限定されている場面で O(n + k) という驚異的な速度を発揮します。

カウントソートは比較ベースの下限 O(n log n) を破る。ただし整数や有限の値域に限られる。

アルゴリズムの動き

[3, 1, 4, 1, 5, 9, 2, 6, 5, 3] をソートする例で、min = 1, max = 9 なので k = 9 です。

長さ k = 9 のカウント配列を 0 で初期化する。
入力を走査して、各値の出現回数を count[value - min] += 1 で記録。
カウント配列を左から走査し、count[i] 回だけ i + min を出力配列に追加。

結果は [1, 1, 2, 3, 3, 4, 5, 5, 6, 9]。比較は一切していません。値の出現回数 を介して並べているだけです。

diagram (will load when visible)

Python での実装

Python

def countingSort(arr):
    if not arr:
        return []
    lo = min(arr)
    hi = max(arr)
    count = [0] * (hi - lo + 1)
    for v in arr:
        count[v - lo] += 1
    result = []
    for i, c in enumerate(count):
        result.extend([i + lo] * c)
    return result

min と max を取って 値域の幅 を確定させてから、カウント配列のサイズを決めます。負の値があっても lo を引いてオフセットすれば問題ありません。

JavaScript での実装

JavaScript

function countingSort(arr) {
  if (arr.length === 0) return [];
  let lo = arr[0], hi = arr[0];
  for (const v of arr) {
    if (v < lo) lo = v;
    if (v > hi) hi = v;
  }
  const count = new Array(hi - lo + 1).fill(0);
  for (const v of arr) count[v - lo]++;
  const result = [];
  for (let i = 0; i < count.length; i++) {
    for (let j = 0; j < count[i]; j++) result.push(i + lo);
  }
  return result;
}

計算量と適用範囲

時間: O(n + k) (n = 要素数、k = 値域の幅)
空間: O(k)
安定: 拡張版は 安定、簡易版 (本レッスン) は 不安定 (整数なので影響なし)

たとえば n = 10^6 で k = 100 なら、比較ソートが 10^6 * 20 = 2 * 10^7 操作なのに対し、カウントソートは 10^6 + 100 ≒ 10^6 で済みます。値域が小さいときには圧勝です。

k が n を大きく上回ると逆効果。[1, 1000000000] のような配列で使うとメモリ爆発。

よくある間違い

1 つ目は min を取らずに count[v] を直接使う。負の値があると配列の負インデックスになります (Python なら逆参照、JS なら undefined)。必ず v - lo でオフセットします。2 つ目は 空配列の処理忘れ。min(arr) を空配列で呼ぶと例外。先頭で if not arr を入れておくこと。3 つ目は 値域が広すぎる入力で使う。[1, 10^9] でカウントソートを呼ぶと 10^9 個の配列を確保しようとして死にます。

やってみよう

[-2, 0, -5, 3, 0] のような 負の数を含む配列 で動作することを確認する。
min と max の差が n より大きいとき、カウントソートとクイックソートのどちらが速いか計測する。
カウント配列を 累積和 に変換して 安定 カウントソートにしてみる (オブジェクト配列のソートで重要)。

基数ソートとの関係

カウントソートを 桁ごと に繰り返し適用すると、基数ソート (radix sort) になります。整数を 10 進数の桁で分解し、1 の位から順に安定カウントソートをかけていくと、最終的に全体がソートされます。値域が 0..10^9 でも、各桁の値域は 0..9 なのでカウントソートが高速に動きます。

diagram (will load when visible)

図のポイント (テキスト併記)

基数ソートは O(d * (n + b)) (d = 桁数、b = 基数)

基数ソートは O(d * (n + b)) (d = 桁数、b = 基数)。整数や固定長文字列のソートで威力を発揮する。

計算機実装のテクニック

大規模データでカウントソートを使うときは、count 配列を 累積和 に変換する一手間で安定性が手に入ります。count[i] を「i 以下の要素数」に変えると、各要素を 末尾の位置から 入れていくだけで 安定 な順序が保てます。レコードのソート (例えば (年齢, 名前) を年齢順) で重要なテクニックです。

よくある質問

Q. このトピックは実務でどう役立ちますか？

A. DB のクエリ最適化、API 設計、データ構造の選択など、設計判断の根拠になります。表面的にライブラリを使うだけでなく「なぜそれが速いのか」を理解できると、性能問題を未然に防げます。コーディング面接でも頻出のテーマです。

Q. 計算量はどう求めれば良いですか？

A. ループのネストごとに掛け算する、再帰なら漸化式から解く、というのが基本です。Big-O 表記は定数倍と低次の項を無視するため、n の指数（n²、n log n など）に注目してください。最悪・平均・最良の 3 つを意識すると説得力が増します。

Q. 覚えるべき定番アルゴリズムは何ですか？

A. 二分探索、クイックソート/マージソート、BFS/DFS、ダイクストラ、DP の基本問題（フィボナッチ・ナップサック）が必修です。これらを「白紙から書ける」状態にすると、応用問題が一気に解けるようになります。

次のレッスン

次は 比較関数つきソート で、比較関数を渡して任意のキーで並べ替える方法を学びます。

事前確認 — 進む前に次の 3 つができることを確認しましょう。

カウントソートの要点を自分の言葉で説明できる
このレッスンの最小コード (または操作手順) を見ずに書ける
練習問題やクイズで間違えた箇所を読み直して理解した

理解度チェック (30 秒)

Q. カウントソートとは何か、1 文で説明してください。

この章のポイント

A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。

関連レッスン

カウントソート