Implementieren Sie den Zählsortieralgorithmus in Java

Veröffentlicht: 2023-01-30
Implementieren Sie den Zählsortieralgorithmus in Java

Was ist der Zählsortieralgorithmus?

Counting sort, ein Sortieralgorithmus, der für small ranges of integers effizient ist. Es funktioniert, indem es die Anzahl der Vorkommen jedes Werts im Eingabearray zählt und dann diese Informationen verwendet, um jeden Wert an seiner richtigen Position im Ausgabearray zu platzieren.

Die Zeitkomplexität dieses Algorithmus ist O(n+k) , wobei n die Größe des Eingabearrays und k der Bereich der ganzen Zahlen ist.

CrunchifyCountingSortAlgo.java

Hier ist eine vollständige Implementierung von Counting Sort in Java. Kopieren Sie es einfach in Ihre bevorzugte IDEA und führen Sie es aus.

 Paket crunchify.com.java.tutorials;

java.util.Arrays importieren;

/**
 * @Autor Crunchify.com
 * Programm: Wie implementiert man den Zählsortieralgorithmus in Java?
 * Countingsort ist ein Sortieralgorithmus, der die Elemente eines Arrays sortiert 
 * durch Zählen der Anzahl der Vorkommen jedes eindeutigen Elements im Array.
 */

öffentliche Klasse CrunchifyCountingSortAlgo {

    public static void main(String[] args) {

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

        crunchifyPrint("Ursprüngliches Array: " + Arrays.toString(crunchifyArray));
        crunchifyPrint ("\n");

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

        crunchifyPrint ("\n");
        crunchifyPrint("Ergebnis des Crunchify-Zählalgorithmus: " + Arrays.toString(crunchifyArray));
    }

    private statische void crunchifyPrint(String s) {

        System.out.println(s);
    }


    /**
     * Autor: App Shah (Crunchify.com)
     *
     * Sortierlogik zählen:
     * Dies ist eine Implementierung von Counting Sort, einem Sortieralgorithmus, der für kleine Bereiche von Ganzzahlen effizient ist.
     * Es funktioniert, indem die Anzahl der Vorkommen jedes Werts im Eingabearray gezählt wird.
     * und dann diese Informationen verwenden, um jeden Wert an der richtigen Position im Ausgabearray zu platzieren.
     * Die Zeitkomplexität dieses Algorithmus ist O(n+k),
     * wobei n die Größe des Eingabearrays und k der Bereich der ganzen Zahlen ist.
     */


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

        // getAsInt(): Wenn ein Wert vorhanden ist, wird der Wert zurückgegeben, andernfalls wirft NoSuchElementException.
        int crunchifyMax = Arrays.stream(crunchifyArray).max().getAsInt();
        int[] crunchifyCount = new int[crunchifyMax + 1];

        // crunchifyCount die Vorkommen jedes Werts im Eingabearray
        for (int i = 0; i < crunchifyArray.length; i++) {
            crunchifyCount[crunchifyArray[i]]++;
            crunchifyPrint("Hinzufügen von 1 zu crunchifyCount[" + crunchifyArray[i] 
                    + "], crunchifyCount-Array ist jetzt: " + Arrays.toString(crunchifyCount));
        }

        crunchifyPrint ("\n");

        Ganzzahl k = 0;
        for (int i = 0; i <= crunchifyMax; i++) {
            for (int j = 0; j < crunchifyCount[i]; j++) {
                crunchifyArray[k++] = i;
                crunchifyPrint("Hinzufügen von " + i + " an Position " + (k - 1) 
                        + " im Ausgabearray, Ausgabearray ist jetzt: " + Arrays.toString(crunchifyArray));
            }
        }

        crunchifyArray zurückgeben;
    }

}

Führen Sie einfach das obige Programm als Java-Anwendung in IntelliJ IDEA oder Eclipse IDE aus und Sie erhalten das folgende Ergebnis.

