Javaでカウンティングソート（計数ソート）を実装するプログラム

カウンティングソート（Counting Sort：計数ソート）は、異なるキー値を持つ要素がそれぞれいくつ存在するかを数え上げることで、整列を行うソートアルゴリズムです。比較ベースのソートとは異なり、要素同士を直接比較せずに出現回数を集計して並べ替えるため、値の範囲が限られているデータに対して高速に動作します。

注意： 以下のコードは、負の数を含む配列にも対応しています。

サンプルコード

import java.util.*;
public class Demo{
    static void count_sort(int[] arr){
        int max_val = Arrays.stream(arr).max().getAsInt();
        int min_val = Arrays.stream(arr).min().getAsInt();
        int range = max_val - min_val + 1;
        int count[] = new int[range];
        int result[] = new int[arr.length];
        for (int i = 0; i < arr.length; i++){
            count[arr[i] - min_val]++;
        }
        for (int i = 1; i < count.length; i++){
            count[i] += count[i - 1];
        }
        for (int i = arr.length - 1; i >= 0; i--){
            result[count[arr[i] - min_val] - 1] = arr[i];
            count[arr[i] - min_val]--;
        }
        for (int i = 0; i < arr.length; i++){
            arr[i] = result[i];
        }
    }
    static void printVal(int[] arr){
        for (int i = 0; i < arr.length; i++){
            System.out.print(arr[i] + " ");
        }
        System.out.println("");
    }
    public static void main(String[] args){
        int[] arr = {-5, 0, -3, 8, 34, 56, 89, -11, -95, -1, 10};
        System.out.println("The array contains");
        for (int i = 0; i < arr.length; i++){
            System.out.print(arr[i] + " ");
        }
        System.out.println();
        System.out.println("Implementing Counting Sort in Java results in : ");
        count_sort(arr);
        printVal(arr);
    }
}

実行結果

The array contains
-5 0 -3 8 34 56 89 -11 -95 -1 10
Implementing Counting Sort in Java results in :
-95 -11 -5 -3 -1 0 8 10 34 56 89

コードの解説

Demo クラスには count_sort メソッドが定義されており、ここで実際のソート処理が行われます。処理の流れは以下の通りです。

1. 最大値・最小値の取得と範囲の計算

まず Arrays.stream() を使って配列内の最大値と最小値を求め、その差から値の範囲（range）を計算します。最小値を引くことで、負の数が含まれる場合でもインデックスとして扱えるようにしています。

2. 出現回数のカウント

配列を先頭から順に走査し、各要素の出現回数を count 配列に記録していきます。

3. 累積カウントの作成

次に count 配列を走査し、直前の値を現在の値に加算することで累積和を作成します。これにより、各要素がソート後のどの位置に配置されるべきかが決まります。

4. 結果配列への配置

元の配列を後ろから走査し、各要素を result 配列の適切な位置に格納すると同時に、対応するカウント値を減少させていきます。後ろから処理することで、ソートの安定性が保たれます。

5. 元の配列への反映

最後に result 配列の内容を元の配列にコピーして、ソート完了となります。

また、printVal メソッドは配列の内容をコンソールに出力するための補助関数です。main メソッドでは負の数を含むテスト用の配列を定義し、count_sort を呼び出してソートを実行しています。

計算量について

カウンティングソートの時間計算量は O(n + k)、空間計算量は O(n + k) です（n は要素数、k は値の範囲）。値の範囲が狭いデータに対しては非常に効率的ですが、範囲が極端に広い場合はメモリ消費が大きくなる点に注意が必要です。