【C言語】Counting Sort（分布数えソート）の実装方法を解説：整数配列を効率よく並べ替える

本記事では、C言語を使って整数配列を効率的に並べ替えるCounting Sortの実装方法を紹介します。

分布数えソートの基本的な流れを丁寧に解説し、実際のコード例も交えて実践的な内容を提供します。

環境が整った方に向け、具体的な手順をシンプルに説明します。

Counting Sortの基本

Counting Sortとは

Counting Sortは、整数の配列を効率よく並べ替えるためのアルゴリズムの一つです。

配列内の各整数の出現回数を数え、その情報を元に並び順を決定します。

対象の数値がとる値の範囲が狭い場合、非常に高速に動作するのが特徴です。

アルゴリズムは安定ソートに分類され、同じ値の要素同士の順序が保たれる利点があります。

アルゴリズムの流れ

Counting Sortの基本的な流れは以下の通りです。

• 最大値の探索

ソート対象の配列から最大値(または最小値)を見つけ、カウント用の配列のサイズを決定します。

• 出現回数のカウント

各数値の出現回数を、対応するインデックスの配列に記録します。

$$count[i]=\text{対象配列中の}i\text{の出現回数}$$

• 累積和の計算

出現回数の配列から累積和を計算し、各数値が最終的な出力配列のどの位置に配置されるかを決めます。

$$cum[i]=\sum _{j=0}^{i}count[j]$$

• 出力配列への再配置

入力配列を逆順にスキャンして、各要素を累積和に基づいた適切な位置へ配置します。

これにより、安定なソートが実現されます。

C言語でのCounting Sort実装

プログラム全体の構成

Counting SortをC言語で実装する際は、以下の構成となります。

• main関数でソート対象の配列を定義し、Counting Sort関数を呼び出す
• Counting Sort処理を関数にまとめ、関数内で以下の処理を実施する：
  • 入力配列の準備
  • カウント配列の初期化
  • 出現回数の集計
  • 累積和の計算
  • 出力配列への再配置
• ソート結果を表示して、正しくソートされていることを確認する

入力配列の準備と出現回数のカウント

カウント配列の初期化

Counting Sortでは、入力される整数の範囲に応じたカウント配列を動的に確保する必要があります。

まずは、すべての要素を0で初期化します。

たとえば、最大値をmaxValueとすると、カウント配列はサイズmaxValue + 1で確保します。

出現回数の集計処理

初期化したカウント配列に対して、入力配列を1つずつ走査し、該当インデックスの値をインクリメントします。

この処理により、各整数の出現回数を正確にカウントすることができます。

累積和の計算と出力配列への再配置

累積和の計算方法

出現回数の配列から累積和を計算します。

具体的には、配列の先頭から順に、現在の値に前の要素の累積値を加えていきます。

数学的には、以下のように表現されます。

$$cum[i]=count[0]+count[1]+\cdots +count[i]$$

この累積和が、各要素を出力配列のどの位置に配置するかを決定します。

要素の再配置処理

入力配列を逆順に走査し、累積和を元に出力配列へ各要素を配置します。

配置が行われるたびに、累積和の該当位置の値を減算することで、次の同じ要素の配置位置を調整します。

この手順を踏むことで、ソートが安定であり、各要素の元の順序が保たれます。

ソースコードの主要ポイント解説

以下は、Counting SortをC言語で実装したサンプルコードです。

このコードは、入力配列の準備、カウント配列の初期化、出現回数のカウント、累積和の計算、および出力配列への再配置の各工程を含みます。

