JavaScriptでカウントソートを実装する方法をわかりやすく解説

カウントソートとは？

今回は、数値の配列を受け取り、カウントソート（計数ソート）アルゴリズムを使って昇順に並べ替えるJavaScript関数を実装します。

配列の最大値が事前に分かっている場合、カウントソートを利用すれば線形時間・線形空間（O(n)）で数値配列を並べ替えることができます。一般的な比較ベースのソート（クイックソートやマージソートなど）の計算量が O(n log n) であることを考えると、条件さえ揃えば非常に効率的な手法です。

アルゴリズムの流れ

カウントソートは、以下の手順で動作します。

1. 最大値の特定： まずループを1回実行し、配列内の最大の要素を見つけます。
2. カウント配列の作成： 最大値をもとにそのサイズ分の配列を作成し、各インデックス値の出現回数を記録します。
3. 結果の展開： カウントが0でないすべてのインデックスを、出現回数の分だけ結果配列へ順番に書き出します。

実装例

const arr = [4, 3, 1, 2, 3];
const findMaximum = arr => arr.reduce((acc, val) => val > acc ? val : acc, Number.MIN_VALUE);
const countingSort = (arr = []) => {
    const max = findMaximum(arr);
    const counts = new Array(max + 1);
    counts.fill(0);
    arr.forEach(value => counts[value]++);
    const res = [];
    let resultIndex = 0;
    counts.forEach((count, index) => {
        for (let i = 0; i < count; i++) {
            res[resultIndex] = index;
            resultIndex++;
        };
    });
    return res;
};
console.log(countingSort(arr));

出力結果

コンソールには次のように出力されます。

[ 1, 2, 3, 3, 4 ]

コードのポイント

• findMaximum： reduce() を使い、配列を1周するだけで最大値を求めます。
• counts配列： 各数値の出現回数を、値をインデックスとして対応付けて記録します。
• 結果の再構築： インデックスの小さい順に、カウント数ぶんだけ値を結果配列へ格納するため、自然と昇順に並びます。

計算量と注意点

カウントソートの時間計算量は O(n + k)（nは要素数、kは最大値）、空間計算量は O(k) です。ただし、実務で使う際は以下の点に留意してください。

• 最大値が極端に大きい場合、カウント配列が巨大化し、メモリを大量に消費する可能性があります。
• 負の数が含まれる場合は、オフセットによる調整などの工夫が必要です。
• 整数の配列に特化した手法のため、文字列やオブジェクトのソートにはそのまま適用できません。