O(n)の計算量で100未満の数値をソートするC++プログラム：計数ソートの実装方法

少数の小さな数値を線形時間 O(n) でソートしたい場合、「計数ソート（Counting Sort／カウントソート）」という手法が非常に有効です。

計数ソートは安定なソートアルゴリズムの一つで、キーとなる値が小さな整数であるオブジェクトを整列するのに適しています。各キー値と同じ値を持つ要素の個数を数え上げ、その情報をもとに配列を再構築することでソートを実現します。キー同士の値の範囲（最大値との差）が小さい場合に高い効率を発揮しますが、範囲が大きすぎるとカウント用の配列が巨大化し、空間計算量が悪化する点には注意が必要です。

計数ソートの計算量

• 時間計算量：O(n + r)　※rはキー値の範囲（最大値）

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

入力 − ソートされていないデータ列：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 := 0 to size-1 do
        配列中に見つかった各数値の出現回数を count に加算する
    done
    j := 0
    for i := 0 to max do
        while count[i] > 0 do
            output[j] := i  // 数値を出力配列に格納
            j := j + 1
            count[i] := count[i] - 1
        done
    done
    return output
End

サンプルコード

以下は、C++で計数ソートを実装した完全なプログラム例です。まず配列内の最大値を求め、その値に応じたサイズのカウント配列を確保して各値の出現回数を数え、最後にカウント情報をもとに元の配列へ書き戻します。

#include <iostream>
using namespace std;

void counting_sort(int array[], int n) {
    // 配列内の最大値を求める
    int max = array[0];
    for (int i = 1; i < n; i++) {
        if (array[i] > max)
            max = array[i];
    }

    // カウント配列を確保し、すべて0で初期化
    int* count = new int[max + 1];
    for (int i = 0; i <= max; i++)
        count[i] = 0;

    // 各値の出現回数をカウント
    for (int i = 0; i < n; i++)
        count[array[i]]++;

    // カウント情報をもとに配列を再構築
    int j = 0;
    for (int i = 0; i <= max; i++) {
        while (count[i] > 0) {
            array[j++] = i;
            count[i]--;
        }
    }
    delete[] count;
}

int main() {
    int array[100], num;

    cout << "配列のサイズを入力してください : ";
    cin >> num;

    cout << "ソートする " << num << " 個の要素を入力してください :" << endl;
    for (int i = 0; i < num; i++)
        cin >> array[i];

    cout << "\nソート前の配列 :" << endl;
    for (int i = 0; i < num; i++)
        cout << array[i] << " ";

    counting_sort(array, num);

    cout << "\nソート後の配列 :" << endl;
    for (int i = 0; i < num; i++)
        cout << array[i] << " ";
    cout << endl;

    return 0;
}

実行結果

配列のサイズを入力してください : 8

ソートする 8 個の要素を入力してください :
54 89 23 20 18 88 65 31

ソート前の配列 :
54 89 23 20 18 88 65 31

ソート後の配列 :
18 20 23 31 54 65 88 89

まとめ

計数ソートの大きな特徴は、比較ベースのソート（クイックソートやマージソートなど）が持つ O(n log n) という理論的な下限を超えられる点です。ただしこれは、キーが小さな範囲の非負整数であるという前提があるため実現できるものであり、値の範囲が広いデータに対してはカウント配列が巨大化するため不向きです。100未満のような小さな整数キーを含む大量のデータを高速に整列したい場合に、ぜひ活用したい手法といえます。