package sorting;

public class CountingSort {
    public static void main(String[] args){
        int k = 20; // 最大可能數值 // k > n

        int[] ary = new int[]{4,4,13,10,7,12,9,9};

        System.out.println("Original: ");
        printAry(ary);

        // sorting
        int[] sortedAry = countingSort(ary, k);

        // 印出結果
        System.out.println("Sorted:");
        printAry(sortedAry);
    }

    /**
     * time complexity: O(N + 2K)
     * (n,k)
     * @param ary
     * @param maxVal
     * @return
     */
    private static int[] countingSort(int[] ary, int maxVal) {

        int[] count = new int[maxVal+1]; // 初始值即為零
        int[] sumCount = new int[maxVal+1];
        int[] sortedAry = new int[ary.length];

        // 計算各個值出現幾次 (O(n))
        for (int i = 0; i < ary.length; i++){
            Integer val = ary[i];
            count[val]++;
        }
        System.out.println("Counted:");
        printAry(count);

        // 算出sumCount (O(k))
        sumCount[0] = count[0];
        for (int i = 1; i < count.length; i++){
            sumCount[i] += (count[i] + sumCount[i-1]); // ("目前count[i]值" + "前一個sumCount[i]累積值")
        }
        System.out.println("sumCounted:");
        printAry(sumCount);

        // 放入結果ary中 (O(k))
        for (int i = 0; i < ary.length; i++){
            int value = ary[i];
            int indexForSortedAry = sumCount[value]--; // 拿完後要減掉,不然重複的值中,只會有一格一直被填
            sortedAry[indexForSortedAry-1] = value; // 若不減一，最後結果最前面會多一個0
        }

        return sortedAry;

    }

    private static void printAry(int[] ary){
        for (int i = 0; i < ary.length; i++){
            System.out.print(ary[i] + " ");
        }
        System.out.println();
    }

}
/**
 *
Original:
4 4 13 10 7 12 9 9
Counted:
0 0 0 0 2 0 0 1 0 2 1 0 1 1 0 0 0 0 0 0 0
sumCounted:
0 0 0 0 2 2 2 3 3 5 6 6 7 8 8 8 8 8 8 8 8
Sorted:
4 4 7 9 9 10 12 13
 */