計数ソート¶
計数ソート（counting sort）は要素数を集計することでソートを実現し、通常は整数配列に適用されます。
単純な実装¶
まず簡単な例を見てみましょう。長さ \(n\) の配列 nums が与えられ、その要素はすべて「非負整数」であるとします。計数ソートの全体的な流れを以下の図に示します。
- 配列を走査し、その中の最大値を見つけて \(m\) とし、続いて長さ \(m + 1\) の補助配列
counterを作成します。 counterを用いてnums内の各数値の出現回数を集計します。ここでcounter[num]は数値numの出現回数に対応します。集計方法は非常に簡単で、numsを走査し（現在の数値をnumとする）、各回でcounter[num]を \(1\) 増やせばよいです。counterの各インデックスは自然に順序づけられているため、すべての数値はすでに整列された状態とみなせます。続いてcounterを走査し、各数値の出現回数に応じて小さい順にnumsへ書き戻せば完了です。
コードは以下のとおりです：
計数ソートとバケットソートの関係
バケットソートの観点から見ると、計数ソートにおける計数配列 counter の各インデックスを 1 つのバケットとみなし、個数を数える過程を各要素を対応するバケットへ振り分ける操作とみなせます。本質的には、計数ソートは整数データにおけるバケットソートの特殊な一例です。
完全な実装¶
注意深い読者なら、**入力データがオブジェクトである場合、上記の手順 3. は機能しない**ことに気づくかもしれません。入力データが商品オブジェクトであり、商品価格（クラスのメンバ変数）に基づいて商品をソートしたいとします。しかし上記のアルゴリズムが返せるのは価格のソート結果だけです。
では、元のデータのソート結果を得るにはどうすればよいのでしょうか。まず counter の「累積和」を計算します。名前のとおり、インデックス i における累積和 prefix[i] は、配列の先頭から i 番目までの要素の総和に等しくなります：
累積和には明確な意味があり、prefix[num] - 1 は要素 num が結果配列 res に最後に現れるインデックスを表します。この情報は非常に重要で、各要素が結果配列のどの位置に現れるべきかを示してくれます。続いて元の配列 nums を逆順に走査し、各要素 num に対して各反復で次の 2 つの手順を行います。
numを配列resのインデックスprefix[num] - 1に格納します。- 累積和
prefix[num]を \(1\) 減らし、次にnumを配置するインデックスを得ます。
走査が完了すると、配列 res にソート済みの結果が格納されます。最後に res で元の配列 nums を上書きすれば完了です。以下の図は完全な計数ソートの流れを示しています。
計数ソートの実装コードは以下のとおりです：
アルゴリズムの特性¶
- 時間計算量は \(O(n + m)\)、非適応ソート ：
numsの走査とcounterの走査が含まれ、いずれも線形時間です。一般には \(n \gg m\) であり、時間計算量は \(O(n)\) に近づきます。 - 空間計算量は \(O(n + m)\)、非インプレースソート：長さがそれぞれ \(n\) と \(m\) の配列
resとcounterを利用します。 - 安定ソート：
resに要素を埋める順序が「右から左」であるため、numsを逆順に走査することで等しい要素どうしの相対位置が変化するのを防ぎ、安定ソートを実現できます。実際には、numsを順方向に走査しても正しいソート結果は得られますが、その結果は安定ではありません。
制約¶
ここまで読むと、計数ソートは非常に巧妙で、個数を数えるだけで効率的なソートを実現できると感じるかもしれません。しかし、計数ソートを利用するための前提条件は比較的厳格です。
計数ソートは非負整数にしか適用できません。ほかの型のデータに適用したい場合は、それらのデータを非負整数に変換でき、かつ変換の過程で要素間の相対的な大小関係が変わらないことを保証する必要があります。たとえば、負数を含む整数配列に対しては、すべての数値に定数を加えて正数へ変換し、ソート後に元へ戻すことができます。
計数ソートはデータ量が多く、値域が小さい場合に適しています。たとえば上記の例では \(m\) が大きすぎてはならず、そうでないと過剰な空間を消費します。また、\(n \ll m\) のとき、計数ソートは \(O(m)\) 時間を要するため、\(O(n \log n)\) のソートアルゴリズムより遅くなる可能性があります。