Counting Sort

Die Noten Deiner Informatik-Klausur sind draußen – nun wollen Du und Deine Kommilitonen wissen, wie die Punkteverteilung aussieht. Dein Professor gibt Dir dafür eine unsortierte Liste mit Daten. Du entschließt Dich dazu, erst mal zu zählen, wie viele Daten es überhaupt sind und anschließend zu schauen, wie oft welche Punktzahl vorkommt.

Notierst Du Dir Ganze, hast Du im Grunde schon die Hälfte des Counting Sort Algorithmus durchgeführt. Wie Du die Liste nach dem Sortieralgorithmus jetzt noch sortieren kannst, erfährst Du in dieser Erklärung.

Counting Sort erklärt

Das Prinzip hinter Counting Sort ist es, Elemente mit unterschiedlichen Schlüsselwerten zu zählen und diese anschließend in einer sortierten Liste abzubilden. Wie das Ganze abläuft, findest Du anhand eines Beispiels nach der Definition erklärt.

Counting Sort Definition

Beachte, dass es sich bei den zugeordneten Schlüsseln immer um natürliche Zahlen handeln muss. Falls Du Dich jetzt fragen solltest, ob Du mit Counting Sort nur Zahlen sortieren kannst – das ist nicht der Fall. Es ist auch möglich z. B. Adressen zu sortieren, indem Du ihnen eine Referenz in Form einer ganzen natürlichen Zahl zuweist, diese dann sortierst und später wieder entschlüsselst.

Counting Sort Algorithmus

Am einfachsten lässt sich der Counting Sort Algorithmus durch ein Beispiel veranschaulichen. Gegeben ist folgendes Array:

1. Schritt: Zählen der Elemente

Im ersten Schritt werden ein Index und eine Hilfsarray angelegt. Der Index geht in diesem Fall von 0 bis 9, das Hilfsarray wird zunächst mit Nullen gefüllt.

Anschließend zählst Du, wie oft die jeweiligen Zahlenwerte im gegebenen Array vorkommen und trägst diese Zahl im Hilfsarray ein.

2. Schritt: Elemente aufsummieren

Summiere nun die Elemente des Hilfsarrays von links nach rechts auf – also addiere zu jedem Feld den Wert des linken Nachbarfelds. Du beginnst im Beispiel beim Index 1.

Mit diesem Schritt ist das Zählen abgeschlossen – nun können die Elemente sortiert werden.

3. Schritt: Elemente sortieren

Für das Einsortieren wird ein Zielarray angelegt. Der Platzhalter sagt aus, wie viele Elemente sortiert werden und dient einfach als Hilfe – in diesem Fall sind es die Zahlen 1 bis 8, da das gegebene Array acht Elemente enthält.

Gehe jetzt durch Dein unsortiertes Array durch und schreibe das Element im Zielarray an die Position, die im Hilfsarray steht.

Schaue Dir also zunächst den Index 3 an. Dort steht eine 3, also schreibst Du die 3 an die Stelle 3 in das Zielarray. Zusätzlich reduzierst Du den Wert im entsprechenden Hilfsarray um 1.

Als Nächstes kommt die 2 dran: Die 2 hat den Wert 2 und wird entsprechend an die zweite Stelle im Zielarray geschrieben. Verringere anschließend wieder den Wert im Hilfsarray um 1.

Gehe das restliche Array nach dem gleichen Prinzip durch. Noch einmal interessant wird es bei der zweiten 2. Da Du den Wert im Hilfsarray vorhin um 1 reduziert hast, landet die zweite 2 nun an der Stelle 1 im Zielarray.

Führe den Algorithmus nun noch zu Ende durch.

Fertig ist Dein mit Counting Sort sortiertes Array. Zugegeben, im Gegensatz zu vergleichsbasierten Sortieralgorithmen wie Selection Sort oder Bubble Sort, ist dieser nicht vergleichsbasierte Algorithmus etwas komplexer. Hast Du das Prinzip jedoch einmal verstanden, sollte Dir auch dieser Algorithmus keine Schwierigkeiten bereiten.

Counting Sort Vorgehensweise

Noch einmal kurz zusammengefasst, wie geht Counting Sort vor:

