Countingsort

Aus SibiWiki
Version vom 23. Januar 2022, 17:55 Uhr von Akaibel (Diskussion | Beiträge) (→‎Implementierung für Arrays)
(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)
Zur Navigation springen Zur Suche springen


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;
           }
       }
   }