Java でカウント ソート アルゴリズムを実装する

カウンティングソートアルゴリズムとは？

small ranges of integers効率的なソート アルゴリズムであるカウント ソート。 これは、入力配列内の各値の出現回数をカウントし、その情報を使用して各値を出力配列内の正しい位置に配置することによって機能します。

このアルゴリズムの時間計算量はO(n+k)です。ここで、n は入力配列のサイズ、k は整数の範囲です。

CrunchifyCountingSortAlgo.java

これは Java での Counting Sort の完全な実装です。 好みの IDEA にコピーして実行するだけです。

 パッケージcrunchify.com.java.tutorials;

java.util.Arrays をインポートします。

/**
 * @著者 Crunchify.com
 * プログラム: Java でカウンティング ソート アルゴリズムを実装するには?
 ※カウンティングソートは、配列の要素をソートするソートアルゴリズムです。 
 * 配列内の一意の各要素の出現回数をカウントすることによって。
 */

public class CrunchifyCountingSortAlgo {

    public static void main(String[] args) {

        // 10 要素の整数配列
        int[] crunchifyArray = {9, 3, 6, 6, 1, 12, 32, 29, 2, 9, 3};

        crunchifyPrint("元の配列: " + Arrays.toString(crunchifyArray));
        crunchifyPrint ("\n");

        CrunchifyCountingSortAlgo crunchify = new CrunchifyCountingSortAlgo();
        crunchify.crunchifyCountingSortAlgorithm(crunchifyArray);

        crunchifyPrint ("\n");
        crunchifyPrint("Crunchify Counting Sort Algorithm の結果: " + Arrays.toString(crunchifyArray));
    }

    private static void crunchifyPrint(String s) {

        System.out.println(s);
    }


    /**
     * 著者: App Shah (Crunchify.com)
     *
     * 並べ替えロジックのカウント:
     * これは、小さな範囲の整数に対して効率的なソート アルゴリズムであるカウント ソートの実装です。
     * 入力配列内の各値の出現回数をカウントすることで機能します。
     * 次に、その情報を使用して、各値を出力配列の正しい位置に配置します。
     * このアルゴリズムの時間計算量は O(n+k) です。
     * ここで、n は入力配列のサイズ、k は整数の範囲です。
     */


    public static int[] crunchifyCountingSortAlgorithm(int[] crunchifyArray) {

        // getAsInt(): 値が存在する場合は値を返し、それ以外の場合は NoSuchElementException をスローします。
        int crunchifyMax = Arrays.stream(crunchifyArray).max().getAsInt();
        int[] crunchifyCount = new int[crunchifyMax + 1];

        // 入力配列内の各値の出現回数を crunchifyCount します
        for (int i = 0; i < crunchifyArray.length; i++) {
            crunchifyCount[crunchifyArray[i]]++;
            crunchifyPrint("crunchifyCount[" + crunchifyArray[i] に 1 を追加します。 
                    + "]、crunchifyCount 配列は次のようになりました: " + Arrays.toString(crunchifyCount));
        }

        crunchifyPrint ("\n");

        int k = 0;
        for (int i = 0; i <= crunchifyMax; i++) {
            for (int j = 0; j < crunchifyCount[i]; j++) {
                CrunchifyArray[k++] = i;
                crunchifyPrint("位置に " + i + " を追加 " + (k - 1) 
                        + " 出力配列で、出力配列は次のようになります: " + Arrays.toString(crunchifyArray));
            }
        }

        crunchifyArray を返します。
    }

}

上記のプログラムを IntelliJ IDEA または Eclipse IDE で Java アプリケーションとして実行すると、以下のようになります。

IntelliJ IDEA コンソールの結果

元の配列: [9, 3, 6, 6, 1, 12, 32, 29, 2, 9, 3]


crunchifyCount[9] に 1 を追加すると、crunchifyCount 配列は [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
crunchifyCount[3] に 1 を追加すると、crunchifyCount 配列は [0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
crunchifyCount[6] に 1 を追加すると、crunchifyCount 配列は [0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
crunchifyCount[6] に 1 を追加すると、crunchifyCount 配列は [0, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
crunchifyCount[1] に 1 を追加すると、crunchifyCount 配列は [0, 1, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
crunchifyCount[12] に 1 を追加すると、crunchifyCount 配列は [0, 1, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
crunchifyCount[32] に 1 を追加すると、crunchifyCount 配列は [0, 1, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
crunchifyCount[29] に 1 を追加すると、crunchifyCount 配列は [0, 1, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1]
crunchifyCount[2] に 1 を追加すると、crunchifyCount 配列は [0, 1, 1, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1]
crunchifyCount[9] に 1 を追加すると、crunchifyCount 配列は [0, 1, 1, 1, 0, 0, 2, 0, 0, 2, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1]
crunchifyCount[3] に 1 を追加すると、crunchifyCount 配列は [0, 1, 1, 2, 0, 0, 2, 0, 0, 2, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1]


出力配列の位置 0 に 1 を追加すると、出力配列は [1, 3, 6, 6, 1, 12, 32, 29, 2, 9, 3] になります。
出力配列の位置 1 に 2 を追加すると、出力配列は次のようになります: [1, 2, 6, 6, 1, 12, 32, 29, 2, 9, 3]
出力配列の位置 2 に 3 を追加すると、出力配列は [1, 2, 3, 6, 1, 12, 32, 29, 2, 9, 3] になります。
出力配列の位置 3 に 3 を追加すると、出力配列は [1, 2, 3, 3, 1, 12, 32, 29, 2, 9, 3] になります。
出力配列の位置 4 に 6 を追加すると、出力配列は [1, 2, 3, 3, 6, 12, 32, 29, 2, 9, 3] になります。
出力配列の位置 5 に 6 を追加すると、出力配列は [1, 2, 3, 3, 6, 6, 32, 29, 2, 9, 3] になります。
出力配列の位置 6 に 9 を追加すると、出力配列は [1, 2, 3, 3, 6, 6, 9, 29, 2, 9, 3] になります。
出力配列の位置 7 に 9 を追加すると、出力配列は [1, 2, 3, 3, 6, 6, 9, 9, 2, 9, 3] になります。
出力配列の位置 8 に 12 を追加すると、出力配列は [1, 2, 3, 3, 6, 6, 9, 9, 12, 9, 3] になります。
出力配列の位置 9 に 29 を追加すると、出力配列は [1, 2, 3, 3, 6, 6, 9, 9, 12, 29, 3] になります。
出力配列の位置 10 に 32 を追加すると、出力配列は [1, 2, 3, 3, 6, 6, 9, 9, 12, 29, 32] になります。


Crunchifyカウントソートアルゴリズムの結果: [1, 2, 3, 3, 6, 6, 9, 9, 12, 29, 32]

プロセスは終了コード 0 で終了しました

上記の Counting Sort Algorithm Java プログラムで問題が発生した場合はお知らせください。