Referat Interne Sortieralgorithmen - Sortierverfahren, Geschwindigkeitsvergleiche

Allgemein

Was ist Sortieren überhaupt?
Niklaus Wirth definiert Sortieren wie folgt:

'Unter Sortieren versteht man allgemein den Prozess des Anordnens einer gegebenen Menge von Objekten in einer bestimmten Ordnung.' , Kapitel 2, Seite 77

Das Sortieren hat in der Datenverarbeitung einen sehr hohen Stellenwert. Circa 25% aller Rechenzeit im kommerziellen Bereich entfällt auf das Sortieren von Daten [2].

An Beispielen zum Sortieren mangelt es nicht:

n      Telefonbücher,

n      Wörterbücher,

n      Verzeichnisse,

Um 'Interne' Sortieralgorithmen anwenden zu können, muß es möglich sein, auf die einzelnen Datensätze direkt zuzugreifen (entweder im Hauptspeicher oder mittels einer geeigneten Datei).
Heutzutage sind schon sehr viele solcher Algorithmen bekannt. Einige sollen hier vorgestellt werden.

Sortierverfahren

Vor der Auswahl eines Sortieralgorithmus sollte man einige Kriterien betrachten:

n      Laufzeit

Die Laufzeit für das Sortieren von n Datensätzen ist abhängig von der Anzahl der Vergleichsoperationen, der Anzahl der Datensatzbewegungen, der Datensatzgröße, usw.

n      Speicherplatz

Wird eine Kopie der Sortierfolge im Hauptspeicher gehalten?

n      Stabilität

Ein Sortierverfahren gilt als 'stabil', wenn bei Elementen mit gleichem Sortier-Schlüssel die ursprüngliche Reihenfolge erhalten bleibt.

Selection Sort (Ripple Sort)

Algorithmus

n      finde das kleinste Element in der Folge/Restfolge und tausche es mit dem ersten Element der Folge/Restfolge

n      kleinstes Element der Folge/Restfolge an der richtigen Stelle; Restfolge um dieses Element verkleinern

n      solange Wiederholen, bis Folge durchsucht ist

Beispiel

Insertion Sort

Algorithmus

n      Folge von links nach rechts durchlaufen

n      aktuelles Element an die richtige Position in der Folge der bereits betrachteten Elemente bringen

n      fertig, wenn bei letztes Element eingeordnet ist

Beispiel

Bubble Sort

Algorithmus

n      Folge von links nach rechts durchlaufen

n      benachbarte Elemente gegebenfalls vertauschen (wenn linkes Element rechtes Element)

n      so lange wiederholen, bis bei einem Durchlauf keine Vertauschungen mehr nötig

Beispiel

Shell Sort

Der Shell Sort-Algorithmus ist eine Erweiterung zum Insertion Sort-Algorithmus. Hier werden, im Gegensatz zum Insertion Sort, weiter entfernte Elemente betrachtet.

'H-sortierte' Folge: betrachtet man jedes H-te Element, müssen diese Elemente eine sortierte Reihe bilden.
Beispiel: 4-sortierte Folge

das 1., 5., 9., 13., Element bilden eine sortierte Reihe
das 3., 7., 11., 15., Element bilden eine sortierte Reihe

Algorithmus

n      Aus der ursprünglichen Folge wird eine Reihe von H-sortierten Folgen erzeugt, wobei H z.B. die Werte 1093, 364, 121, 40, 13, 4, 1 durchläuft (günstige Werte für H wurden empirisch ermittelt).

Beispiel

Quick Sort

Algorithmus

n      beliebiges Element wählen (z.B. das ganz rechte)

n      Mittels L-Zeiger Folge von links kommend durchsuchen, bis Element gefunden, das größer als das ausgewählte ist, mittels R-Zeiger Folge von rechts kommend durchsuchen, bis Element gefunden, das kleiner als das ausgewählte ist

n      diese beiden Elemente vertauschen

n      Vorgang wiederholen, bis sich die beiden Zeiger 'treffen' und danach ausgewähltes Element mit dem, auf das der R-Zeiger verweist, vertauschen; Ausgewähltes Element ist an seiner richtigen Position

n      die beiden Teilfolgen (links und rechts vom ausgewählten Element) mit derselben Methode sortieren (rekursiv)

Beispiel

Heap Sort

Grundlagen

n      Heap

Hier: Ein nicht sortierter möglichst vollständiger (es dürfen nur in der untersten Ebene Blätter fehlen) Baum, für den die Heap-Bedingung erfüllt ist.

n      Heap-Bedingung

Betrachtet man einen bestimmten Knoten, so muß dieser größer als alle seine Nachfolger sein - Wurzel ist größtes Element

n      Hinweis

Elemente werden 'serialisiert' (d.h. zuerst alle Knoten der 1. Ebene, danach alle Knoten der 2. Ebene, von links nach rechts) in einem Array gespeichert - Die Nachfolger eines Knotens an der Position i befinden sich an den Positionen 2*i und 2*i+1

Algorithmus

n      Aus der gegebenen Folge einen Heap erzeugen

n      Wurzel mit dem letzten Element vertauschen

n      Heap-Bedingung wiederherstellen, letztes Element dabei nicht mehr beachten

n      Wurzel mit dem vorletzten Element vertauschen

n      Heap-Bedingung wiederherstellen, die letzten beiden Elemente dabei nicht mehr beachten

n      usw.

Beispiel

Geschwindigkeitsvergleiche

In der folgenden Tabelle sind für vier Sortieralgorithmen die Zeiten (in Sekunden) für ein bestimmtes n aufgelistet. Die zu sortierenden Folgen sind den Algorithmen sortiert/zufällig/invers sortiert übergeben worden.

Alle Messungen wurden unter folgenden Bedingungen durchgeführt:

n      System: Amiga 500; 7.14 MHz

n      compiliertes ACE-Programm

Anhang

Wirth, Niklaus

Algorithmen und Datenstrukturen

B.H. Teubner, Stuttgart

4. Auflage, 1995

Ottmann, Thomas

Algorithmen und Datenstrukturen

Bibliographisches Institut & F.A. Brockhaus AG

2. Auflage, 1993