Robert Sedgewick: Algorithmen

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


13. Externes Sortieren



Sortieren-Mischen

Bei vielen externen Sortiermethoden kommt die folgende allgemeine Strategie zur Anwendung: Realisiere einen ersten Durchlauf durch die zu sortierende Datei, zerlege sie dabei in Blöcke, die ungefähr die Größe des internen Speichers haben, und sortiere diese Blöcke. Mische dann die sortierten Blöcke durch Ausführung mehrerer Durchläufe durch die Datei zusammen, wobei nach und nach größere sortierte Blöcke erzeugt werden, bis die ganze Datei sortiert ist. Der Zugriff auf die Daten wird meist sequentiell realisiert, eine Eigenschaft, dank der diese Methode für die meisten externen Einheiten geeignet ist. Algorithmen für das externe Sortieren verfolgen das Ziel, die Zahl der Durchläufe durch die Datei zu verringern und die Kosten eines einzelnen Durchlaufs so zu reduzieren, daß sie den Kosten einer Kopie möglichst nahe kommen.

Da der größte Teil der Kosten einer externen Sortiermethode durch die Ein- und Ausgabe entsteht, können wir ein grobes Maß für die Kosten einer Misch-Sortier-Methode erhalten, indem wir zählen, wie oft jedes Wort in der Datei gelesen oder geschrieben wird (Anzahl der Durchläufe durch alle Daten). Für viele Anwendungen erfordern die von uns betrachteten Methoden etwa zehn oder weniger solcher Durchläufe. Wir sind daher selbst dann an Methoden interessiert, wenn diese nur einen einzigen Durchlauf eliminieren können. Weiterhin kann die Laufzeit des gesamten externen Sortierverfahrens leicht anhand der Laufzeit geschätzt werden, die bei einem Vorgang von der Art der oben vorgeschlagenen Übung »Kopie einer Datei in umgekehrter Reihenfolge« benötigt wird.


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