Countingsort

Verfahren

Countingsort ist ein Sortierverfahren, das sich nur einsetzen lässt, wenn die Anzahl der möglichen Werte beschränkt ist, wie z.B. beim Sortieren von Postleitzahlen (es gibt nur 99.999 verschiedene Werte).

Für jeden möglichen Wert wird dann eine "Strichliste" angelegt; d.h. bei Postleitzahlen gäbe es 99.999 Strichlisten. Dann wird das zu sortierende Array durchlaufen und für jeden Eintrag ein Strich in der richtigen Strichliste gemacht.

Sobald man das Array durchlaufen hat, geht man die Strichlisten der Reihe nach durch: Wenn z.B. bei der PLZ "1" fünf Striche und bei der PLZ "2" drei Striche sind, dann trägt man in das Ergebnisarray ein: 1-1-1-1-1-2-2-2.

Wenn man das für alle Strichlisten macht, dann hat man das Array sortiert.

Laufzeit

Die Laufzeit ist O(n + m), mit

• n: Anzahl der zu sortierenden Elemente
• m: Größe des Wertebereichs (bei Postleitzahlen: 100.000)

Implementierung für Arrays

   public void countingsort (int[] pZahlen)
   {
       int[] strichlisten = new int[100000];
       for(int i=0;i<pZahlen.length;i++)
       {
           int aktuellerWert;
           aktuellerWert = pZahlen[i];
           strichlisten[aktuellerWert] = strichlisten[aktuellerWert]+1;
       }

       int position=0;
       int anzahl=0;

       for(int i=0; i<strichlisten.length;i++)
       {
           anzahl = strichlisten[i];
           while(anzahl>0)
           {
               pZahlen[position] = i;
               anzahl = anzahl-1;
               position = position+1;
           }
       }
   }