Mengimplementasikan Algoritma Penghitungan Pengurutan di Java

Diterbitkan: 2023-01-30
Mengimplementasikan Algoritma Penghitungan Pengurutan di Java

Apa itu Menghitung Algoritma Sortir?

Penghitungan sortir, algoritme pengurutan yang efisien untuk small ranges of integers . Ini bekerja dengan menghitung jumlah kemunculan setiap nilai dalam larik masukan, dan kemudian menggunakan informasi tersebut untuk menempatkan setiap nilai pada posisi yang benar dalam larik keluaran.

Kompleksitas waktu dari algoritma ini adalah O(n+k) , di mana n adalah ukuran larik input dan k adalah rentang bilangan bulat.

CrunchifyCountingSortAlgo.java

Berikut adalah implementasi lengkap Counting Sort di Java. Cukup salin ke IDEA pilihan Anda dan jalankan.

 paket crunchify.com.java.tutorials;

import java.util.Arrays;

/**
 * @penulis Crunchify.com
 * Program: Bagaimana mengimplementasikan Algoritma pengurutan penghitungan di java?
 * Menghitung pengurutan adalah algoritma pengurutan yang mengurutkan elemen-elemen array 
 * dengan menghitung jumlah kemunculan setiap elemen unik dalam larik.
 */

kelas publik CrunchifyCountingSortAlgo {

    public static void main(String[] args) {

        // Integer Array dari 10 elemen
        int[] crunchifyArray = {9, 3, 6, 6, 1, 12, 32, 29, 2, 9, 3};

        crunchifyPrint("Array Asli: " + Arrays.toString(crunchifyArray));
        crunchifyPrint ("\n");

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

        crunchifyPrint ("\n");
        crunchifyPrint("Hasil Algoritma Penghitungan Crunchify: " + Arrays.toString(crunchifyArray));
    }

    private static void crunchifyPrint(String s) {

        System.out.println(s);
    }


    /**
     * Penulis: App Shah (Crunchify.com)
     *
     * Menghitung Sortir Logika:
     * Ini adalah implementasi dari counting sort, sebuah algoritma sorting yang efisien untuk rentang bilangan bulat kecil.
     * Ini bekerja dengan menghitung jumlah kemunculan setiap nilai dalam array input,
     * dan kemudian menggunakan informasi itu untuk menempatkan setiap nilai pada posisi yang benar dalam larik keluaran.
     * Kompleksitas waktu dari algoritma ini adalah O(n+k),
     * di mana n adalah ukuran larik input dan k adalah rentang bilangan bulat.
     */


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

        // getAsInt(): Jika ada nilai, kembalikan nilainya, jika tidak, lempar NoSuchElementException.
        int crunchifyMax = Arrays.stream(crunchifyArray).max().getAsInt();
        int[] crunchifyCount = new int[crunchifyMax + 1];

        // crunchifyHitung kemunculan setiap nilai dalam larik masukan
        for (int i = 0; i < crunchifyArray.length; i++) {
            crunchifyCount[crunchifyArray[i]]++;
            crunchifyPrint("Menambahkan 1 ke crunchifyCount[" + crunchifyArray[i] 
                    + "], array crunchifyCount sekarang: " + 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("Menambahkan " + i + " ke posisi " + (k - 1) 
                        + " dalam larik keluaran, larik keluaran sekarang adalah: " + Arrays.toString(crunchifyArray));
            }
        }

        kembali crunchifyArray;
    }

}

Jalankan saja program di atas sebagai Aplikasi Java di IntelliJ IDEA atau Eclipse IDE dan Anda akan mendapatkan hasil seperti di bawah ini.

Hasil Konsol IntelliJ IDEA

 Larik Asli: [9, 3, 6, 6, 1, 12, 32, 29, 2, 9, 3]


Menambahkan 1 ke crunchifyCount[9], larik crunchifyCount sekarang: [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, 0]
Menambahkan 1 ke crunchifyCount[3], larik crunchifyCount sekarang: [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]
Menambahkan 1 ke crunchifyCount[6], larik crunchifyCount sekarang: [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]
Menambahkan 1 ke crunchifyCount[6], larik crunchifyCount sekarang: [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]
Menambahkan 1 ke crunchifyCount[1], larik crunchifyCount sekarang: [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]
Menambahkan 1 ke crunchifyCount[12], larik crunchifyCount sekarang: [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]
Menambahkan 1 ke crunchifyCount[32], larik crunchifyCount sekarang: [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]
Menambahkan 1 ke crunchifyCount[29], larik crunchifyCount sekarang: [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]
Menambahkan 1 ke crunchifyCount[2], larik crunchifyCount sekarang: [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]
Menambahkan 1 ke crunchifyCount[9], larik crunchifyCount sekarang: [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]
Menambahkan 1 ke crunchifyCount[3], larik crunchifyCount sekarang: [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]


Menambahkan 1 ke posisi 0 dalam larik keluaran, larik keluaran sekarang: [1, 3, 6, 6, 1, 12, 32, 29, 2, 9, 3]
Menambahkan 2 ke posisi 1 dalam larik keluaran, larik keluaran sekarang: [1, 2, 6, 6, 1, 12, 32, 29, 2, 9, 3]
Menambahkan 3 ke posisi 2 dalam larik keluaran, larik keluaran sekarang: [1, 2, 3, 6, 1, 12, 32, 29, 2, 9, 3]
Menambahkan 3 ke posisi 3 dalam larik keluaran, larik keluaran sekarang: [1, 2, 3, 3, 1, 12, 32, 29, 2, 9, 3]
Menambahkan 6 ke posisi 4 dalam larik keluaran, larik keluaran sekarang: [1, 2, 3, 3, 6, 12, 32, 29, 2, 9, 3]
Menambahkan 6 ke posisi 5 dalam larik keluaran, larik keluaran sekarang: [1, 2, 3, 3, 6, 6, 32, 29, 2, 9, 3]
Menambahkan 9 ke posisi 6 dalam larik keluaran, larik keluaran sekarang: [1, 2, 3, 3, 6, 6, 9, 29, 2, 9, 3]
Menambahkan 9 ke posisi 7 dalam larik keluaran, larik keluaran sekarang: [1, 2, 3, 3, 6, 6, 9, 9, 2, 9, 3]
Menambahkan 12 ke posisi 8 dalam larik keluaran, larik keluaran sekarang: [1, 2, 3, 3, 6, 6, 9, 9, 12, 9, 3]
Menambahkan 29 ke posisi 9 dalam larik keluaran, larik keluaran sekarang: [1, 2, 3, 3, 6, 6, 9, 9, 12, 29, 3]
Menambahkan 32 ke posisi 10 dalam larik keluaran, larik keluaran sekarang: [1, 2, 3, 3, 6, 6, 9, 9, 12, 29, 32]


Hasil Algoritma Urutan Menghitung Crunchify: [1, 2, 3, 3, 6, 6, 9, 9, 12, 29, 32]

Proses selesai dengan kode keluar 0
Terapkan Algoritma Penghitungan Penghitungan di Java - Hasil IntelliJ IDEA

Beri tahu saya jika Anda menghadapi masalah apa pun yang menjalankan program Java Algoritma Penghitungan Penghitungan.