Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


10. Digitales Sortieren



Kenngrößen der Leistungsfähigkeit digitaler Sortierverfahren

Die Laufzeiten bei beiden grundlegenden digitalen Sortierverfahren für das Sortieren von N Datensätzen mit aus b Bits bestehenden Schlüsseln betragen im Prinzip Nb. Einerseits kann man davon ausgehen, daß diese Laufzeit im wesentlichen N log N beträgt, da, falls die Zahlen alle verschieden sind, b wenigstens log N sein muß. Andererseits verwenden beide Methoden gewöhnlich viel weniger als Nb Operationen: die von links nach rechts vorgehende Methode, weil sie abbrechen kann, sobald Unterschiede zwischen Schlüsseln gefunden worden sind, und die von rechts nach links vorgehende Methode, weil sie viele Bits gleichzeitig verarbeiten kann.

Eigenschaft 10.1 Radix Exchange Sort verwendet im Durchschnitt ungefähr N lg N Bitvergleiche.

Wenn die Größe der Datei eine Zweierpotenz ist und die Bits zufällig sind, so ist zu erwarten, daß eine Hälfte der führenden Bits 0 und die andere Hälfte 1 ist, so daß die rekurrente Beziehung CN = 2CN/2 + N die Leistungsfähigkeit beschreiben müßte, wie in Kapitel 9 für Quicksort erläutert wurde. Diese Beschreibung der Situation ist wiederum nicht exakt, da die Zerlegung nur im Durchschnitt auf die Mitte fällt (und da die Anzahl der Bits in den Schlüsseln endlich ist). In diesem Modell ist jedoch die Wahrscheinlichkeit dafür, daß die Zerlegung in der Mitte erfolgt, wesentlich größer als bei Quicksort, so daß die Behauptung sich als richtig erweist. (Um dies zu beweisen, ist eine gründliche Analyse erforderlich, die über den Rahmen dieses Buches hinausgehen würde.) w.z.b.w.

Eigenschaft 10.2 Beide digitale Sortierverfahren verwenden für das Sortieren von N Schlüsseln aus b Bits weniger als Nb Bitvergleiche.

Anders gesagt, die digitalen Sortierverfahren sind linear in dem Sinne, daß die benötigte Zeit proportional zur Anzahl der Bits im Datensatz ist. Dies folgt unmittelbar aus einer Untersuchung der Programme: Kein Bit wird mehr als einmal betrachtet. w.z.b.w.

Wie Abbildung 9.6 zeigt, verhält sich Radix Exchange Sort für große zufällige Dateien recht ähnlich wie Quicksort, während sich Straight Radix Sort völlig anders verhält. Abbildung 10.5 zeigt die Etappen von Straight Radix Sort für eine zufällige Datei, die aus Schlüsseln mit sechs Bits besteht. Die fortschreitende Organisation der Datei im Verlauf des Sortierens ist auf diesen Bildern klar zu erkennen. Beispielsweise besteht die Datei nach der vierten Etappe (unten mitte) aus vier miteinander vermischten sortierten Teildateien: Die mit 00 beginnenden Schlüssel (unterer Streifen), die mit 01 beginnenden Schlüssel usw.

Abbildung 10.5
Abbildung 10.5 Etappen von Straight Radix Sort.

Eigenschaft 10.3 Straight Radix Sort kann N Datensätze mit aus b Bits bestehenden Schlüsseln in b/m Durchläufen sortieren, wobei ein zusätzlicher Platz für 2m Zähler (und ein Puffer für das Umordnen der Datei) benötigt wird.

Der Beweis dieser Tatsache ergibt sich unmittelbar aus der Implementation. Insbesondere erhalten wir, wenn wir m = b/4 wählen können, ohne allzu großen zusätzlichen Speicheraufwand ein lineares Sortierverfahren! Die praktischen Konsequenzen aus dieser Eigenschaft werden im folgenden Abschnitt ausführlicher erörtert. w.z.b.w.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]