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. 

Counting Sort Counting Sort

Erstelle Lernmaterialien über Counting Sort mit unserer kostenlosen Lern-App!

  • Sofortiger Zugriff auf Millionen von Lernmaterialien
  • Karteikarten, Notizen, Übungsprüfungen und mehr
  • Alles, was du brauchst, um bei deinen Prüfungen zu glänzen
Kostenlos anmelden
Inhaltsverzeichnis
Inhaltsangabe

    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.

    Statt Counting Sort kannst Du auch Countingsort schreiben – beide Schreibweisen sind korrekt.

    Counting Sort Definition

    Counting Sort ist ein stabiler, nicht vergleichsbasierter Sortieralgorithmus, der Datenmengen mithilfe von Schlüsselwerten sortiert.

    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.

    Eine Weiterentwicklung vom Counting Sort ist der Radix Sort. Mehr zu diesem Sortieralgorithmus findest Du in der gleichnamigen Erklärung auf StudySmarter.

    Counting Sort Algorithmus

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

    52849723

    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.

    Hilfsarray0000000000
    Index0123456789

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

    Hilfsarray0021110111
    Index0123456789

    Als kleine Kontrolle kannst Du die Werte aus dem Hilfsarray zusammenzählen. Die Zahl sollte gleich der Menge Deiner unsortierten Daten sein.

    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.

    Was ist der Sinn des Ganzen: Durch diesen Schritt weißt Du nicht mehr nur wie oft einzelne Elemente vorkommen, sondern auch an welche Stelle sie gehören!

    Hilfsarray0023455678
    Index0123456789

    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.

    Zielarray
    Platzhalter12345678

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

    Das Array muss von rechts nach links durchlaufen werden, damit der Algorithmus stabil bleibt.

    Unsortiertes Array52849723
    Hilfsarray0023455678
    Index0123456789

    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.

    Hilfsarray0022455678
    Index0123456789
    Zielarray3
    Platzhalter12345678

    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.

    Hilfsarray0012455678
    Index0123456789
    Zielarray23
    Platzhalter12345678

    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.

    Hier wird auch noch mal deutlich, warum der Algorithmus das Array rückwärts durchlaufen muss, um stabil zu bleiben. Würdest Du das Array von links nach rechts durchgehen, landet die erste 2 an der Stelle 2 im Zielarray und die zweite 2 würde davor landen – das heißt ihre ursprüngliche Reihenfolge wäre vertauscht und der Algorithmus wäre instabil.

    Hilfsarray0002355567
    Index0123456789
    Zielarray2234789
    Platzhalter12345678

    Führe den Algorithmus nun noch zu Ende durch.

    Hilfsarray0002345567
    Index0123456789
    Zielarray22345789
    Platzhalter12345678

    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.

    Kommt in einem Array jeder Schlüssel exakt einmal vor, benötigst Du übrigens keine Vergleiche, sondern kannst die Schlüssel einfach so übertragen.

    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.

    Vorsortierte DatenmengenUnsortierte Datenmengen
    Gemessene Werte entsprechen der erwarteten linearen Komplexität von O(n + k).Gemessene Werte liegen etwas über einer linearen Komplexität.
    Bei sehr vielen Elementen (mehrere Millionen) werden vorsortierte Datenmengen etwa neunmal so schnell sortiert wie unsortierte Datenmengen.
    Datenmengen, die absteigend vorsortiert sind, werden etwas langsamer sortiert als aufsteigend vorsortierte Daten.

    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.

    Wie läuft die Parallelisierung dann grob weiter ab? Im 1. Schritt durchläuft jeder Prozessor seine zugeteilten Elemente in einem Hilfsarray. Beim 2. Schritt werden dann alle Hilfsarrays zusammengenommen. Im letzten Schritt kopieren die Prozessoren "ihre" Elemente in das Zielarray.

    Parallel durchgeführter Counting Sort ist nicht mehr stabil, da die ursprüngliche Reihenfolge von gleichen Elementen durch das Hin- und Herkopieren von unterschiedlichen Prozessoren nicht gewährleistet werden kann.

    Counting Sort Zusammenfassung

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

    Best-CaseAverage-CaseWorst-CasePlatz-komplexitätStabiles Verfahrenvergleichs-basiertIn-PlaceParallelisier-barkeit
    O(n + k)O(n + k)O(n + k)O(n + k)JaNeinNeinMöglich

    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

    Counting Sort – Das Wichtigste

    • Einfach erklärt ist Counting Sort ein stabiler, nicht vergleichsbasierter Sortieralgorithmus, der Datenmengen mithilfe von Schlüsselwerten sortiert.
    • Counting Sort Algorithmus Vorgehensweise:
      • Maximum eines Eingabearrays berechnen
      • Index und Hilfsarray anlegen + Anzahl Elemente zählen und im Hilfsarray notieren
      • Elemente von links nach rechts aufsummieren
      • Ursprüngliche Datenmenge von rechts nach links durchgehen und das Element im Zielarray an die Position schreiben, die im Hilfsarray steht
      • Danach den Wert im Hilfsarray um 1 reduzieren
    • Counting Sort besitzt eine Laufzeit von O(n + K), die Platzkomplexität beträgt ebenfalls O(n + k).
    • Counting Sort stabil Beweis: Counting Sort ist ein stabiles Verfahren, weil gleiche Elemente beim Sortieren nicht in ihrer ursprünglichen Reihenfolge vertauscht werden.

    Nachweise

    1. Matthias Teschner (2012). Algorithmen und Datenstrukturen, Sortieren. cg.informatik.uni-freiburg.de (07.11.2022)
    2. Happycoders.eu: Counting Sort – Algorithmus, Quellcode, Zeitkomplexität. (07.11.2022)
    Häufig gestellte Fragen zum Thema Counting Sort

    Warum ist Counting Sort stabil? 

    Counting Sort ist stabil, weil die Elemente beim Schreiben ins Zielarray einfach z. B. von rechts nach links durchgearbeitet werden und so gleiche Elemente ihre ursprüngliche Reihenfolge behalten. 

    Wie funktioniert Counting Sort? 

    Das Prinzip hinter Counting Sort ist es, Elemente mit unterschiedlichen Schlüsselwerten zu zählen und diese anschließend in einer sortierten Liste abzubilden.  

    Wann wird Counting Sort verwendet? 

    Counting Sort wird vor allem bei kleineren, häufiger vorkommenden Zahlen verwendet oder wenn eine lineare Komplexität gefordert wird.

    Ist Counting Sort stabil? 

    Counting Sort ist ein stabiler Sortieralgorithmus, da sich die Reihenfolge gleicher Elemente beim Sortieren nicht verändert. 

    Teste dein Wissen mit Multiple-Choice-Karteikarten

    Wahr oder falschCounting Sort ist ein stabiler, vergleichsbasierter Sortieralgorithmus.

    Wahr oder falschCounting Sort arbeitet out-of-place.

    Ist Counting Sort parallelisierbar?

    Weiter

    Entdecken Lernmaterialien mit der kostenlosen StudySmarter App

    Kostenlos anmelden
    1
    Über StudySmarter

    StudySmarter ist ein weltweit anerkanntes Bildungstechnologie-Unternehmen, das eine ganzheitliche Lernplattform für Schüler und Studenten aller Altersstufen und Bildungsniveaus bietet. Unsere Plattform unterstützt das Lernen in einer breiten Palette von Fächern, einschließlich MINT, Sozialwissenschaften und Sprachen, und hilft den Schülern auch, weltweit verschiedene Tests und Prüfungen wie GCSE, A Level, SAT, ACT, Abitur und mehr erfolgreich zu meistern. Wir bieten eine umfangreiche Bibliothek von Lernmaterialien, einschließlich interaktiver Karteikarten, umfassender Lehrbuchlösungen und detaillierter Erklärungen. Die fortschrittliche Technologie und Werkzeuge, die wir zur Verfügung stellen, helfen Schülern, ihre eigenen Lernmaterialien zu erstellen. Die Inhalte von StudySmarter sind nicht nur von Experten geprüft, sondern werden auch regelmäßig aktualisiert, um Genauigkeit und Relevanz zu gewährleisten.

    Erfahre mehr
    StudySmarter Redaktionsteam

    Team Counting Sort Lehrer

    • 9 Minuten Lesezeit
    • Geprüft vom StudySmarter Redaktionsteam
    Erklärung speichern

    Lerne jederzeit. Lerne überall. Auf allen Geräten.

    Kostenfrei loslegen

    Melde dich an für Notizen & Bearbeitung. 100% for free.

    Schließ dich über 22 Millionen Schülern und Studierenden an und lerne mit unserer StudySmarter App!

    Die erste Lern-App, die wirklich alles bietet, was du brauchst, um deine Prüfungen an einem Ort zu meistern.

    • Karteikarten & Quizze
    • KI-Lernassistent
    • Lernplaner
    • Probeklausuren
    • Intelligente Notizen
    Schließ dich über 22 Millionen Schülern und Studierenden an und lerne mit unserer StudySmarter App!