Externes Sortieren

Sortieralgorithmen für Daten auf externen Speichern

1. Einleitung

2. Sortierverfahren

2.1. Direktes Mischen

2.1.1. Algorithmus

2.1.2. Beispiel

2.2. Natürliches Mischen

2.2.1. Unterschiede

2.2.2. Algorithmus

2.2.3. Beispiel

2.3. M-Wege-Mischen bzw. Ausgeglichenes Mehrweg-Mischen

2.3.1. Beschreibung

2.3.2. Algorithmus:

2.3.3. Beispiel

2.4. Merphasen Sortieren

2.4.1. Beschreibung

2.4.2. Beispiel

2.5. Ein einfacherer Weg

Einleitung

Sind die Daten, die sortiert werden sollen, zu groß um im internen Speicher gehalten zu werden, muß man auf externe Sortieralgorithmen zurückgreifen. Man kann dabei nicht auf ein beliebiges einzelnes Element zugreifen, da die Datei nur sequentiell lesbar und beschreibbar ist.

Die Effizienz eines Algorithmus hängt von der Anzahl der Übertragungen zwischen dem Arbeitsspeicher und dem peripheren Speicher ab. Je weniger übertragen werden muß, um so Effizienter ist er.

Die bedeutendste Methode ist das Sortieren durch Mischen, auch merge sort genannt, von der es einige Variationen gibt:

Direktes Mischen

Natürliches Mischen

M-Wege Mischen bzw. Ausgeglichenes Mehrweg-Mischen

Merphasen Sortieren

Sortierverfahren

Direktes Mischen

Algorithmus

Schritt 1:            Zerlege die Sequenz A in zwei Hälften B und C.

Schritt 2:            Mische B und C durch Kombination einzelner Elemente zu geordneten Paaren.

Schritt 3:            Schreibe die gemischte Sequenz auf A und wiederhole die Schritte 1 und 2, wobei die geordneten Paare zu geordneten Quadrupeln zusammengefaßt werden.

Schritt 4:            Wiederhole die voranstehenden Schritte durch mischen der Quadrupel zu Octupel und fahre damit so lange fort bis die Sequenz geordnet ist. Bei jedem Schritt wird die Länge der gemischten Sequenz verdoppelt.

Beispiel

Band A: 9 5 2 8 9 0 1 2 unsortierte Sequenz

Band B:

Band C:

Band B:  9|2|9|1

Band C:  5|8|0|2

Band A: 5 9|2 8|0 9|1 2

Band B: 5 9|0 9

Band C: 2 8|1 2

Band A: 2 5 8 9|0 1 2 9

Band B: 2 5 8 9

Band C:  0 1 2 9

Band A: 0 1 2 2 5 8 9 9 sortierte Sequenz

Natürliches Mischen

Unterschiede

Beim Natürlichen Mischen (natural merge) werden bereits vorhandene sortiere Teilsequenzen berücksichtigt. Die Länge aller gemischten Teilsequenzen im k-ten Durchlauf ist gleich k², unabhängig davon, ob bereits längere Teilsequenzen geordnet sind und gemischt werden könnten.

Eine Teilsequenz wird Lauf genannt, wenn sie folgende Bedingungen erfüllt:

a[n] <= a[n+1] für n = ij-1

a[i-1] > a[i] i = Beginn der Sequenz

a[j]         > a[j+1] j = Ende der Sequenz

Algorithmus

1. Schritt:           Mische die zu sortierenden Daten (Band A) in Läufe und schreibe die Läufe abwechselnd in Band B und C.

2. Schritt:           Sortiere jeweils einen Lauf aus B und C zu einem neuen Lauf und schreibe die Läufe abwechselnd in Band A. Wiederhole so lange, bis das Band sortiert ist.

Beispiel

Band A: 9 5 2 8 9 0 1 2 unsortierte Sequenz

Band B:

Band C:

Band B: 9|2 8 9

Band C:  5|0 1 2

Band A: 5 9|0 1 2 2 8 9

Band B: 5 9

Band C:  0 1 2 2 8 9

Band A: 0 1 2 2 5 8 9 9 sortierte Sequenz

M-Wege-Mischen bzw. Ausgeglichenes Mehrweg-Mischen

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.

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.

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

Merphasen Sortieren

Beschreibung

Ein Problem beim M-Wege-Mischen ist, daß man 2*m Bänder benötigt. Um diesen Nachteil aufzuheben wurden verschiedene Algorithmen entwickelt. Die bekannteste Methode ist das Mehrphasen Sortieren (polyphase sort).

Die grundlegende Idee besteht darin, daß zu Beginn ein Band, das Ausgabeband, leer bleibt. Auf die restlichen Bänder werden die zu sortierenden Daten vorsortiert verteilt und danach auf das Ausgabeband gemischt. Sind von einem Eingabeband alle Daten gelesen wird es zum Ausgabeband.

Beispiel

Sequenz: 04 06 05 08 09 03 11 20 22

Band A: 04 06|03 11 20 22

Band B: 05 08 09

Band C:

Band A: 03 11 20 22

Band B:

Band C: 04 05 06 08 09

Band A:

Band B: 03 04 05 06 08 09 11 20 22

Band C: 

Ein einfacherer Weg

Viele Computersysteme verfügen über eine große virtuelle Speicherkapazität, die man beim Implementieren einer Methode für das Sortieren sehr großer Dateien verwenden kann. Es können alle Daten direkt adressiert werden und es liegt in der Verantwortung des Systems, daß die Daten bei Bedarf in den Hauptspeicher kommen. Somit sollte die Strategie der Anwendung einer einfachen internen Sortiermethode für das Sortieren von auf Platten befindlichen Dateien in einem guten Virtuellen Speichersystem ernsthaft in Erwägung gezogen werden.