Atari Logo
Atari Computer

Hauptseite -
Welches System? -
Hardware -
Software -
Emulatoren -
Internet
MausNet
Programmieren
Verweise
Über

Algorithmen

Home Felder sortieren Quicksort Intervallhalbierung

2.6 Mergesort

Übersteigt der Speicherbedarf für die Daten den vorhandenen Rechnerspeicher, müssen die Daten auf mehrere Dateien aufgeteilt werden. Jede einzelne Datei darf nur so groß sein, das sie in den Rechnerspeicher paßt und dort sortiert werden kann. Anschließend werden die einzelnen Dateien wieder zusammengeführt.

  1. Lies soviel Daten aus der Datei, wie im Speicher sortiert werden können.
  2. Sortiere diese Daten und schreibe sie in eine eigene Datei.
  3. Führe die Schritte 1 - 2 solange aus, wie noch Daten vorhanden sind.
  4. Lies aus jeder der erzeugten Dateien ein Element.
  5. Schreibe das kleinste Element und lies ein neues aus der Datei, aus der das kleinste stammt.
  6. Führe die Schritte 4 - 5 solange aus, bis alle sortierten Teildateien ausgelesen sind. Sobald eine dieser Dateien leer ist, wird sie in Schritt 4 und 5 nicht mehr berücksichtigt.

Die Beispiele benutzen nur 2 sortierte Dateien. Der Algorithmus läßt sich auch so implementieren, daß immer nur jeweils 2 Dateien verschmolzen werden. Der Sortieralgorithmus für das Sortieren im Speicher wurde weggelassen. Es kann einer der oben aufgeführten verwendet werden. Aufgrund der großen Datenmenge (sie passen komplett nicht in den Speicher!) sollte ein möglichst schneller gewählt werden.

Beispielcode
Home Felder sortieren Quicksort Intervallhalbierung


Best viewed with any browser English version not yet available.

Änderungen und Irrtümer vorbehalten. Letzte Änderung:
14 September 2001.
Home - Mail an den Webmaster - Impressum