カウントソート（計数ソート）とは？仕組み・計算量・C++実装をわかりやすく解説

カウントソート（計数ソート）とは

カウントソートは安定なソート手法の一つで、比較的小さな整数値をキーとして要素を並べ替えるために用いられます。同じキー値を持つ要素の個数を数え、その情報をもとに各要素の正しい位置を決定するのが大きな特徴です。

この手法は、キーとなる数値同士の差（最大値と最小値の範囲）がそれほど大きくない場合に非常に効果的です。逆に、値の範囲が広すぎるとカウント用の配列が巨大になり、空間計算量が増大してしまう点には注意が必要です。

カウントソートの計算量

• 時間計算量：O(n+r)（n は要素数、r はキーの範囲）
• 空間計算量：O(n+r)

入力と出力

入力:
ソートされていないデータのリスト: 2 5 6 2 3 10 3 6 7 8
出力:
ソート前の配列: 2 5 6 2 3 10 3 6 7 8
ソート後の配列: 2 2 3 3 5 6 6 7 8 10

アルゴリズム

countingSort(array, size)

入力: データの配列と、その配列に含まれる要素の総数

出力: ソート済みの配列

Begin
    max := 配列から最大要素を取得する
    サイズ [max+1] のカウント配列 count を定義する

    for i := 0 to max do
        count[i] = 0 // カウント配列の全要素を 0 で初期化
    done

    for i := 1 to size do
        配列中に出現した各数値のカウントを 1 ずつ増やす
    done

    for i := 1 to max do
        count[i] = count[i] + count[i-1] // 累積度数を求める
    done

    for i := size down to 1 do
        出力配列の適切な位置に数値を格納する
        count[array[i]] を 1 減らす
    done

    出力配列を返す
End

動作のポイント

まず各値の出現回数を数え、次に累積度数を求めることで「その値以下の要素が何個あるか」が分かります。これにより各要素の最終的な位置が一意に決まります。出力時に配列を後ろから走査することで、同じ値を持つ要素の相対的な順序が保たれ、ソートの安定性が確保されます。

C++による実装例

#include<iostream>
#include<algorithm>
using namespace std;

// 配列の内容を表示する関数
void display(int *array, int size) {
    for(int i = 1; i<=size; i++)
        cout << array[i] << " ";
    cout << endl;
}

// 配列の最大値を求める関数
int getMax(int array[], int size) {
    int max = array[1];
    for(int i = 2; i<=size; i++) {
        if(array[i] > max)
            max = array[i];
    }
    return max; // 配列中の最大要素を返す
}

// カウントソート本体
void countSort(int *array, int size) {
    int output[size+1];
    int max = getMax(array, size);
    int count[max+1]; // カウント配列を作成（max+1 個の要素）

    for(int i = 0; i<=max; i++)
        count[i] = 0; // カウント配列をすべて 0 で初期化
    for(int i = 1; i <=size; i++)
        count[array[i]]++; // 各数値の出現回数をカウント
    for(int i = 1; i<=max; i++)
        count[i] += count[i-1]; // 累積度数を求める

    for(int i = size; i>=1; i--) {
        output[count[array[i]]] = array[i];
        count[array[i]] -= 1; // 同じ数値がある場合はカウントを減らす
    }

    for(int i = 1; i<=size; i++) {
        array[i] = output[i]; // 出力配列の内容を元の配列へコピー
    }
}

int main() {
    int n;
    cout << "要素数を入力してください: ";
    cin >> n;
    int arr[n+1]; // 指定された要素数の配列を作成
    cout << "要素を入力してください:" << endl;

    for(int i = 1; i<=n; i++) {
        cin >> arr[i];
    }

    cout << "ソート前の配列: ";
    display(arr, n);
    countSort(arr, n);
    cout << "ソート後の配列: ";
    display(arr, n);
}

実行結果

要素数を入力してください: 10
要素を入力してください:
2 5 6 2 3 10 3 6 7 8
ソート前の配列: 2 5 6 2 3 10 3 6 7 8
ソート後の配列: 2 2 3 3 5 6 6 7 8 10