Was ist Counting Sort?

Counting Sort ist ein effizienter Sortieralgorithmus, der besonders dann nützlich ist, wenn die zu sortierenden Elemente einen begrenzten Bereich von Werten haben. Im Gegensatz zu vergleichsbasierten Sortieralgorithmen wie Quicksort oder Mergesort, die ihre Laufzeit durch Vergleiche zwischen Elementen bestimmen, basiert Counting Sort auf der Zählung der Vorkommen jedes einzelnen Elements.

Funktionsweise am Beispiel des Arrays

[3, 2, 5, 0, 0, 2]

Initialisierung des Counting-Arrays: Wir beginnen damit, ein Hilfsarray, das sogenannte Counting-Array, zu initialisieren. Die Länge dieses Arrays wird durch den maximalen Wert im gegebenen Array plus eins bestimmt. Für unser Beispiel-Array [3, 2, 5, 0, 0, 2] wäre die Länge des Counting-Arrays also 6.

Zählen der Elemente:

1. Schritt Wir starten beim ersten Element des Arrays den wir sortieren wollen (hier ArrayToCount). Dieses Element hat jetzt den Wert 3. Wir inkrementieren den Zähler im Counting-Array an der Position 3 um eins.

2. Schritt Wir gehen zum nächsten Element im Array: 2. Wir inkrementieren den Zähler im Counting-Array an der Position 2 um eins.

3. Schritt wieder das gleiche Spiel...

4. Schritt

5. Schritt

6. Schritt

7. Schritt

Wir haben nun alle Elemente gezählt und wissen, wie viele Elemente von jedem Wert im zu sortierenden Array vorhanden sind.

Als nächstes erzeugen wir den sortierten Array aus unserem Count-Array. Dazu gehen wir wie folgt vor:

• Wir erstellen ein neues Array, in das wir die sortierten Elemente einfügen werden.
• Für jedes Element im Counting-Array: Wenn der Zähler größer als 0 ist, x-Element (wobei x dem Zähler entspricht) an das Ende des sortierten Array ein und gehen zum nächsten Element im Counting-Array, mit dem Wert ungleich 0. Dabei behalten wir die ganze Zeit das jetzige Ende des sortierten Arrays im Auge.

1. Schritt

2. Schritt

3. Schritt

4. Schritt

5. Schritt

6. Schritt

Nun haben wir den sortierten Array [0, 0, 2, 2, 3, 5] erhalten.

Laufzeit- und Platzkomplexität

Die Laufzeitkomplexität von Counting Sort beträgt O(n + k), wobei n die Anzahl der Elemente im zu sortierenden Array ist und k der Wertebereich der Elemente. Die Platzkomplexität beträgt ebenfalls O(n + k), da wir zusätzlichen Speicher für das Counting-Array benötigen.

Counting Sort in Python implementieren

Kompletter Code

def countingSort(arr):
    # Find the maximum value in the array
    max_val = max(arr)
    
    # Initialize the counting array
    count = [0] * (max_val + 1)
    
    # Count the occurrences of each element
    for num in arr:
        count[num] += 1
    
    # Build the sorted array
    sorted_arr = []
    for i in range(len(count)):
        while count[i] > 0:
            sorted_arr.append(i)
            count[i] -= 1
    
    return sorted_arr

Die Funktion countingSort nimmt ein unsortiertes Array arr als Eingabe.

Zuerst wird die maximale Wert im Array arr gefunden, um die Länge des Counting-Arrays zu bestimmen.

Dann wird ein Counting-Array count initialisiert, das die Anzahl der Vorkommen jedes Elements im Eingabearray arr speichert. Die Länge des Counting-Arrays wird durch max_val + 1 bestimmt.

Der Code zählt die Vorkommen jedes Elements im Eingabearray, indem er durch das Array arr iteriert und den entsprechenden Zähler im Counting-Array inkrementiert.

Nachdem alle Elemente gezählt wurden, wird das sortierte Array sorted_arr initialisiert.

Anschließend durchläuft der Code das Counting-Array und fügt jedes Element entsprechend seiner Anzahl im Counting-Array in das sortierte Array ein. Dabei wird das Element so oft hinzugefügt, wie es im Counting-Array gezählt wurde.

Schließlich wird das sortierte Array zurückgegeben.