|
2.3.1. Beschreibung
Der Aufwand für sequentielles Sortieren ist proportional zur Zahl der benötigten Durchläufe, da bei jedem Durchgang die benötigten Daten kopiert werden müssen. Ein Weg um diese Anzahl zu verringern ist die Verwendung von mehreren Files bzw. Bändern. Dafür müssen jedoch m Blöcke gleichzeitig im Arbeitsspeicher Platz haben und m * 2 Bänder/Files zur Verfügung stehen.
2.3.2. Algorithmus:
1. Schritt: Man liest Blöcke aus m Datensätzen aus der Datei, sortiert diese (internes Sortieren!) und schreibt diese abwechseln auf die ersten m Bänder. (Bei m = 3 auf Band A - C)
2. Schritt: Der erste Datensatz jedes Eingabebandes wird gelesen und der kleinste Ausgegeben. Danach wird der nächste Datensatz von dem Band eingelesen von dem der kleinste Ausgegeben wurde. Ist das Ende eines aus m Datensätzen Bestehenden Blockes erreicht, wird das Betreffende Band ignoriert, bis die anderen Bänder verarbeitet worden sind.
3. Schritt: Die Schritte 1 und 2 werden so lange wiederholt bis die Datensätze sortiert sind.
2.3.3. Beispiel
m = 3 (6 Bänder)
Sequenz: 01 19 15 18 20 09 14 07 01 14 04 13 05 18 07 09 14 07 05 24 01 13 16 12 05
Band A: 01 15 19|04 13 14|01 05 24
Band B: 09 18 20|05 07 18|12 13 16
Band C: 01 07 14|07 09 14|05
Band D:
Band E:
Band F:
Band A:
Band B:
Band C:
Band D: 01 01 07 09 14 15 18 19 20
Band E: 04 05 07 07 09 13 14 14 18
Band F: 01 05 05 12 13 16 24
Sortiert: 01 01 01 04 05 05 05 07 07 07 09 09 12 13 13 14 14 14 15 16 18 18 19 20 24
|
