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.

Prinzip

Sind $N$ ganzzahlige Schlüssel $1\leq k_{1},\ldots ,k_{N}\leq M,M\in \mathbb {N}$ gegeben, so zählt Countingsort, wie oft jede Zahl aus dem Intervall $[1,M]$ in den zu sortierenden Schlüsseln vorkommt. Diese Anzahl wird in einer Hilfsliste C festgehalten. Danach durchläuft das Sortierverfahren das Intervall $[1,M]$ aufsteigend, und addiert die Werte in C nach dem Schema $C[x]=C[x]+C[x-1]$ . Somit beinhaltet die Hilfsliste die Intervallsgrenzen. Zuletzt wird mithilfe dieser Liste die sortierte Liste B erstellt, was das Typische an Countingsort ist, indem man den Schlüssel an der Stelle i in der unsortierten Liste A an die Stelle $B[C[A[i]-1]]$ schreibt.

Beispiel

Gegeben ist das unsortierte Feld a=[2,5,3,0,2,3,0,3].

1.)Größtes Element k suchen(hier die 5)
2.)Neues Feld Anlegen,bestehend aus k=5 Einträgen: i=[0,0,0,0,0]
3.)Durchzählen (count),wie oft jeder Wert im Ausgangsfeld vorkommt:

  die 0-2x ,1-0x , 2-2x ,3-3x ,4-0x ,5-1x

4.)Die ermittelten Werte in das neue Feld einfügen:i=[2,0,2,3,0,1]
5.)Aufsummieren des Feldes i => h=[2,(0+2),(2+0+2),(3+2+0+2),(0+3+2+0+2),(1+0+3+2+0+2)]

  => h=[2,2,4,7,7,8]

Dieses sind nun die Indexwerte für das zu sortierende Feld

6.)Neues Feld b anlegen mit n=lenght(a)
7.)b=[0,0,0,0,0,0,0,0]
8.)Indizies auslesen.d.h. Die 5 kommt an position 8(Feld beginnt bei 1 nicht bei 0!!!)

  => b=[0,0,0,0,0,0,0,5]
  i dekrementieren => i=[2,0,2,3,0,0]
  h dekrementieren => h=[2,2,4,7,7,7]

nun ist die 5 verarbeitet und der laufindex geht eine Position nach links (im feld i und h). da in Feld i die position 5=0 ist bedeutet dies das der index noch eine Position weiter nach links rückt (wieder in i und h)

d.h. der Index zeigt in i auf Pos 4 (den Wert 3) und in h auch auf 4 (den Wert 7) Dies Bedeutet an Pos. 7 in Feld b kommt eine 3:

  => b=[0,0,0,0,0,0,3,5]
  => i dekrementieren i=[2,0,2,2,0,0] h dekrementieren => h=[2,2,4,6,7,7]

laufindex bleibt auf pos 4 da in i pos 4 noch nicht 0 ist. d.h. an Pos 6 in b kommt auch noch eine 3:

  => b=[0,0,0,0,0,3,3,5]
  => i und h dekrementieren i=[2,0,2,1,0,0] h=[2,2,4,5,7,7]

Laufindex bleibt wieder stehen bei Pos 4:

  => b=[0,0,0,0,3,3,3,5]
  => i und h dekrementieren i=[2,0,2,0,0,0] h=[2,2,4,4,7,7]

Da Pos 4 in jetzt = 0 ist bzw in h Pos 4 = Pos 3 laufindex um einen verringern. Pos 3 in i ist nicht 0 ,sondern 2 => es müssen 2 2en geschrieben werden,die erste an Pos 4 in b, da der Zeiger in h auf 4 zeigt:

  => b=[0,0,0,2,3,3,3,5]
  => i und h wieder dekrementieren i=[2,0,1,0,0,0] h=[2,2,3,4,7,7]
  da i[3] nicht 0
  => b=[0,0,2,2,3,3,3,5]
  => i=[2,0,0,0,0,0] h=[2,2,2,4,7,7]

nun ist i[3]=0 bzw h[3]=h[2] ,d.h index zeiger wandert einen nach links. i[2]=0 und h[2]=h[1] ,d.h. noch einen nach links (Nochmals Achtung i[1]= erste Feldposition!): i[1]=2 und h[1]=2

  => b=[0,0,2,2,3,3,3,5] => i=[1,0,0,0,0,0] => h=[1,2,2,4,7,7]
  da i[1] nicht 0
  => b=[0,0,2,2,3,3,3,5] => i=[0,0,0,0,0,0[ => h=[0,2,2,4,7,7]

 (Anmerkung man kann dies auch ohne das Feld i machen in dem man wie gezeigt die Werte in h auf      
 gleichheit testet.Außerdem ist diese Implementierung STABIL!)

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

Siehe auch: Liste von Algorithmen

Implementierungen

Python

def counting_sort(A):
   B=[]  //sortierte Liste
   C=[]  //Hilfsliste

   //Generierung der Listen C und B (Erstellung von Idizes)
   for index in xrange(0, max(A)+1):
           C.append(0)
   for index in xrange(0, len(A)):
           B.append("")

   //Schlüssel an der Stelle A[index] wird in C[A[index]] inkrementiert 
   for index in xrange(0, len(A)):
           C[A[index]]=C[A[index]]+1

   //Intervallsgrenzen werden gebildet
   for index in xrange(1, len(C)):
           C[index]=C[index]+C[index-1]

   //Mithilfe von Liste C wird die sortierte Liste B erstellt
   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

Weblinks

Interaktives Java-Applet zur Demonstration