Dies ist eine alte Version dieser Seite, zuletzt bearbeitet am 4. Januar 2008 um 21:26 Uhr durch Jumaki(Diskussion | Beiträge)(Rechtschreibfehler verbessert.). Sie kann sich erheblich von der aktuellen Version unterscheiden.
Countingsort (von engl. count „zählen“) ist ein einfaches, stabilesSortierverfahren. Es sortiert eine gegebene Zahlenfolge nicht durch Vergleiche, sondern setzt das Wissen voraus, aus welchem Intervall die Zahlen des Schlüssels stammen.
Die zu sortierenden Zahlen liegen in für ein festes, im Voraus bekanntes . Dann bestimme für jedes zu sortierende Element die Anzahl der Elemente, welche in der sortierten Reihenfolge vor liegen, und platziere damit an die korrekte Stelle.
Eingabe
Feld mit für alle . Als Parameter werden übergeben.
Ausgabe
Feld mit Inhalt von in sortierter Reihenfolge.
Zudem wird bei dem Sortierverfahren ein Hilfsvektor benötigt.
Implementierungen
Pseudocode
Der nachfolgende Pseudocode bezieht sich auf die in der Problemstellung benutzten Bezeichnungen.
COUNTINGSORT(A)
1 for i = 0 to k
2 do C[i] = 0
3 for j = 1 to length[A]
4 do C[A[j]] = C[A[j]] + 1
//C[i] gibt nun an, wie oft i in A vorkommt.
5 for i = 1 to k
6 do C[i] = C[i] + C[i - 1]
//C[i] gibt nun die Anzahl der Elemente <= i in A an.
7 for j = length[A] downto 1
8 do B[C[A[j]]] = A[j]
9 C[A[j]] = C[A[j]] - 1
Python
def counting_sort(A):
B = []
C = []
for index in xrange(0, max(A)+1):
C.append(0)
for index in xrange(0, len(A)):
B.append("")
for index in xrange(0, len(A)):
C[A[index]]=C[A[index]]+1
for index in xrange(1, len(C)):
C[index]=C[index]+C[index-1]
for index in xrange(len(A)-1, -1, -1):
B[C[A[index]]-1]=A[index]
C[A[index]]=C[A[index]]-1
return B
Beispiel
Ausführung von Countingsort auf ein Eingabefeld mit Elementen aus mit Hilfsfeld und sortierter Ausgabe in Feld .
1
2
3
4
5
6
7
8
2
5
3
0
2
3
0
3
0
1
2
3
4
5
0
0
0
0
0
0
1
2
3
4
5
6
7
8
Darstellung untereinander Ausgangsliste , Hilfsvektor , dessen Länge vom Definitionsbereich der Liste abhängt. In unterster Liste werden die Elemente sortiert eingefügt. Die Obige Abbildung stellt die gegebene Zahlenfolge dar, wobei die erste Schleife des Algorithmus bereits abgearbeitet wurde, indem lediglich der Vektor mit 0 initialisiert wird. Zweite Schleife inkrementiert für jede Ziffer deren Stelle im Vektor um eins.
1
2
3
4
5
6
7
8
2
5
3
0
2
3
0
3
0
1
2
3
4
5
2
0
2
3
0
1
1
2
3
4
5
6
7
8
Die dritte Schleife summiert den Vektor auf, so daß dessen Inhalt angibt, bis zu welcher Position ein Wert in der sortierten Liste auftaucht. Zwei gleiche aufeinanderfolgende Zahlen bedeuten dabei, daß die letzte der beiden Zahlen in der Folge überhaupt nicht auftaucht, also vorher in an dieser Position ein 0 gewesen war.
1
2
3
4
5
6
7
8
2
5
3
0
2
3
0
3
0
1
2
3
4
5
2
2
4
7
7
8
1
2
3
4
5
6
7
8
Nun folgt die letzte Schleife. In dieser werden nun sukzessive die Werte aus in den Vektor übertragen und zwar genau an der Stelle im Zielvektor, die der Hilfsvektor für die entsprechende Zahl angibt. Vor der Schleife ist dies immer die letzte Stelle, an der die Zahl auftauchen wird. Nach dem übertragen jeder Zahl wird zusätzlich der Wert in dekrementiert. Die nächste gleiche Zahl wird deswegen eine Stelle weiter vorn im Zielvektor eingefügt. Nachfolgend die 8 Schritte.
Die ersten 7 Schritte im Detail
1. Schritt
1
2
3
4
5
6
7
8
2
5
3
0
2
3
0
3
0
1
2
3
4
5
2
2
4
6
7
8
1
2
3
4
5
6
7
8
3
2. Schritt
1
2
3
4
5
6
7
8
2
5
3
0
2
3
0
3
0
1
2
3
4
5
1
2
4
6
7
8
1
2
3
4
5
6
7
8
0
3
3. Schritt
1
2
3
4
5
6
7
8
2
5
3
0
2
3
0
3
0
1
2
3
4
5
1
2
4
5
7
8
1
2
3
4
5
6
7
8
0
3
3
4. Schritt
1
2
3
4
5
6
7
8
2
5
3
0
2
3
0
3
0
1
2
3
4
5
1
2
3
5
7
8
1
2
3
4
5
6
7
8
0
2
3
3
5. Schritt
1
2
3
4
5
6
7
8
2
5
3
0
2
3
0
3
0
1
2
3
4
5
0
2
3
5
7
8
1
2
3
4
5
6
7
8
0
0
2
3
3
6. Schritt
1
2
3
4
5
6
7
8
2
5
3
0
2
3
0
3
0
1
2
3
4
5
0
2
3
4
7
8
1
2
3
4
5
6
7
8
0
0
2
3
3
3
7. Schritt
1
2
3
4
5
6
7
8
2
5
3
0
2
3
0
3
0
1
2
3
4
5
0
2
3
4
7
7
1
2
3
4
5
6
7
8
0
0
2
3
3
3
5
8. Schritt
1
2
3
4
5
6
7
8
2
5
3
0
2
3
0
3
0
1
2
3
4
5
0
2
2
4
7
7
1
2
3
4
5
6
7
8
0
0
2
2
3
3
3
5
Laufzeitanalyse
Wie man aus obigem Pseudocode leicht ersehen kann, hängt die Laufzeit der Funktion von und ab. Die erste for-Schleife wird genau -mal durchlaufen, die zweite genau -mal. Die Zeitkomplexität von Countingsort beträgt O.
Speicherplatzbedarf
Zusätzlich zur Eingabe, die 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 Feldern. Die Platzkomplexität von Countingsort liegt in .
![{\displaystyle A[1..n]}](/media/api/rest_v1/media/math/render/svg/77350b7b7a24749675609a440314e0ab8aded3d5)
![{\displaystyle A[j]\in \{0,\ldots ,k\}}](/media/api/rest_v1/media/math/render/svg/7029f78524a404676f564620de14b592199bc06d)
![{\displaystyle B[1..n]}](/media/api/rest_v1/media/math/render/svg/7bc6aa2e55a7d9ee100e0605dd87ff62a401dea0)
![{\displaystyle C[0..k]}](/media/api/rest_v1/media/math/render/svg/8fd92f0f393f1c3f79b8214b6b8a2c33c3c3d93d)
![{\displaystyle A[1..8]}](/media/api/rest_v1/media/math/render/svg/6153b20efb7a1612823ea07bec92ad77582f2cff)
![{\displaystyle C[Zahl]}](/media/api/rest_v1/media/math/render/svg/495c78d5888801a1eb969c13d4de5c25e20dff40)
