Robert Sedgewick: Algorithmen

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


Literatur für Sortieren



Die wichtigste Referenz für diesen Abschnitt ist Band 3 der Reihe von D. E. Knuth, der dem Sortieren und Suchen gewidmet ist. Zu praktisch jedem Thema, das wir gestreift haben, kann man in diesem Buch weitere Informationen finden. Insbesondere werden die hier vorgestellten Ergebnisse zu den Leistungsmerkmalen der verschiedenen Algorithmen dort durch eine vollständige mathematische Analyse untermauert.

Über das Sortieren existiert eine umfangreiche Literatur. Die 1973 erschienene Bibliographie von Knuth und Rivest enthält Hunderte von Titeln, und dabei sind zahllose Bücher und Artikel zu anderen Themen, in denen auch Fragen des Sortierens behandelt werden, noch nicht erfaßt. Eine neuere Referenz mit einer ausführlichen Bibliographie, die Arbeiten bis 1984 beinhaltet, ist das Buch von Gonnet.

Für Quicksort ist die beste Referenz das Original, der Artikel von Hoare aus dem Jahre 1962, in dem alle wichtigen Varianten suggeriert werden, einschließlich der in Kapitel 9 betrachteten Anwendung beim Auswählen. Zahlreiche weitere Einzelheiten hinsichtlich der mathematischen Analyse und der praktischen Auswirkungen vieler der Modifikationen und Vervollkommnungen, die im Laufe der Jahre vorgeschlagen wurden, sind im 1978 erschienenen Buch des Autors zu finden.

Ein gutes Beispiel für eine höherentwickelte Prioritätswarteschlangen-Struktur sind J. Vuillemins »Binomialwarteschlangen«, so wie sie von M. R. Brown implementiert und analysiert wurden. Diese Datenstruktur unterstützt alle Operationen mit Prioritätswarteschlangen in einer eleganten und effizienten Weise. Der neueste Stand bei dieser Datenstruktur bezüglich praktischer Implementationen ist der »Paarungs-Heap« (pairing heap), der von Fredman, Sedgewick, Sleator und Tarjan beschrieben wurde.

Um einen Eindruck von den unzähligen Details zu bekommen, die zu beachten sind, wenn Algorithmen von der Art der hier betrachteten auf praktische Allzweck-Implementationen zurückgeführt werden sollen, wird dem Leser empfohlen, die entsprechenden Unterlagen für das Sortierprogramm seines speziellen Computersystems zu studieren. In solchen Unterlagen ist notwendigerweise vor allem von Schlüsselformaten, Datensätzen und Dateien sowie von vielen anderen Einzelheiten die Rede, und es ist oft interessant herauszufinden, wie die Algorithmen selbst ins Spiel gebracht werden.


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