• Übergebe das Eingabearray mit den zu sortierenden Daten
• Berechne das Maximum der Werte
• Lege basierend auf dem Maximum einen Index sowie ein Hilfsarray an, das zunächst mit Nullen initialisiert wird
• Zähle nun, wie oft jedes Element vorkommt und trage die Zahl ins Hilfsarray ein
• Summiere nun alle Elemente von links nach rechts auf
• Sortiere nun die Elemente, indem Du die unsortierte Datenmenge von rechts nach links durchläufst; lege dafür ein Zielarray an
  • Schreibe dabei das Element im Zielarray an die Position, die im Hilfsarray angegeben ist
  • Reduziere den Wert im Hilfsarray um 1
  • Fahre fort, bis das komplette Array sortiert ist

Counting Sort Komplexität

Wie sieht es mit der Komplexität von Counting Sort aus? Auch hier können wieder die Zeitkomplexität (Laufzeit) und die Platzkomplexität (zusätzlicher Speicher) betrachtet werden.

Counting Sort Laufzeit

Die Counting Sort Laufzeit ist abhängig von der Anzahl der zu sortierenden Daten (n) und der Größe des Zahlenraums (k). Dabei enthält der Algorithmus meist eine – oder mehrere – Schleifen, um die Daten (n) zu durchlaufen und eine für die Größe des Zahlenraums (k).

Daraus ergibt sich wiederum eine Laufzeit von O(n + k), die sowohl für den Best-Case als auch für den Average-Case und den Worst-Case gilt.

Counting Sort Laufzeitanalyse

Aus der Laufzeitanalyse vom Counting Sort lassen sich verschiedene Aussagen ablesen. In der folgenden Tabelle findest Du diese getrennt nach vorsortierten und unsortierten Datenmengen.

Außerdem kann festgehalten werden, dass die Anzahl an benötigten Operationen nicht abhängig von der Reihenfolge der gegebenen Datenmenge ist. Zudem entspricht die Anzahl an Operationen der erwarteten Laufzeit von O(n + k).

Counting Sort Platzkomplexität

Counting Sort läuft out-of-place und benötigt neben einer Hilfsvariable ein temporäres Array als Zwischenspeicher. Deswegen beträgt die Platzkomplexität O(n + k).

Counting Sort – Weitere Begrifflichkeiten

Im Folgenden werden weitere Begrifflichkeiten rund um Counting Sort erklärt, dazu gehören:

• Stabilität
• Vergleichsbasiert
• Parallelisierbarkeit

Counting Sort stabil Beweis

Beim Counting Sort Algorithmus handelt es sich um ein stabiles Verfahren. Warum? Das liegt daran, dass gleiche Elemente beim Kopieren nicht vertauscht werden – das Array wird dafür immer von rechts nach links durchgearbeitet.

Counting Sort vergleichsbasiert

Counting Sort arbeitet im Gegensatz zu anderen Sortieralgorithmen wie Selection Sort oder Bubble Sort nicht vergleichsbasiert. Das heißt, es werden keine zwei Elemente miteinander verglichen, stattdessen wird eine Datenmenge gezählt und durch Schlüsselwerte sortiert.

Counting Sort Parallelisierbarkeit

Counting Sort ist ein parallelisierbarer Sortieralgorithmus. Das kannst Du erreichen, indem Du die gegebene Datenmenge in so viele Partitionen unterteilst, wie Deinem Rechner Prozessoren zur Verfügung stehen.

Counting Sort Zusammenfassung

In der folgenden Übersicht wird das bisher Gelernte noch einmal zusammengefasst:

Counting Sort Beispiel

In den folgenden Abschnitten werden Dir noch ein paar weitere (Code-)Beispiele rund um Counting Sort vorgestellt. Doch zunächst soll noch geklärt werden, wann der Sortieralgorithmus am ehesten verwendet wird:

• Bei kleineren, häufiger vorkommenden Zahlen
• Wenn eine lineare Komplexität gefordert wird

Counting Sort Pseudocode

Pseudocode könnte beim Counting Sort Algorithmus wie folgt aussehen:

counting sort (A)
// A ist das zu sortierende Array
// Komplexität beträgt O(k)
  for i = 0 to k 
    do C[i] = 0  // Initialisierung des Hilfsarrays mit der Zahl 0
// Zählen der Elemente + abspeichern
  for j = 1 to length[A]
    do C[A[j]] = C[A[j]] + 1  

// berechnen der Summe, sodass C[i] die tatsächliche Position der Elemente im Ausgabearray enthält
  for i = 1 to k 
    do C[i] = C[i] + C[i - 1]  

// Ausgabearray aus C[i] erstellen durch neu ordnen/Sortieren der Elemente
  for j = length[A] downto 1
    do B[C[A[j]]] = A[j]  
        C[A[j]] = C[A[j]] - 1

end function