ALDS1_6_A:

この問題の計数ソートでは、入力の数列を便宜上 1 オリジンの配列に記録します。例えば、入力配列$A = \{4, 5, 0, 3, 1, 5, 0, 5\}$ に対して、計数ソートを行うことを考えます。次の図のように、配列 $A$ の各要素が何回現れるかを数え、配列 $C$ に記録します。

例えば、$A$ の中に 5 は 3 つ含まれているので $C[5]$ が $3$ となります。次に、カウンタ $C$ の各要素の累積和を求め、カウンタ配列 $C$ を更新します。

このカウンタ配列の要素 $C[x]$ には、配列 $A$ について $x$ 以下の要素の数が記録されていま す。次の図のように、このカウンタ配列 $C$を用いて、出力配列 $B$ に $A$ の要素を順番にコピ ーしていき、昇順に整列された要素を持つ配列 $B$ を作ります。

$A$ の要素を後ろから順番に参照して $B$ の適切な位置にコピーしていきます。 1. では $A[8] \;(= 5)$ をコピーしますが、$C[5] = 8$ より、$A$ の要素で 5 以下の数は 8 個あるので $B[8]$ に 5 をコピーします。このとき、$C[5]$ を１つ減らします。これで、$A$ の残りの要素で 5 以下の数は 7 個になります。

2. では $A[7]\;(= 0)$ をコピーしますが、$A$ の残りの要素で 0 以下の数は 2 個なので $B[2]$ に 0 をコピーします。3. では、$A$ の残りの要素で 5 以下の数は 7 個なので $B[7]$ に 5 をコピーします。以下同様に $B[i]$の値が決定していきます。

計数ソートは、入力配列 $A$ の要素を後ろから選んでいくことで安定なソートになります。図0の例では、$A$ の要素を前から選んでいくと重複している 0 と 5 が、それぞれ逆順に $B$ にコピーされてしまいます。

問題で示されている計数ソートは、$A_i$ が 0 以上という条件と $A_i$ の最大値のサイズに比例 する時間と記憶領域が必要となりますが、線形時間 $O(n + k)$ で動く高速で安定なアルゴリズムです。

Reference

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造 (マイナビ) AIZU ONLINE JUDGE のコース問題を題材にした解説書です。初級者が体系的にアルゴリズムとデータ構造の基礎を学ぶことができる入門書となっています。