Quelltext der Seite Countingsort

'''Countingsort''' (von {{enS|count}} „zählen“) ist ein [[Stabiles Sortierverfahren|stabiles]] [[Sortierverfahren]], das eine gegebene [[Folge (Mathematik)|Folge]] von <math>n</math> Elementen mit [[Zeitkomplexität|linearem Zeitaufwand]] ([[Problemkomplexität]] <math>\textstyle O(n + k)</math>) sortiert, wenn deren Sortierschlüssel [[Natürliche Zahl|natürliche Zahlen]] aus einem beschränkten [[Intervall (Mathematik)|Intervall]] mit <math>k</math> möglichen Werten sind (oder sich darauf abbilden lassen). Der [[Algorithmus]] arbeitet nicht [[Sortierverfahren#Vergleichsbasiertes Sortieren|vergleichsbasiert]], sondern zählt die Vorkommnisse der Schlüsselwerte – er arbeitet dann adressbasiert. Im Vergleich zum vergleichenden Sortieren mit der bestmöglichen Komplexität <math>\textstyle O(n \log n)</math> ergibt sich ein Vorteil, wenn die Intervalllänge <math>k</math> sehr klein gegenüber der Anzahl der zu sortierenden Elemente <math>n</math> ist.

Gut geeignetes Beispiel: Sortieren aller Einwohner Bayerns (n = 12,85 Mio.) nach ihrem Alter (in vollendeten Jahren: k = 0..150).

Schlechtes/nicht umsetzbares Beispiel: Sortieren der Schüler einer Grundschule (n = 300) nach ihrem Nachnamen (Zeichenkette mit max. Länge 40 aus allen möglichen Buchstaben, Umlauten und Sonderzeichen; k ≈ 35<sup>40</sup>).

== Algorithmus ==
Countingsort setzt voraus, dass die zu sortierenden Schlüsselwerte der Eingabe in einem beschränkten [[Intervall (Mathematik)|Intervall]] <math>\{0,\ldots,(k-1)\}</math> liegen (oder sich einfach darauf abbilden lassen). Der Algorithmus zählt, wie oft jeder dieser Werte in der Eingabe vorkommt. Diese Anzahlen speichert er in einem zusätzlichen Array mit <math>k</math> Feldern ab. Mit Hilfe dieses Arrays wird anschließend für jeden Schlüsselwert die Ziel''position'' in der Ausgabe berechnet.

'''Eingabe:'''
[[Array (Datentyp)|Array]] <math>A[1 .. n]</math> mit <math>A[j] \in \{0,\ldots, (k-1)\}</math> für alle <math>j=1,\ldots,n</math> und die rechte Intervallgrenze <math>(k-1)</math>.

'''Ausgabe:'''
Feld <math>B[1 .. n]</math> mit Inhalt von <math>A</math> in sortierter Reihenfolge.

'''Zusätzlicher Speicher:''' Während der Sortierung benötigt der Algorithmus ein Hilfs-Array <math>C[0 .. (k-1)]</math>.

Angabe des Algorithmus in [[Pseudocode]]:

<syntaxhighlight lang="C">
countingsort(A,k)
{
  C = array(0,k-1)

  // Initialisiere das Array C mit Nullen
  for (m=0; m<k; m++)
    C[m] = 0
  // end for

  // Schreibe in C[m], wie häufig der Wert m in A vorkommt
  for (j=1; j<=A.size; j++)
    C[key(A[j])] += 1
  // end for

  // Adressrechnung
  for (m=1; m<k; m++)
    C[m] += C[m-1]
  // end for

  B = array(1, A.size)

  // Kopiere auf jeweilige Zieladresse in B (mit Dekrementierung)
  for (j=A.size; j>0; j--) {
    B[ C[ key(A[j]) ] ] = A[j]
    C[key(A[j])] -= 1
  }

  return B
}
</syntaxhighlight>

Die Funktion ''key'' gibt den [[Nummerung|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 <math>\text{key}(x) = x</math>.<br />In der ersten [[for-Schleife]] wird das Hilfs-Array <math>C</math> initialisiert.<br />Die zweite for-Schleife iteriert über die Eingabe und inkrementiert für jeden Sortierschlüssel das zugeordnete Array-Element <math>C[\text{key}(A[j])]</math>. <math>C[m]</math> enthält somit die Anzahl, wie oft der Schlüsselwert <math>m</math> in <math>A</math> vorkommt.<br />In der dritten for-Schleife werden die Zähler in <math>C</math> akkumuliert, so dass nach dem Ende der Schleife <math>C[x]</math> die letzte Position für ein Element mit Schlüsselwert <math>x</math> im Ausgabe-Array bezeichnet. Somit enthält <math>C[m]</math> jetzt nicht mehr „Anzahl der ‚m-Elemente‘ in A“, sondern die „Adresse des ‚m-Abschnitts‘ für B“ (allerdings die Endadresse, nicht die Startadresse).<br />Die letzte for-Schleife durchläuft die Eingabe von rechts nach links (aufgrund der ''End''adressen in <math>C</math>), und sortiert den jeweiligen Eintrag dabei ein:
Ist die Schleife in Iteration <math>j</math>, so hat <math>A[j]</math> den Schlüsselwert <math>m_j</math> (= <math>\text{key}(A[j])</math>). Dieser muss also einsortiert werden an Adresse <math>C[m_j]</math>. Anschließend wird die Zieladresse <math>C[m_j]</math> dekrementiert, damit das nächste Element in <math>A</math>, welches den Schlüssel <math>m_j</math> besitzt, eine Position weiter vorne einsortiert wird.<br />Durch die sprungfreie Iteration wird die relative Reihenfolge von mehreren Elementen der Eingabe mit dem gleichen Sortierschlüssel auch in der Ausgabe nicht verändert, d.&nbsp;h. Countingsort sortiert [[Stabiles Sortierverfahren|stabil]].

=== Vereinfachter Algorithmus ===

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

<syntaxhighlight lang="c">
countingsort(A, k)
{
  C = array(0, (k-1))
  for (m=0; m<k; m=m+1)
    C[m] = 0
  // end for

  for (j=1; j<=A.size; j=j+1)
    C[A[j]] = C[A[j]] + 1
  // end for

  i=0
  B = array(1, A.size)
  for (m=0; m<k; m=m+1) {
    while (C[m]>0) {
      B[i] = m
      C[m] = C[m]-1
      i = i+1
    }
  }

  return B
}
</syntaxhighlight>

Hierbei wird ausgenutzt, dass es dann nicht notwendig ist, die Inhalte von A nach B zu kopieren – es genügt, die <math>m</math>-Abschnitte von B mit so vielen <math>m</math>-Ganzzahlen zu füllen, wie im jeweiligen <math>C[m]</math> vermerkt ist.

== Funktionsbeispiel ==
Ausführung von Countingsort auf ein Eingabefeld <math>A[1 .. 8]</math> mit Elementen aus <math>\{0, \ldots, 5\}</math> mit Hilfsfeld <math>C</math> und sortierter Ausgabe in Feld <math>B</math>.
<div class="center">
{| class="wikitable" style="border-top:0 solid; border-left:0 solid; border-right:0 solid;"
|-
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 1
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 2
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 3
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 4
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 5
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 6
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 7
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 8
|- style="text-align:center; font-size:larger;"
|style="background:#FFFFFF"| 2
|style="background:#FFFFFF"| 5
|style="background:#FFFFFF"| 3
|style="background:#FFFFFF"| 0
|style="background:#FFFFFF"| 2
|style="background:#FFFFFF"| 3
|style="background:#FFFFFF"| 0
|style="background:#FFFFFF"| 3
|}
{| class="wikitable" style="border-top:0 solid; border-left:0 solid; border-right:0 solid;"
|-
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 0
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 1
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 2
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 3
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 4
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 5
|- style="text-align:center; font-size:larger;"
|style="background:#FFD700"| 0
|style="background:#FFD700"| 0
|style="background:#FFD700"| 0
|style="background:#FFD700"| 0
|style="background:#FFD700"| 0
|style="background:#FFD700"| 0
|}
{| class="wikitable" style="border-top:0 solid; border-left:0 solid; border-right:0 solid;"
|-
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 1
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 2
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 3
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 4
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 5
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 6
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 7
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 8
|- style="text-align:center; font-size:larger;"
|style="background:#FFFFFF"|
|style="background:#FFFFFF"|
|style="background:#FFFFFF"|
|style="background:#FFFFFF"|
|style="background:#FFFFFF"|
|style="background:#FFFFFF"|
|style="background:#FFFFFF"|
|style="background:#FFFFFF"|
|}
</div>
Darstellung untereinander: Ausgangsarray <math>A</math>, Hilfsarray <math>C</math>, dessen Länge vom Definitionsbereich des Arrays abhängt. In das unterste Array werden die Elemente sortiert eingefügt.<br />Die obige Abbildung stellt die gegebene Zahlenfolge dar, wobei die erste Schleife des Algorithmus bereits abgearbeitet wurde, indem lediglich das Array <math>C</math> mit 0 initialisiert wird. Die zweite Schleife inkrementiert für jede Ziffer deren Stelle im Array um eins.
<div class="center">
{| class="wikitable" style="border-top:0 solid; border-left:0 solid; border-right:0 solid;"
|-
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 1
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 2
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 3
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 4
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 5
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 6
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 7
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 8
|- style="text-align:center; font-size:larger;"
|style="background:#FFFFFF"| 2
|style="background:#FFFFFF"| 5
|style="background:#FFFFFF"| 3
|style="background:#FFFFFF"| 0
|style="background:#FFFFFF"| 2
|style="background:#FFFFFF"| 3
|style="background:#FFFFFF"| 0
|style="background:#FFFFFF"| 3
|}
{| class="wikitable" style="border-top:0 solid; border-left:0 solid; border-right:0 solid;"
|-
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 0
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 1
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 2
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 3
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 4
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 5
|- style="text-align:center; font-size:larger;"
|style="background:#FFD700"| 2
|style="background:#FFD700"| 0
|style="background:#FFD700"| 2
|style="background:#FFD700"| 3
|style="background:#FFD700"| 0
|style="background:#FFD700"| 1
|}
{| class="wikitable" style="border-top:0 solid; border-left:0 solid; border-right:0 solid;"
|-
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 1
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 2
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 3
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 4
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 5
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 6
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 7
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 8
|- style="text-align:center; font-size:larger;"
|style="background:#FFFFFF"|
|style="background:#FFFFFF"|
|style="background:#FFFFFF"|
|style="background:#FFFFFF"|
|style="background:#FFFFFF"|
|style="background:#FFFFFF"|
|style="background:#FFFFFF"|
|style="background:#FFFFFF"|
|}
</div>
Die dritte Schleife summiert das Array <math>C</math> auf, so dass dessen Inhalt angibt, bis zu welcher Position ein Wert in dem sortierten Array auftaucht. Zwei gleiche aufeinanderfolgende Zahlen bedeuten dabei, dass die letzte der beiden Zahlen in der Folge überhaupt nicht auftaucht, also vorher in <math>C</math> an dieser Position ein 0 gewesen war.
In Array <math>C</math> stehen nun also statt der ''Anzahlen'', wie oft ein Wert im Array A enthalten ist, stattdessen ''Endadressen'' (bzw. ''End-Indizes''):
* Der letzte Wert '5' aus Array A muss an Index 8 in das Zielarray B;
* der Wert '4' kam in Array A nicht vor und hat daher dieselbe Endadresse wie der Wert '3';
* die letzte '3' aus Array A muss an Index 7 in das Zielarray B – anschließend wird die Zieladresse C['3'] um 1 heruntergezählt, so dass die nächste '3' aus Array A den Zielindex 6 erhält und somit nach B[6] kopiert wird;
* die letzte '2' aus Array A muss an Index 4 (also B[4]), weitere '2'er aus A müssen ''vor'' Index 4;
* '1' kommt in A nicht vor, daher hat es dieselbe „letzte Zieladresse“ wie der Wert '0';
* die letzte '0' aus Array A hat die Zieladresse C['0'], also 2. Sobald sie in das Array B einsortiert wurde (also nach B[2]), muss C['0'] um 1 heruntergezählt werden, damit die nächste '0', die in Array A gefunden wird, nach Index C['0']=1, also in das Feld B[1] kopiert wird.
<div class="center">
{| class="wikitable" style="border-top:0 solid; border-left:0 solid; border-right:0 solid;"
|-
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 1
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 2
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 3
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 4
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 5
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 6
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 7
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 8
|- style="text-align:center; font-size:larger;"
|style="background:#FFFFFF"| 2
|style="background:#FFFFFF"| 5
|style="background:#FFFFFF"| 3
|style="background:#FFFFFF"| 0
|style="background:#FFFFFF"| 2
|style="background:#FFFFFF"| 3
|style="background:#FFFFFF"| 0
|style="background:#FFFFFF"| 3
|}
{| class="wikitable" style="border-top:0 solid; border-left:0 solid; border-right:0 solid;"
|-
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 0
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 1
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 2
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 3
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 4
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 5
|- style="text-align:center; font-size:larger;"
|style="background:#FFD700"| 2
|style="background:#FFD700"| 2
|style="background:#FFD700"| 4
|style="background:#FFD700"| 7
|style="background:#FFD700"| 7
|style="background:#FFD700"| 8
|}
{| class="wikitable" style="border-top:0 solid; border-left:0 solid; border-right:0 solid;"
|-
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 1
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 2
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 3
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 4
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 5
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 6
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 7
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 8
|- style="text-align:center; font-size:larger;"
|style="background:#FFFFFF"|
|style="background:#FFFFFF"|
|style="background:#FFFFFF"|
|style="background:#FFFFFF"|
|style="background:#FFFFFF"|
|style="background:#FFFFFF"|
|style="background:#FFFFFF"|
|style="background:#FFFFFF"|
|}
</div>
In der letzten Schleife werden sukzessive die Werte aus <math>A</math> in das Array <math>B</math> übertragen und zwar genau an der Stelle im Zielarray, die das Hilfsarray <math>C</math> 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 <math>C[Zahl]</math> dekrementiert. Die nächste gleiche Zahl wird deswegen eine Stelle weiter vorne im Zielarray eingefügt. Nachfolgend die 8 Schritte.

{{Klappleiste/Anfang|style-kopf=text-align:left;|TITEL=Die ersten 7 Schritte im Detail}}
1. Schritt
<div class="center">
{| class="wikitable" style="border-top:0 solid; border-left:0 solid; border-right:0 solid;"
|-
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 1
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 2
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 3
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 4
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 5
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 6
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 7
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 8
|- style="text-align:center; font-size:larger;"
|style="background:#FFFFFF"| 2
|style="background:#FFFFFF"| 5
|style="background:#FFFFFF"| 3
|style="background:#FFFFFF"| 0
|style="background:#FFFFFF"| 2
|style="background:#FFFFFF"| 3
|style="background:#FFFFFF"| 0
|style="background:#87CEFF"| 3
|}
{| class="wikitable" style="border-top:0 solid; border-left:0 solid; border-right:0 solid;"
|-
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 0
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 1
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 2
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 3
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 4
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 5
|- style="text-align:center; font-size:larger;"
|style="background:#FFD700"| 2
|style="background:#FFD700"| 2
|style="background:#FFD700"| 4
|style="background:#87CEFF;font-size:smaller;"| 6
|style="background:#FFD700"| 7
|style="background:#FFD700"| 8
|}
{| class="wikitable" style="border-top:0 solid; border-left:0 solid; border-right:0 solid;"
|-
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 1
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 2
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 3
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 4
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 5
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 6
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 7
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 8
|- style="text-align:center; font-size:larger;"
|style="background:#FFFFFF"|
|style="background:#FFFFFF"|
|style="background:#FFFFFF"|
|style="background:#FFFFFF"|
|style="background:#FFFFFF"|
|style="background:#FFFFFF"|
|style="background:#87CEFF"| 3
|style="background:#FFFFFF"|
|}
</div>
2. Schritt
<div class="center">
{| class="wikitable" style="border-top:0 solid; border-left:0 solid; border-right:0 solid;"
|-
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 1
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 2
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 3
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 4
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 5
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 6
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 7
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 8
|- style="text-align:center; font-size:larger;"
|style="background:#FFFFFF"| 2
|style="background:#FFFFFF"| 5
|style="background:#FFFFFF"| 3
|style="background:#FFFFFF"| 0
|style="background:#FFFFFF"| 2
|style="background:#FFFFFF"| 3
|style="background:#87CEFF"| 0
|style="background:#FFFFFF"| 3
|}
{| class="wikitable" style="border-top:0 solid; border-left:0 solid; border-right:0 solid;"
|-
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 0
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 1
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 2
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 3
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 4
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 5
|- style="text-align:center; font-size:larger;"
|style="background:#87CEFF"| 1
|style="background:#FFD700"| 2
|style="background:#FFD700"| 4
|style="background:#FFD700;font-size:smaller;"| 6
|style="background:#FFD700"| 7
|style="background:#FFD700"| 8
|}
{| class="wikitable" style="border-top:0 solid; border-left:0 solid; border-right:0 solid;"
|-
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 1
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 2
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 3
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 4
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 5
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 6
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 7
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 8
|- style="text-align:center; font-size:larger;"
|style="background:#FFFFFF"|
|style="background:#87CEFF"| 0
|style="background:#FFFFFF"|
|style="background:#FFFFFF"|
|style="background:#FFFFFF"|
|style="background:#FFFFFF"|
|style="background:#FFFFFF"| 3
|style="background:#FFFFFF"|
|}
</div>
3. Schritt
<div class="center">
{| class="wikitable" style="border-top:0 solid; border-left:0 solid; border-right:0 solid;"
|-
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 1
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 2
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 3
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 4
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 5
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 6
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 7
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 8
|- style="text-align:center; font-size:larger;"
|style="background:#FFFFFF"| 2
|style="background:#FFFFFF"| 5
|style="background:#FFFFFF"| 3
|style="background:#FFFFFF"| 0
|style="background:#FFFFFF"| 2
|style="background:#87CEFF"| 3
|style="background:#FFFFFF"| 0
|style="background:#FFFFFF"| 3
|}
{| class="wikitable" style="border-top:0 solid; border-left:0 solid; border-right:0 solid;"
|-
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 0
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 1
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 2
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 3
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 4
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 5
|- style="text-align:center; font-size:larger;"
|style="background:#FFD700"| 1
|style="background:#FFD700"| 2
|style="background:#FFD700"| 4
|style="background:#87CEFF"| 5
|style="background:#FFD700"| 7
|style="background:#FFD700"| 8
|}
{| class="wikitable" style="border-top:0 solid; border-left:0 solid; border-right:0 solid;"
|-
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 1
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 2
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 3
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 4
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 5
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 6
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 7
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 8
|- style="text-align:center; font-size:larger;"
|style="background:#FFFFFF"|
|style="background:#FFFFFF"| 0
|style="background:#FFFFFF"|
|style="background:#FFFFFF"|
|style="background:#FFFFFF"|
|style="background:#87CEFF"| 3
|style="background:#FFFFFF"| 3
|style="background:#FFFFFF"|
|}
</div>
4. Schritt
<div class="center">
{| class="wikitable" style="border-top:0 solid; border-left:0 solid; border-right:0 solid;"
|-
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 1
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 2
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 3
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 4
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 5
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 6
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 7
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 8
|- style="text-align:center; font-size:larger;"
|style="background:#FFFFFF"| 2
|style="background:#FFFFFF"| 5
|style="background:#FFFFFF"| 3
|style="background:#FFFFFF"| 0
|style="background:#87CEFF"| 2
|style="background:#FFFFFF"| 3
|style="background:#FFFFFF"| 0
|style="background:#FFFFFF"| 3
|}
{| class="wikitable" style="border-top:0 solid; border-left:0 solid; border-right:0 solid;"
|-
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 0
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 1
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 2
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 3
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 4
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 5
|- style="text-align:center; font-size:larger;"
|style="background:#FFD700"| 1
|style="background:#FFD700"| 2
|style="background:#87CEFF"| 3
|style="background:#FFD700"| 5
|style="background:#FFD700"| 7
|style="background:#FFD700"| 8
|}
{| class="wikitable" style="border-top:0 solid; border-left:0 solid; border-right:0 solid;"
|-
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 1
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 2
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 3
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 4
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 5
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 6
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 7
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 8
|- style="text-align:center; font-size:larger;"
|style="background:#FFFFFF"|
|style="background:#FFFFFF"| 0
|style="background:#FFFFFF"|
|style="background:#87CEFF"| 2
|style="background:#FFFFFF"|
|style="background:#FFFFFF"| 3
|style="background:#FFFFFF"| 3
|style="background:#FFFFFF"|
|}
</div>
5. Schritt
<div class="center">
{| class="wikitable" style="border-top:0 solid; border-left:0 solid; border-right:0 solid;"
|-
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 1
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 2
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 3
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 4
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 5
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 6
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 7
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 8
|- style="text-align:center; font-size:larger;"
|style="background:#FFFFFF"| 2
|style="background:#FFFFFF"| 5
|style="background:#FFFFFF"| 3
|style="background:#87CEFF"| 0
|style="background:#FFFFFF"| 2
|style="background:#FFFFFF"| 3
|style="background:#FFFFFF"| 0
|style="background:#FFFFFF"| 3
|}
{| class="wikitable" style="border-top:0 solid; border-left:0 solid; border-right:0 solid;"
|-
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 0
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 1
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 2
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 3
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 4
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 5
|- style="text-align:center; font-size:larger;"
|style="background:#87CEFF"| 0
|style="background:#FFD700"| 2
|style="background:#FFD700"| 3
|style="background:#FFD700"| 5
|style="background:#FFD700"| 7
|style="background:#FFD700"| 8
|}
{| class="wikitable" style="border-top:0 solid; border-left:0 solid; border-right:0 solid;"
|-
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 1
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 2
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 3
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 4
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 5
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 6
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 7
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 8
|- style="text-align:center; font-size:larger;"
|style="background:#87CEFF"| 0
|style="background:#FFFFFF"| 0
|style="background:#FFFFFF"|
|style="background:#FFFFFF"| 2
|style="background:#FFFFFF"|
|style="background:#FFFFFF"| 3
|style="background:#FFFFFF"| 3
|style="background:#FFFFFF"|
|}
</div>
6. Schritt
<div class="center">
{| class="wikitable" style="border-top:0 solid; border-left:0 solid; border-right:0 solid;"
|-
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 1
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 2
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 3
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 4
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 5
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 6
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 7
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 8
|- style="text-align:center; font-size:larger;"
|style="background:#FFFFFF"| 2
|style="background:#FFFFFF"| 5
|style="background:#87CEFF"| 3
|style="background:#FFFFFF"| 0
|style="background:#FFFFFF"| 2
|style="background:#FFFFFF"| 3
|style="background:#FFFFFF"| 0
|style="background:#FFFFFF"| 3
|}
{| class="wikitable" style="border-top:0 solid; border-left:0 solid; border-right:0 solid;"
|-
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 0
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 1
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 2
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 3
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 4
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 5
|- style="text-align:center; font-size:larger;"
|style="background:#FFD700"| 0
|style="background:#FFD700"| 2
|style="background:#FFD700"| 3
|style="background:#87CEFF"| 4
|style="background:#FFD700"| 7
|style="background:#FFD700"| 8
|}
{| class="wikitable" style="border-top:0 solid; border-left:0 solid; border-right:0 solid;"
|-
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 1
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 2
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 3
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 4
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 5
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 6
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 7
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 8
|- style="text-align:center; font-size:larger;"
|style="background:#FFFFFF"| 0
|style="background:#FFFFFF"| 0
|style="background:#FFFFFF"|
|style="background:#FFFFFF"| 2
|style="background:#87CEFF"| 3
|style="background:#FFFFFF"| 3
|style="background:#FFFFFF"| 3
|style="background:#FFFFFF"|
|}
</div>
7. Schritt
<div class="center">
{| class="wikitable" style="border-top:0 solid; border-left:0 solid; border-right:0 solid;"
|-
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 1
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 2
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 3
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 4
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 5
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 6
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 7
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 8
|- style="text-align:center; font-size:larger;"
|style="background:#FFFFFF"| 2
|style="background:#87CEFF"| 5
|style="background:#FFFFFF"| 3
|style="background:#FFFFFF"| 0
|style="background:#FFFFFF"| 2
|style="background:#FFFFFF"| 3
|style="background:#FFFFFF"| 0
|style="background:#FFFFFF"| 3
|}
{| class="wikitable" style="border-top:0 solid; border-left:0 solid; border-right:0 solid;"
|-
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 0
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 1
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 2
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 3
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 4
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 5
|- style="text-align:center; font-size:larger;"
|style="background:#FFD700"| 0
|style="background:#FFD700"| 2
|style="background:#FFD700"| 3
|style="background:#FFD700"| 4
|style="background:#FFD700"| 7
|style="background:#87CEFF"| 7
|}
{| class="wikitable" style="border-top:0 solid; border-left:0 solid; border-right:0 solid;"
|-
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 1
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 2
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 3
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 4
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 5
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 6
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 7
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 8
|- style="text-align:center; font-size:larger;"
|style="background:#FFFFFF"| 0
|style="background:#FFFFFF"| 0
|style="background:#FFFFFF"|
|style="background:#FFFFFF"| 2
|style="background:#FFFFFF"| 3
|style="background:#FFFFFF"| 3
|style="background:#FFFFFF"| 3
|style="background:#87CEFF"| 5
|}
</div>
{{Klappleiste/Ende}}
8. Schritt
<div class="center">
{| class="wikitable" style="border-top:0 solid; border-left:0 solid; border-right:0 solid;"
|-
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 1
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 2
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 3
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 4
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 5
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 6
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 7
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 8
|- style="text-align:center; font-size:larger;"
|style="background:#87CEFF"| 2
|style="background:#FFFFFF"| 5
|style="background:#FFFFFF"| 3
|style="background:#FFFFFF"| 0
|style="background:#FFFFFF"| 2
|style="background:#FFFFFF"| 3
|style="background:#FFFFFF"| 0
|style="background:#FFFFFF"| 3
|}
{| class="wikitable" style="border-top:0 solid; border-left:0 solid; border-right:0 solid;"
|-
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 0
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 1
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 2
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 3
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 4
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 5
|- style="text-align:center; font-size:larger;"
|style="background:#FFD700"| 0
|style="background:#FFD700"| 2
|style="background:#87CEFF"| 2
|style="background:#FFD700"| 4
|style="background:#FFD700"| 7
|style="background:#FFD700"| 7
|}
{| class="wikitable" style="border-top:0 solid; border-left:0 solid; border-right:0 solid;"
|-
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 1
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 2
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 3
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 4
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 5
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 6
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 7
!style="border-top:0 solid; border-left:0 solid; border-right:0 solid;" width="20"| 8
|- style="text-align:center; font-size:larger;"
|style="background:#FFFFFF"| 0
|style="background:#FFFFFF"| 0
|style="background:#87CEFF"| 2
|style="background:#FFFFFF"| 2
|style="background:#FFFFFF"| 3
|style="background:#FFFFFF"| 3
|style="background:#FFFFFF"| 3
|style="background:#FFFFFF"| 5
|}
</div>

== Komplexität ==
=== Laufzeitanalyse ===
Die Laufzeit der Funktion hängt von <math>n</math> (Anzahl der Elemente des Eingabearrays) und <math>k</math> (die Größe des Zahlenintervalls) ab. Die [[for-Schleife]]n werden jeweils <math>n</math>-mal oder <math>k</math>-mal durchlaufen. Die [[Zeitkomplexität]] von Countingsort beträgt somit [[Landau-Symbole|<math>\mathcal{O}(n + k)</math>]].

=== Speicherplatzbedarf ===
Zusätzlich zur Ein- und Ausgabe, die jeweils <math>n</math> Speicherfelder benötigen ([[Out-of-place-Algorithmus|out-of-place]]), wird noch ein temporäres Array zur Speicherung der Häufigkeiten der Zahlenwerte angelegt. Dieses benötigt <math>k</math> Elemente Speicherplatz. Die [[Platzkomplexität]] von Countingsort liegt also in <math>\mathcal{O}(n + k)</math>.

== Literatur ==
* {{BibISBN|0262032937|Seite=168–170}}
* {{BibISBN|0201896850|Seite=78}}
* {{Literatur
   |Autor=W. Feurzeig
   |Titel=Algorithm 23: Math Sort
   |Sammelwerk=Communications of the ACM
   |Band=3
   |Nummer=11
   |Datum=1960
   |Seiten=601}}
* {{Literatur
   |Autor=H. H. Seward
   |Titel=M.I.T. Digital Computer Laboratory Report R-232
   |Datum=1954
   |Seiten=25–28
   |Kommentar=Masterarbeit}}

== Weblinks ==
{{Wikibooks|Algorithmensammlung: Sortierverfahren: Countingsort|Countingsort|suffix=Implementierungen in der Algorithmensammlung}}
* [http://users.cs.cf.ac.uk/C.L.Mumford/tristan/CountingSort.html Interaktives Java-Applet zur Demonstration]
* [https://www.cs.usfca.edu/~galles/visualization/CountingSort.html Demonstration des Algorithmus]

[[Kategorie:Sortieralgorithmus]]