Sortieralgorithmen
Suchalgorithmen
Datenstrukturen
Verschiedenes
Quellen
![\begin{listing}{1}
void counting_sort( int * data, int N )
{
int k, i, max;
in...
... < N; i++ )
data[i] = tmp[i];
\par free( counts );
free( tmp );
}\end{listing}](img62.png)
Wie schon erwähnt, kann man für Datenmengen, die nur aus ganzen positiven Zahlen bestehen, eine andere Vorgehensweise des CountingSorts implementieren. Nach dem die Häufigkeitsinformation gesammelt wurde, lässt sich ohne das Aufsummieren und Schreiben eines Temporärarrays tmp arbeiten. Das letztere fällt gänzlich weg. Der Clue hier ist, daß die Indizes selbst als Elemente benutz werden, da die Elemente selbst Zahlen sind.
![\begin{listing}{1}
num_counting_sort( int * data, int N )
{
int i, j, max;
int...
... {
data[i++] = j;
counts[j]--;
}
j++;
}
\par free( counts );
}\end{listing}](img63.png)
Angemerkt sei, daß in den beiden hier vorgestellten Implementierungen keine Überprüfung des Rückgabewertes der Funktion ``malloc'' stattfindet. Dies sollte in einer ernsthaften Verwendung des Algorithmus geschen, da diese Funktion durchaus fehlschlagen kann und in diesem Falle ``NULL'' liefert, um so einen Fehler zu signalisieren.
Nächste Seite: Optimierung
Aufwärts: CoutingSort
Vorherige Seite: Laufzeitkomplexität
Inhalt
