Optimierung

Wie schon in zweiten Code-Listing gezeigt, können zwei Durchläufe der Ordnung N und der zusäztliche Speicher tmp gespart werden, falls die Datenmenge aus Zahlen besteht. Allerdings sind in realen Anwendungen solche Situationen nicht immer gegeben.

Ein anderes Problem entsteht durch den Speicherverbrauch des Algorithmus für das Häufigkeitsarray counts. Kommen nur Elemente vor, die beispielsweise zwischen 500 und 1000 liegen, so würde eine einfache Implementierung ein 1001-elementiges Array allokieren, obwohl die ersten 500 ungebraucht bleiben würden, da diese Elemente nicht vorkommen und somit eine Häufigkeit von 0 aufweisen. Eine Idee wäre es, nicht nur das größte Element, sondern auch das Kleinste vor der Allokierung herauszufinden und nur den wirklich benötigten Speicher anzufordern. Später müssten natürlich die Werte der Elemente auf die richtige Position im Array durch ein ``mapping'' indiziert werden.

Nächste Seite Aufwärts Vorherige Seite Inhalt

Nächste Seite: Hashing Aufwärts: CoutingSort Vorherige Seite: Implementierung Inhalt

2002-05-09