Ergebnis der IntelliJ IDEA-Konsole

 Ursprüngliches Array: [9, 3, 6, 6, 1, 12, 32, 29, 2, 9, 3]


Durch Hinzufügen von 1 zu crunchifyCount[9] ist das crunchifyCount-Array jetzt: [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]
Durch Hinzufügen von 1 zu crunchifyCount[3] ist das crunchifyCount-Array jetzt: [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]
Durch Hinzufügen von 1 zu crunchifyCount[6] ist das crunchifyCount-Array jetzt: [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]
Durch Hinzufügen von 1 zu crunchifyCount[6] ist das crunchifyCount-Array jetzt: [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]
Durch Hinzufügen von 1 zu crunchifyCount[1] ist das crunchifyCount-Array jetzt: [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]
Durch Hinzufügen von 1 zu crunchifyCount[12] ist das crunchifyCount-Array jetzt: [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]
Durch Hinzufügen von 1 zu crunchifyCount[32] ist das crunchifyCount-Array jetzt: [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]
Durch Hinzufügen von 1 zu crunchifyCount[29] ist das crunchifyCount-Array jetzt: [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]
Durch Hinzufügen von 1 zu crunchifyCount[2] ist das crunchifyCount-Array jetzt: [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]
Durch Hinzufügen von 1 zu crunchifyCount[9] ist das crunchifyCount-Array jetzt: [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]
Durch Hinzufügen von 1 zu crunchifyCount[3] ist das crunchifyCount-Array jetzt: [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]


Hinzufügen von 1 zu Position 0 im Ausgabearray, Ausgabearray ist jetzt: [1, 3, 6, 6, 1, 12, 32, 29, 2, 9, 3]
Hinzufügen von 2 zu Position 1 im Ausgabearray, Ausgabearray ist jetzt: [1, 2, 6, 6, 1, 12, 32, 29, 2, 9, 3]
Hinzufügen von 3 zu Position 2 im Ausgabearray, Ausgabearray ist jetzt: [1, 2, 3, 6, 1, 12, 32, 29, 2, 9, 3]
Hinzufügen von 3 zu Position 3 im Ausgabearray, Ausgabearray ist jetzt: [1, 2, 3, 3, 1, 12, 32, 29, 2, 9, 3]
Hinzufügen von 6 zu Position 4 im Ausgabearray, Ausgabearray ist jetzt: [1, 2, 3, 3, 6, 12, 32, 29, 2, 9, 3]
Hinzufügen von 6 zu Position 5 im Ausgabearray, Ausgabearray ist jetzt: [1, 2, 3, 3, 6, 6, 32, 29, 2, 9, 3]
Hinzufügen von 9 zu Position 6 im Ausgabearray, Ausgabearray ist jetzt: [1, 2, 3, 3, 6, 6, 9, 29, 2, 9, 3]
Hinzufügen von 9 zu Position 7 im Ausgabearray, Ausgabearray ist jetzt: [1, 2, 3, 3, 6, 6, 9, 9, 2, 9, 3]
Hinzufügen von 12 zu Position 8 im Ausgabearray, Ausgabearray ist jetzt: [1, 2, 3, 3, 6, 6, 9, 9, 12, 9, 3]
Hinzufügen von 29 zu Position 9 im Ausgabearray, Ausgabearray ist jetzt: [1, 2, 3, 3, 6, 6, 9, 9, 12, 29, 3]
Hinzufügen von 32 zu Position 10 im Ausgabearray, Ausgabearray ist jetzt: [1, 2, 3, 3, 6, 6, 9, 9, 12, 29, 32]


Ergebnis des Crunchify-Zählalgorithmus: [1, 2, 3, 3, 6, 6, 9, 9, 12, 29, 32]

Prozess beendet mit Exit-Code 0
Implementieren Sie den Zählsortieralgorithmus in Java – Ergebnis von IntelliJ IDEA

Lassen Sie mich wissen, wenn Sie auf ein Problem stoßen, das über dem Java-Programm „Counting Sort Algorithm“ ausgeführt wird.