Robert Sedgewick: Algorithmen

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


8. Elementare Sortierverfahren



Als ersten Eistieg in das Gebiet der Sortieralgorithmen wollen wir einige »elementare« Methoden untersuchen, die für kleine Dateien oder Dateien mit einer speziellen Struktur geeignet sind. Es gibt verschiedene Gründe dafür, diese einfachen Sortieralgorithmen recht ausführlich zu betrachten. Erstens bieten sie einen relativ mühelosen Weg, Terminologie und grundlegende Mechanismen für Sortieralgorithmen kennenzulernen, so daß wir einen geeigneten Hintergrund für das Studium der komplizierteren Algorithmen schaffen. Zweitens ist es bei einem großen Teil der Anwendungen von Sortierverfahren besser, diese einfachen Methoden zu benutzen als die leistungsfähigeren Mehrzweckverfahren. Schließlich lassen sich einige der einfachen Methoden zu besseren Mehrzweckverfahren weiterentwickeln, oder sie können verwendet werden, um die Effizienz leistungsfähigerer Verfahren zu erhöhen.

Wie bereits erwähnt wurde, gibt es verschiedene Sortier-Anwendungen, bei denen ein relativ einfacher Algorithmus die zu bevorzugende Methode sein kann. Sortierprogramme werden oft nur einmal (oder nur wenige Male) benutzt. Wenn die Anzahl der zu sortierenden Elemente nicht zu groß ist (sagen wir, weniger als fünfhundert Elemente), so kann es durchaus effizienter sein, lediglich eine einfache Methode anzuwenden, als ein kompliziertes Verfahren zu implementieren und zu debuggen. Elementare Verfahren sind für kleine Dateien (mit weniger als etwa fünfzig Elementen) immer geeignet; ein komplizierter Algorithmus dürfte für eine kleine Datei kaum gerechtfertigt sein, es sei denn, daß eine sehr große Anzahl solcher Dateien zu sortieren ist. Weitere Typen von Dateien, die sich relativ leicht sortieren lassen, sind solche, die bereits nahezu sortiert (oder bereits sortiert!) sind, oder solche, die eine große Anzahl von gleichen Schlüsseln enthalten. Bei solchen gut strukturierten Dateien sind einfache Methoden weit besser geeignet als Mehrzweckverfahren.

In der Regel benötigen die elementaren Methoden, die wir betrachten werden, etwa N2 Schritte, um N zufällig angeordnete Elemente zu sortieren. Falls N hinreichend klein ist, ist das im allgemeinen kein Problem, und falls die Elemente nicht zufällig angeordnet sind, können einige der Verfahren weit schneller ablaufen als kompliziertere. Es muß jedoch betont werden, daß diese Verfahren für umfangreiche, zufällig angeordnete Dateien nicht benutzt werden sollten, mit der bemerkenswerten Ausnahme von Shellsort, welches tatsächlich das bevorzugte Sortierverfahren für sehr viele Anwendungen ist.


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