#include <stdio.h>
#include <stdlib.h>
// Counting Sortを実装する関数
void countingSort(int *input, int size) {
    int i;
    // 配列内の最大値を探索
    int maxValue = input[0];
    for(i = 1; i < size; i++) {
        if(input[i] > maxValue) {
            maxValue = input[i];
        }
    }
    // カウント配列の初期化(0で埋める)
    int *count = (int *)calloc(maxValue + 1, sizeof(int));
    if(count == NULL) {
        printf("メモリ確保に失敗しました\n");
        exit(EXIT_FAILURE);
    }
    // 出現回数の集計処理
    for(i = 0; i < size; i++) {
        count[input[i]]++;
    }
    // 累積和の計算
    for(i = 1; i <= maxValue; i++) {
        count[i] += count[i - 1];
    }
    // 出力配列の確保
    int *output = (int *)malloc(size * sizeof(int));
    if(output == NULL) {
        printf("メモリ確保に失敗しました\n");
        free(count);
        exit(EXIT_FAILURE);
    }
    // 安定ソートのために、入力配列を逆順に走査して出力配列に再配置
    for(i = size - 1; i >= 0; i--) {
        // 配置する位置を決定
        output[count[input[i]] - 1] = input[i];
        count[input[i]]--;
    }
    // 結果を入力配列にコピー(ソート済みとなる)
    for(i = 0; i < size; i++) {
        input[i] = output[i];
    }
    // 使用したメモリの解放
    free(count);
    free(output);
}
// main関数: プログラムのエントリーポイント
int main(void) {
    // ソート対象のサンプル配列(日本語のコメント付き)
    int array[] = {4, 2, 2, 8, 3, 3, 1};
    int size = sizeof(array) / sizeof(array[0]);
    // ソート前の出力
    printf("ソート前: ");
    for (int i = 0; i < size; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
    // Counting Sortの呼び出し
    countingSort(array, size);
    // ソート後の出力結果
    printf("ソート後: ");
    for (int i = 0; i < size; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
    return 0;
}

ソート前: 4 2 2 8 3 3 1
ソート後: 1 2 2 3 3 4 8

上記サンプルコードでは、必要な#include文を含め、main関数によってプログラムが実行できるようになっています。

コード中のコメントには、日本語で簡潔に各処理の目的や手順が記述されているため、理解しやすい構成となっています。

Counting Sort実装時の注意点

配列サイズとメモリ管理

Counting Sortでは、カウント配列のサイズが入力データの最大値に依存します。

入力配列の要素が非常に大きい場合、カウント配列が大きくなる可能性があるため、動的メモリ確保を行い、必要なメモリ量を事前に確認することが重要です。

また、動的に確保したメモリは、使用後に必ず解放するように注意してください。

入力データの制約とエラーチェック

Counting Sortは、通常、0以上の整数に対して効果的に動作します。

負の数が含まれる場合は、別途処理を行うか、アルゴリズムの改修が必要です。

さらに、配列のサイズやメモリ確保に失敗した場合のエラーチェックを適切に実装し、プログラムが予期せぬ状況でクラッシュしないようにすることが求められます。

テストケースと動作確認

テストケースの選定

Counting Sortのテストケースとしては、以下のポイントを網羅することが望ましいです。

• 通常ケース

例：ランダムな整数配列

• 境界ケース

例：すでにソート済みの配列、全ての要素が同じ配列

• 極端なケース

例：非常に大きな数値や、カウント配列のサイズが大きくなる場合

これらのテストケースを用いることで、アルゴリズムがさまざまな状況下で正しく動作することを確認できます。

実行結果の確認方法

ソースコード内でソート前とソート後の配列を標準出力に表示することで、正しくソートが行われたか確認することができます。

また、出力結果を事前に準備した期待値と比較するテストを自動化することで、コードの信頼性を向上させることが可能です。

まとめ

本記事では、整数配列を効率的にソートするCounting Sortの基本と、各工程(入力配列の準備、カウント配列の初期化、出現回数の集計、累積和計算および安定な再配置処理)の詳細を解説しています。

さらに、C言語での実装例を通じて、メモリ管理や入力データのエラーチェック、テストケースの選定と実行結果の確認方法について学ぶことができます。