Countingsort

Countingsort (von engl. count "zählen") ist ein relativ langsames und unstabiles Sortierverfahren.

Prinzip

Countingsort zählt die Anzahl des Vorkommens einzelner Zahlenelmente aus der zu sortierenden Menge und schreibt diese dann der Reihe nach entsprechend ihres Vorkommens in das Feld.

Pseudocode

gegeben: m = (3,2,5,1,4,3) (Eingabe) a = array [0..größter Zahlenwert aus m] of Integer

 for i := 0 to high(a) do
   erhöhe den Zahlenwert in a an stelle m[i]
 for i := 0 to high(a) do
   gebe a[i] mal i aus

Bemerkung

Diese Art der Implementierung gibt die sinngemäße Verfahrensweise wieder, ist jedoch ungeeignet um hohe Zahlenwerte zu sortieren. Dies rührt daher, dass die Länge des Arrays a bei dieser Implementierung von dem höchsten Wert aus m abhängt. Eine Methode um dieses Problem zu umschiffen wäre eine lineare Zuordnung der Indizes von a mit den Zahlenwerten aus m, dann wäre die Länge von a = |m|-1.