Countingsort
aus Wikipedia, der freien Enzyklopädie
Countingsort (von engl. count „zählen“) ist ein einfaches, stabiles Sortierverfahren. Es sortiert eine gegebene Zahlenfolge nicht durch Vergleiche, sondern setzt das Wissen voraus, aus welchem Intervall die Zahlen des Intervalls stammen.
Inhaltsverzeichnis |
[Bearbeiten] Prinzip
Sind N ganzzahlige Schlüssel 
gegeben, so zählt Countingsort, wie oft jede Zahl aus dem Intervall [1,M] in den zu sortierenden Schlüsseln vorkommt. Danach durchläuft das Sortierverfahren das Intervall [1,M] aufsteigend, und gibt jede Zahl so oft aus, wie sie in der Eingabe vorkommt.
[Bearbeiten] Beispiel mit Pseudocode
| Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf bitte mit, ihn zu verbessern, und entferne anschließend diese Markierung. |
Die Folge 3, 2, 5, 1, 3, 7 ist zu sortieren. Also ist N = 6 und M = 7.
Die folgende in Pseudocode geschriebene Funktion, die als Eingabe die zu sortierende Folge als Feld K, die Anzahl N der Elemente im Feld K und das größte Element M des Feldes K erwartet, gibt die Folge sortiert auf dem Bildschirm aus:
K ← [3, 2, 5, 1, 3, 7] # Eingabe
N ← length(k) # Anzahl der Elemente in k = 6
M ← max(k) # größtes Element in k = 7
A ← array[1..M] of Integer # Feld mit M Elementen, initialisiert mit 0
func CountingSort(K, N, M):
for i ← 1 to N: # bestimmt Häufigkeit jeder Zahl in K
cur ← K[i]
A[cur] ← A[cur] + 1
for j ← 1 to M:
for k ← 1 to A[j]: # gibt jede Zahl j in K genau A[j]-mal aus
print j
Wird die Funktion CountingSort mit obigem Feld K und zugehörigem N und M aufgerufen, sieht die Ausgabe wie folgt aus:
1 2 3 3 5 7
[Bearbeiten] Laufzeitanalyse
Wie man aus obigem Pseudocode leicht ersehen kann, hängt die Laufzeit der Funktion von N und M ab. Die erste for-Schleife wird genau N-mal durchlaufen, die zweite genau M-mal. Die Zeitkomplexität von Countingsort beträgt O(N + M).
[Bearbeiten] Speicherplatzbedarf
Zusätzlich zur Eingabe, die N Speicherfelder benötigt, wird noch eine Liste zur Speicherung der Häufigkeiten der Zahlenwerte benötigt. Diese benötigt im Falle der obigen Implementierung einen Speicherplatz von M Feldern. Die Platzkomplexität von Countingsort liegt in O(N + M).
Siehe auch: Liste von Algorithmen
