C++でカウントソート（計数ソート）を実装する方法

カウントソートとは

カウントソート（計数ソート）は安定なソート手法の一つで、小さな整数値をキーとするデータを並べ替えるために用いられるアルゴリズムです。キー値が同じ要素の個数を数え、その情報をもとに整列を行うのが大きな特徴です。キー同士の差（値の範囲）がそれほど大きくなければ非常に高い効率を発揮しますが、範囲が広すぎる場合は空間計算量が増大する点に注意が必要です。

カウントソートの計算量

• 時間計算量：O(n+r)
• 空間計算量：O(n+r)

※ n は要素数、r はキーの最大値（値の範囲）を表します。

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

カウントソートの処理の流れ

1. 配列内の最大値を取得し、「最大値+1」のサイズでカウント配列を用意して、全要素を0で初期化します。
2. 元の配列を走査し、各値の出現回数をカウント配列に記録します。
3. カウント配列を累積和に変換することで、各要素がソート後に位置するインデックスを決定します。
4. 元の配列を後ろから走査しながら、累積度数に基づいて出力配列の適切な位置へ要素を配置し、配置するたびに対応するカウントを減らしていきます。

後ろから走査することで、同じ値を持つ要素の相対的な順序が保たれ、ソートの安定性が保証されます。

アルゴリズム（擬似コード）

countingSort(array, size)

入力： データの配列と、その総要素数
出力： ソート済みの配列

Begin
    max = 配列内の最大要素を取得
    サイズ [max+1] のカウント配列を宣言
    for i := 0 to max do
        count[i] = 0  // カウント配列の全要素を0に初期化
    done
    for i := 1 to size do
        配列中に見つかった各数値のカウントを増加させる
    done
    for i := 1 to max do
        count[i] = count[i] + count[i-1]  // 累積度数を求める
    done
    for i := size downto 1 do
        数値を出力配列に格納する
        対応するカウントを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 << "Enter the number of elements: ";
    cin >> n;
    int arr[n+1]; // 指定された要素数の配列を作成
    cout << "Enter elements:" << endl;
    for(int i = 1; i<=n; i++) {
        cin >> arr[i];
    }
    cout << "Array before Sorting: ";
    display(arr, n);
    countSort(arr, n);
    cout << "Array after Sorting: ";
    display(arr, n);
}

実行結果

Enter the number of elements: 10
Enter elements:
2 5 6 2 3 10 3 6 7 8
Array before Sorting: 2 5 6 2 3 10 3 6 7 8
Array after Sorting: 2 2 3 3 5 6 6 7 8 10

補足： 上記のコードでは可変長配列（VLA）を使用しています。これは GCC など一部のコンパイラでは利用できますが、C++の標準規格には含まれていないため、移植性を重視する場合は std::vector を使うことをおすすめします。また、カウントソートは比較ベースのソートではないため、クイックソートなどの O(n log n) のアルゴリズムよりも、キーの範囲が狭い場合には高速に動作します。