public class Tugas2CountingSort {
    /** Membuat function sort, untuk mengurutkan array berdasarkan jumlah frekuensi **/
    void sort(char arr[]) {
        int n = arr.length;
        
        char output[] = new char[n];
        
        /** Array Count[] berfungsi untuk menyimpan jumlah kemunculan tiap karakter ASCII (0-255) **/
        int count[] = new int[256];
        
        System.out.println("\nStep 1 : Inisialisasi count[] ke 0");
        
        for(int i = 0; i < 256; ++i)
        {
            count[i] = 0;
        }
        
        System.out.println("Semua nilai count[i] di-set ke 0");
        
        
        System.out.println("\nStep 2 : Hitung Frekuensi karakter ASCII");
        
        for(int i = 0; i < n; i++)
        {
            ++count[arr[i]];
            System.out.printf("Karakter '%c' ditemukan, count['%c'] sekarang = %d\n", arr[i], arr[i], count[arr[i]]);
        }
        
        /** Menampilkan Frekuensi akhir tiap karakter yang ada **/
        System.out.println("\nFrekuensi akhir : ");
        
        for(int i = 0; i < 256; ++i)
        {
            if(count[i] > 0)
            {
                System.out.printf("  %c : %d kali\n", (char)i, count[i]);
            }
        }
        
        System.out.println("\nStep 3 : Buat Count Kumulatif (untuk menentukan posisi terakhir karakter");
        /** Membuat Count Kumulatif **/
        
        
        int lastCount = 1;
            
        for(int i = 1; i <= 255; ++i)
        {
            
            if(count[i] > 0)
            {
                
                System.out.println("Menkumulatifkan " + count[i] + " dengan " + count[i - 1] );
                count[i] += count[i - lastCount];
                
                lastCount = 1;
            } else {
                lastCount++;
            }
        }
        
        
        /** Cetak hasil Kumulatif karakter yang muncul **/
        System.out.println("Nilai count[] setelah kumulatif:");
        for(int i = 0; i < 256; ++i)
        {
            if(count[i] > 0)
            {
                System.out.printf("   %c : %d\n", (char)i, count[i]);
            }
        }
        
        
        System.out.println("\n Step 4: Penempatan ke output[] berdasarkan count kumulatif");
        /** Menyusun array output[] berdasarkan posisi akhir yang dihitung dari count[]
         * secara Descending
         */
        
        for(int i = n - 1; i >= 0; --i)
        {
            output[n- count[arr[i]]] = arr[i];
            
            int posisi = count[arr[i]] - 1;
            
            System.out.printf("i=%2d | arr[i]='%c' -> count['%c']=%2d -> output[%d]='%c'\n",
                    i, arr[i], arr[i], count[arr[i]], posisi, arr[i]);
            
            --count[arr[i]];
        }
        
       /** Tampilkan hasil output sementara **/
       System.out.println("\nHasil output[] setelah semua penempatan :");
       for(char c : output) System.out.print(c + " ");
       System.out.println();
       
       System.out.println("\nStep 5 : Salin output[] ke arr[]");
       /** Menyalin kembali hasil akhir dari output[] ke array utama arr[] **/
       for(int i = 0; i < n; i++)
       {
           arr[i] = output[i];
           System.out.printf("arr[%2d] = '%c'\n", i, arr[i]);
       }
       
       System.out.println("\nArray sudah terurut sepenuhnya secara descending");
       
        
    }
    
    public static void main(String args[]) {
        /** Deklarasi Variabel **/
        
        char a1 = 'g';
        char a2 = 'e';
        char a3 = 'e';
        char a4 = 'k';
        char a5 = 's';
        char a6 = 'f';
        char a7 = 'o';
        char a8 = 'r';
        char a9 = 'g';
        char a10 = 'e';
        char a11 = 'e';
        char a12 = 'k';
        char a13 = 's';
        
        char arr[] = {a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11, a12, a13};
        
        System.out.print("Array sebelum dilakukan sorting : ");
        for (char c : arr) System.out.print(c + " ");
        System.out.println();
        
        
        /** Membuat Variabel Tugas2CountingSort **/
        Tugas2CountingSort ob = new Tugas2CountingSort();
        
        /** Menjalankan function sort **/
        ob.sort(arr);
        
        
        
        System.out.print("\nSetelah dilakukan sorting secara Descending : ");
        for(char c : arr) System.out.print(c + " ");
        
        System.out.println();


       /** Analisa Algoritma Counting Sort **/
       String hasilAnalisa = """
                             ================================================
                              KESIMPULAN ALGORITMA COUNTING SORT
                             ================================================
                             Counting Sort adalah algoritma pengurutan non-komparatif
                             (tanpa perbandingan)yang bekerja dengan cara menghitung jumlah 
                             kemunculan tiap elemen.

                             Proses utama:
                             1. Inisialisasi array count[] berukuran 256 dengan nilai awal 0.
                             2. Hitung jumlah kemunculan setiap karakter dari array input.
                             3. Ubah count[] menjadi bentuk kumulatif untuk mengetahui posisi akhir.
                             4. Tempatkan elemen ke array output[] sesuai posisi kumulatif, 
                                dan disusun secara Descending
                             5. Salin hasil akhir dari output[] ke arr[].

                             Kelebihan:
                             - Sangat cepat untuk rentang data kecil.
                             - Tidak menggunakan perbandingan antar elemen.

                             Kekurangan:
                             - Membutuhkan memori tambahan (array count dan output).
                             - Tidak cocok untuk data dengan rentang nilai yang sangat besar.

                             Contoh hasil:
                             Array awal  : [g, e, e, k, s, f, o, r, g, e, e, k, s]
                             Hasil akhir : [s, s, r, o, k, k, g, g, f, e, e, e, e]
                             ================================================
                             """;
       
       System.out.println(hasilAnalisa);
        

    }
}