Site hosted by Angelfire.com: Build your free website today!

Distribution Counting


Dieser Sortieralgorithmus ist nur auf den speziellen Fall anwendbar, dass alle N Datensätze Schlüssel im ganzzahligen Bereich von 0 bis M-1 (M nicht zu groß) haben, läuft dort jedoch linear zu MN ab.
Es wird die Anzahl der Schlüssel jedes Wertes ermittelt, um die Elemente anschließend in einem Hilfsfeld (das später das Original-Feld ersetzt) in die richtige Position zu bringen. IMHO spricht der einfache Code für sich.

void cm_DistributionCounting(itemType feld[], int M, int N) {
     int i, j;
     itemType *zaehlfeld = new itemType[M];
     itemType *hilfsfeld = new itemType[N+1];
     for(j=0; j<M; ++j) zaehlfeld[j] = 0;
     for(i=1; i<=N; ++i) zaehlfeld[zaehlfeld[i]]++;
     for(j=1; j<M; ++j) zaehlfeld[j] += zaehlfeld[j-1];
     for(i=N; i>=1; --i) hilfsfeld[zaehlfeld[feld[i]]--] = feld[i];
     for(i=1; i<=N; ++i) feld[i] = hilfsfeld[i];
}


   Computer    Programmieren (incl. C++ Kurs)    Algorithmen    Bücher    

Zeitschriften    Heavy Metal    Mountainbiking    Meine Katze    

Über mich und die Site    Links    Downloads    Gästebuch    HP mit Umfrage