計数ソート

計数ソートは、値を添字にして出現回数を数えます。要素同士を比較する代わりに、各値が出力配列のどこに入るかを計算します。キーが小さい範囲の整数なら、時間 O(n + k) で整列できます。

このレッスンでは、非負整数の配列から度数表を作り、累積和で出力位置を求めます。入力を末尾から走査して出力するため、同値の要素の順序を保つ安定ソートです。

計数ソートの仕組み

最大値を k として、count[0..k] を 0 で初期化します。各入力値 x に対して count[x] を一つ増やします。この時点の count[x] は、値 x の出現回数です。

次に count[x] += count[x − 1] で累積和を作ります。すると count[x] は「値が x 以下の要素数」に変わります。これは、出力配列で x 以下の要素が占める領域の終端の次の位置です。最後の x が入る添字は count[x] − 1 になります。

入力を末尾から読み、値 x のカウントを一つ減らして、その位置へ書き込みます。同値の要素のうち、入力で後ろにあるものを出力の後ろへ置きます。これが安定性を保つ仕組みです。

計数ソートのステップ

初期入力は [2, 5, 3, 0, 2, 3, 0, 3] です。最大値は 5 なので、カウント配列は六要素です。

出現回数を数える。 0 は二回、2 は二回、3 は三回、5 は一回です。度数表は [2, 0, 2, 3, 0, 1] になります。

累積和を作る。 左から加算すると [2, 2, 4, 7, 7, 8] になります。たとえば 3 以下の要素は七つなので、最後の 3 は添字 6 に入ります。1 と 4 は入力になくても、累積和の計算ではその位置を通ります。

末尾から配置する。 三つの 3 を入力順に 3a、3b、3c、二つの 0 を 0a、0b と呼びます。末尾の 3c は count[3] を 7 から 6 に減らし、出力の添字 6 へ置きます。次の 0b は添字 1、3b は添字 5 へ入ります。

残りは 2b を添字 3、0a を添字 0、3a を添字 4、5 を添字 7、2a を添字 2 へ置きます。結果は [0, 0, 2, 2, 3, 3, 3, 5] です。各同値グループでは元の順序が保たれます。

アニメーションでは、度数表が累積和へ変わる点を確認します。同じカウント欄でも、前半は出現回数、後半は出力位置の境界を表します。要素の元の添字は、安定性の確認に使えます。

時間・空間計算量

カウント配列は k + 1 要素、出力配列は n 要素なので、追加領域も O(n + k) です。キーの範囲が入力サイズに近い場合に適しています。k が n より大きいと、使わない値のためにも領域と処理が必要です。

たとえば、四要素しかなくても最大値が 29 なら、カウント配列は三十要素で、累積和の加算は二十九回です。レッスンの入力上限 MAX_KEY は 30 ですが、これは表示の制約であり、アルゴリズム自体の上限ではありません。

境界条件

• 空配列：最大値を求める前に終了します。画面の入力は一要素以上ですが、実装では空入力も扱う必要があります。
• 一要素：結果は同じ値です。最大値までのカウント配列の処理は残ります。
• 全要素が同値：一つのキーにカウントが集まります。末尾から配置すれば順序は保たれます。
• すべて 0：カウント配列は一要素で、累積和の加算は不要です。
• キーの範囲が広い：入力が少なくても O(k) の費用がかかります。比較ソートの方が適する場合があります。

よくある間違い

• この配置方法で入力を先頭から読む：同値の要素を後ろから埋めるため、順序が逆転します。安定性のために末尾から読みます。
• 減らす前の count[x] を添字にする：境界の次の位置へ書き込むため、一つずれます。先に減らすか、count[x] − 1 に書きます。
• カウント配列を n 要素にする：必要なサイズは最大キーに依存します。k + 1 要素を用意します。
• 負数をそのまま添字にする：最小値に応じたオフセットが必要です。小数や文字列も、この実装の添字には直接使えません。