Robert Sedgewick: Algorithmen

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


10. Digitales Sortieren



Ein lineares Sortierverfahren

Die im vorangehenden Abschnitt angegebene Implementation von Straight Radix Sort realisiert b/m Durchläufe durch die Datei. Indem wir m groß wählen, erhalten wir eine sehr effiziente Sortiermethode, solange wir M = 2m Wörter im Speicher zur Verfügung haben. Eine sinnvolle Entscheidung besteht darin, m etwa gleich einem Viertel der Wortlänge (b/4) zu wählen, so daß das digitale Sortierverfahren vier Durchläufen des Distribution Countings entspricht. Die Schlüssel werden als Zahlen auf der Basis M behandelt, und jede (Basis-M)-Ziffer jedes Schlüssels wird betrachtet; es existieren jedoch lediglich vier Ziffern pro Schlüssel. (Dies entspricht unmittelbar der internen Organisation vieler Computer: Eine typische Speicherorganisation hat 32-Bit-Wörter, die jeweils aus vier Bytes zu je 8 Bits bestehen. Die Prozedur bits realisiert dann in diesem Fall das Extrahieren bestimmter Bytes aus den Wörtern, was auf solchen Computern offensichtlich auf sehr effiziente Weise möglich ist.) Nun ist jeder Durchlauf von Distribution Counting linear, und da nur vier Durchläufe erfolgen, ist das gesamte Sortierverfahren linear; sicher ist das das beste Ergebnis, auf das wir bei einem Sortierverfahren hoffen konnten.

In Wirklichkeit zeigt es sich, daß wir sogar mit nur zwei Durchläufen des Distribution Countings auskommen können. (Selbst ein aufmerksamer Leser wird diesmal vermutlich Schwierigkeiten haben, sich zurechtzufinden, so daß einige Mühe nötig sein wird, um diese Methode zu verstehen.) Wir tun das, indem wir die Tatsache ausnutzen, daß die Datei beinahe sortiert sein wird, wenn nur die führenden b/2 Bits der aus b Bits bestehenden Schlüssel verwendet werden. Wie bei Quicksort kann der Sortiervorgang auf effiziente Weise vervollständigt werden, indem anschließend auf die gesamte Datei Insertion Sort angewandt wird. Diese Methode ist offensichtlich eine einfache Modifikation der obigen Implementation: Um ein Sortieren von rechts nach links unter Verwendung der führenden Hälfte der Schlüssel zu realisieren, lassen wir einfach die äußere Schleife bei pass=b div (2 * m) anstatt bei pass=1 beginnen. Danach kann auf die resultierende, nahezu geordnete Datei ein gewöhnliches Insertion Sort angewandt werden. Um sich davon zu überzeugen, daß eine Datei, die anhand ihrer führenden Bits sortiert wurde, recht gut geordnet ist, kann der Leser die ersten Spalten von Abbildung 10.2 betrachten. Beispielsweise würden bei Anwendung von Insertion Sort auf die Datei, die bereits hinsichtlich der ersten drei Bits sortiert ist, nur sechs Austauschoperationen erforderlich sein.

Indem man zwei Durchläufe von Distribution Counting (wobei m etwa gleich einem Viertel der Wortlänge ist) und danach zur Vollendung der Aufgabe Insertion Sort verwendet, erhält man eine Sortiermethode, die schneller ablaufen dürfte als jede andere, die wir für große Dateien, deren Schlüssel zufällige Bits sind, kennengelernt haben. Ihr hauptsächlicher Nachteil ist, daß sie ein zusätzliches Feld der gleichen Größe wie das zu sortierende Feld benötigt. Es ist möglich, durch die Anwendung verketteter Listen das zusätzliche Feld zu beseitigen, doch ein zu N proportionaler zusätzlicher Platz (für die Verkettungen) ist trotzdem erforderlich.

Ein lineares Sortieren ist offensichtlich für viele Anwendungen wünschenswert, doch aus verschiedenen Gründen ist es nicht das Universalmittel, das es zu sein scheint. Zum einen hängt seine Effizienz wirklich davon ab, daß die Schlüssel zufällig angeordnete zufällige Bits sind. Wenn diese Bedingung nicht erfüllt ist, ist eine stark verringerte Leistungsfähigkeit wahrscheinlich. Zweitens erfordert es zusätzlichen Platz, der zur Größe des zu sortierenden Feldes proportional ist. Drittens enthält die »innere Schleife« des Programms tatsächlich eine ganze Reihe von Anweisungen, so daß das Verfahren, obwohl es linear ist, nicht um so viel schneller als (zum Beispiel) Quicksort ist, wie man erwarten könnte, außer für sehr große Dateien (wobei dann wiederum das zusätzliche Feld zu einem echten Hindernis wird). Die Entscheidung zwischen Quicksort und dem digitalen Sortieren ist kompliziert und dürfte nicht nur von Merkmalen der Anwendung wie Größe der Schlüssel, der Datensätze und der Datei abhängen, sondern auch von Merkmalen der Programmierumgebung und -möglichkeiten, die mit der Effizienz des Zugriffs und der Verwendung von einzelnen Bits in Zusammenhang stehen. Doch auch hier gilt wieder, daß solche Untersuchungen von einem Experten durchgeführt werden müssen und daß sie sich nur für ernsthafte Sortieranwendungen lohnen dürften.


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