Countingsort: Unterschied zwischen den Versionen

Aus SibiWiki
Zur Navigation springen Zur Suche springen
 
Zeile 19: Zeile 19:


=Implementierung für Arrays=
=Implementierung für Arrays=
<code>
<code>
     public void countingsort (int[] pZahlen)
     public void countingsort (int[] pZahlen)
     {
     {
Zeile 44: Zeile 44:
         }
         }
     }
     }
 
</code>
</code>

Aktuelle Version vom 23. Januar 2022, 17:55 Uhr


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