Countingsort

Countingsort (von engl. count „zählen“) ist ein stabiles Sortierverfahren, das eine gegebene Folge von natürlichen Zahlen aus einem beschränkten Intervall mit linearem Zeitaufwand in Abhängigkeit von der Eingabelänge sortiert. Der Algorithmus arbeitet nicht vergleichsbasiert, sondern zählt die Zahlen der Eingabe. Im Gegensatz dazu ist die Problemkomplexität von Sortieren per Vergleich in O(nlog n).

Algorithmus

Countingsort setzt voraus, dass die zu sortierenden Zahlen der Eingabe in einem beschränkten Intervall $\{0,\ldots,k\}$ liegen. Der Algorithmus zählt jede Zahl, die in der Eingabe vorkommt und speichert dies in einem zusätzlichen Array mit k + 1 Elementen ab. Mit Hilfe von diesem Array wird für jedes Element der Eingabe die Zielposition in der Ausgabe berechnet.

Eingabe: Array A[1..n] mit $A[j] \in \{0,\ldots, k\}$ für alle $j=1,\ldots,n$ und die rechte Intervallgrenze k.

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

Zusätzlicher Speicher: Während der Sortierung benötigt der Algorithums ein Hilfs-Array C[0..k].

Angabe des Algorithmus in Pseudocode:

countingsort(A, k)
  C = array(0,k)
  for (i=0; i<=k; i=i+1)
    C[i] = 0
  for (i=1; i<=A.size; i=i+1)
    C[key(A[i])] = C[key(A[i])] + 1
  for (i=1; i<=k; i=i+1)
    C[i] = C[i] + C[i-1]
  B = array(1, A.size)
  for (i=A.size; i>0; i=i-1)
    B[C[key(A[i])]] = A[i]
    C[key(A[i])] = C[key(A[i])] - 1
  return B

Die Funktion key gibt den Sortierschlüssel des Array-Elements der Eingabe zurück. Wenn ein Array-Element nur aus dem Sortierschlüssel besteht und keine weitere Komponenten enthält, dann ist key(x) = x. In der ersten for-Schleife wird das Hilfs-Array C initialisiert. Die zweite for-Schleife iteriert über die Eingabe und inkrementiert für jeden Sortierschlüssel das zugeordnete Array-Element C[key(A[i])]. In der dritten for-Schleife werden die Zähler in C akkumuliert, so dass nach dem Ende der Schleife C[x] die letzte Position von der Zahl x im Ausgabe-Array bezeichnet. Die letzte for-Schleife durchläuft die Eingabe von rechts nach links und dekrementiert für jeden Sortierschlüssel den Eintrag in C, der die Position im Ausgabe-Array bestimmt. Durch die Iteration von rechts nach links wird die relative Reihenfolge von mehreren Elementen der Eingabe mit dem gleichen Sortiertschlüssel auch in der Ausgabe nicht verändert, d.h. Countingsort sortiert stabil.

Vereinfachter Algorithmus

Wenn die Eingabe ein einfaches Zahlen-Array ist, dann kann Countingsort ohne eine Akkumulationsphase dargestellt werden:

countingsort(A, k)
  C = array(0, k)
  for (i=0; i<=k; i=i+1)
    C[i] = 0
  for (i=1; i<=A.size; i=i+1)
    C[A[i]] = C[A[i]] + 1
  j=0
  B = array(1, A.size)
  for (i=0; i<=k; i=i+1)
    for ( ; C[i]>0; C[i]=C[i]-1)
      B[j] = i
      j = j+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 dass dessen Inhalt angibt, bis zu welcher Position ein Wert in der sortierten Liste auftaucht. Zwei gleiche aufeinanderfolgende Zahlen bedeuten dabei, dass 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

Komplexität

Laufzeitanalyse

Wie man aus obigem Pseudocode leicht ersehen kann, hängt die Laufzeit der Funktion von n (Anzahl der Elemente des Eingabe(arrays)) und k (die Größe des Zahlenintervalls) ab. Die for-Schleifen werden jeweils n-mal oder k-mal durchlaufen. Die Zeitkomplexität von Countingsort beträgt also $\mathcal{O}(n + k)$.

Speicherplatzbedarf

Zusätzlich zur Ein- und Ausgabe, die jeweils n Speicherfelder benötigen, wird noch ein temporäres Array zur Speicherung der Häufigkeiten der Zahlenwerte angelegt. Dieses benötigt k Elemente Speicherplatz. Die Platzkomplexität von Countingsort liegt also in $\mathcal{O}(m + k)$.

Literatur

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms. 2. Auflage. MIT Press, Cambridge (Massachusetts) 2001, ISBN 0-262-03293-7, S. 168-170. 
• Donald Ervin Knuth: The Art of Computer Programming: Volume 3 Sorting and Searching. 2. Auflage. Addison-Wesley, Reading, Mass. 1997, ISBN 0-201-89685-0, S. 78. 
• W. Feurzeig: Algorithm 23: Math Sort. In: Communications of the ACM. 3, Nr. 11, 1960, S. 601.
• H. H. Seward: M.I.T. Digital Computer Laboratory Report R-232. 1954, S. 25-28 (Masterarbeit).

Weblinks

 Wikibooks: Countingsort – Implementierungen in der Algorithmensammlung

• Interaktives Java-Applet zur Demonstration