TugasCountingSort.java

package id.ac.ut.praktikumstrukturdata.modul6;

/**
 *
 * @author Zain
 */

public class TugasCountingSort {

    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("Sebelum sorting : ");
        for (char c : arr) System.out.print(c + " ");
        System.out.println();

        /** Membuat Variabel TugasCountingSort **/
        TugasCountingSort ob = new TugasCountingSort();

        /** Menjalankan Sort Counting secara Descending **/
        ob.sort(arr);


        System.out.print("\nSetelah sorting secara Descending : ");
        for (char c : arr) System.out.print(c + " ");
        System.out.println();

    }

    /** Function untuk melakukan sorting **/
    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");
        /** Inisialisasi count[] menjadi 0 **/
        /** 256 adalah total karakter ASCII **/
        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");
        /** Menghitung Jumlah Kemunculan tiap Karakter di Array Input arr[] **/
        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 (Posisi Terakhir Karakter)**/
        for(int i = 1; i <= 255 ; ++i){

            if (count[i] > 0) {
                count[i] += count[i - 1];
            }

        }



        /* Cetak hasil kumulatif untuk 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("\nStep 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[%2d]='%c'\n",
                    i, arr[i], arr[i], count[arr[i]], posisi, arr[i]);

            --count[arr[i]];
        }


        /** Tampilkan hasil output sementara **/
        System.out.print("\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!");


        /** 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);

    }



}