Externes Sortieren

Beschreibung / Inhalt
Das Dokument beschreibt verschiedene Sortieralgorithmen für Daten auf externen Speichern. Der Fokus liegt dabei auf der Effizienz der Algorithmen, die von der Anzahl der Übertragungen zwischen Arbeitsspeicher und peripherem Speicher abhängt. Der bedeutendste Algorithmus ist das Sortieren durch Mischen, auch merge sort genannt. Es werden verschiedene Variationen wie das direkte Mischen, das natürliche Mischen, das M-Wege-Mischen bzw. das ausgeglichene Mehrweg-Mischen und das Merphasen-Sortieren behandelt und deren jeweilige Algorithmen beschrieben. Es werden auch Beispiele für die Anwendung der Algorithmen gegeben. Ebenfalls wird ein einfacherer Weg beschrieben, der die große virtuelle Speicherkapazität von Computersystemen nutzt, um alle Daten direkt adressieren zu können, was das Sortieren von großen Dateien auf Platten erleichtert.
Direkt das Referat aufrufen

Auszug aus Referat
Externes Sortieren Sortieralgorithmen für Daten auf externen Speichern 1. 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 2. Sortierverfahren 2.1. Direktes Mischen 2.1.1. 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. 2.1.2. 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 ...
Direkt das Referat aufrufen