Countingsort

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 Schlüssels stammen.

Problemstellung

Die zu sortierenden Zahlen liegen in $\{0,1,\ldots ,k\}$ für ein festes, im Voraus bekanntes $k$ . Dann bestimme für jedes zu sortierende Element $x$ die Anzahl der Elemente, welche in der sortierten Reihenfolge vor $x$ liegen, und platziere damit $x$ an die korrekte Stelle.

Eingabe

Feld $A[1..n]$ mit $A[j]\in \{0,\ldots ,k\}$ für alle $j=1,\ldots ,n$ . Als Parameter werden $A,k,n$ übergeben.

Ausgabe

Feld $B[1..n]$ mit Inhalt von $A$ in sortierter Reihenfolge.

Zudem wird bei dem Sortierverfahren ein Hilfsvektor $C[0..k]$ 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 $A[1..8]$ mit Elementen aus $\{0,\ldots ,5\}$ mit Hilfsfeld $C$ und sortierter Ausgabe in Feld $B$ .

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 $A$ , Hilfsvektor $C$ , 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 $C$ 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 $C$ 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 $C$ 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 $A$ in den Vektor $B$ übertragen und zwar genau an der Stelle im Zielvektor, die der Hilfsvektor $C$ 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 $C[Zahl]$ 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 $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)$ .

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)$ .

Weitere Sortierverfahren

Siehe auch: Liste von Algorithmen

Weblinks

Interaktives Java-Applet zur Demonstration