Counting Sort
Algorithmen wie Merge Sort führen Operationen durch, um eine gegebene Sequenz von Elementen zu sortieren. Die meisten eingebauten
sort()-Funktionen in verschiedenen Programmiersprachen benötigen ebenfalls etwa Operationen. Daraus ergibt sich die Frage, ob es eine Möglichkeit gibt, noch schneller zu sortieren.Ein grundlegender Algorithmus, der eine Sequenz von Elementen in linearer Zeit sortiert, also Operationen benötigt, ist das Counting Sort. Counting Sort ist ein effizienter Sortieralgorithmus mit linearer Laufzeit und eignet sich besonders gut für das Sortieren von Elementen, bei denen die Werte bekanntermaßen kleine ganze Zahlen sind.
Die Grundidee von Counting Sort besteht darin, eine Art Histogramm zu erstellen, das zählt, wie viele Elemente des Eingabearrays einen bestimmten Wert haben. Mithilfe dieser Informationen werden die Elemente anschließend in die gewünschte sortierte Reihenfolge gebracht.
Um beispielsweise ein Array mit den Werten
[7, 3, 5, 5, 1, 1, 6, 3, 4, 4, 3, 3, 7, 7, 1, 2, 5, 7, 4, 1, 7, 2, 1, 5, 5, 3, 1, 4, 8, 7] zu sortieren, würde man ein Histogramm erstellen, aus dem hervorgeht, dass es zum Beispiel 6 Einsen, 2 Zweien, 5 Dreien und so weiter gibt: [6, 2, 5, 4, 5, 1, 6, 1] (wie im Bild dargestellt).
a = ...
bottom, top = min(a), max(a) + 1 # Bestimme den Wertebereich
hist = [0] * (top - bottom) # Fülle den Wertebereich mit Nullen => keine Zählwerte
for num in a: # Gehe durch das Array
hist[num - bottom] += 1 # Erhöhe den Histogrammwert
res = [] # Initialisiere das Ergebnis-Array
for num in range(bottom, top): # Gehe über den Wertebereich
res += [num] * hist[num - bottom] # Füge so viele num zum Ergebnis hinzu, wie es der Wert im Histogramm angibtAm Ende enthält das Ergebnis die Werte
[1, 1, 1, 1, 1, 1, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 7, 7, 7, 7, 7, 7, 8].Beachte, dass dieses Verfahren nur für Zahlen funktioniert, insbesondere für Zahlen in einem kleinen Wertebereich, während andere Algorithmen wie Bubble Sort oder Merge Sort auch mit beliebigen Elementen umgehen können, sofern sich diese miteinander vergleichen lassen.
Der Algorithmus benötigt insgesamt Operationen, wobei
n die Anzahl der Elemente im Ausgangsarray ist und r die Größe des Wertebereichs der vorliegenden Zahlen. Verglichen mit Algorithmen wie Merge Sort kann Counting Sort besonders schnell sein, wenn man mit Zahlen arbeitet, die nur einen relativ kleinen Wertebereich haben.🤔
Gibt es andere lineare Sortieralgorithmen?
Ja, man kann sich zum Beispiel Radix-Sort anschauen. Auch dieser Algorithmus funktioniert nur für Zahlen.
Wenn wir nur Vergleichs-basierte Sortieralgorithmen betrachten, die für jede Art von Sequenz funktionieren, solange man die Elemente miteinander vergleichen kann, dann liegt das Optimum bei Operationen; schneller geht es nicht.
Eingabe
Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl
n (1 ≤ n ≤ ).Die nächste Zeile enthält
n durch Leerzeichen getrennte ganze Zahlen (-100 ≤ ≤ 100).Ausgabe
Das Programm soll die gegebenen
n Zahlen in aufsteigender Reihenfolge durch ein Leerzeichen getrennt ausgeben.Beispiele
Input | Output |
5
-3 5 -1 2 10 | -3 -1 2 5 10 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 5 MB