|
Allgemein
Was ist Sortieren überhaupt?br />
Niklaus Wirth definiert Sortieren wie folgt:
\"Unter Sortieren versteht man allgemein den Prozess des Anordnens einer gegebenen Menge von Objekten in einer bestimmten Ordnung.\" [1], 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:
Telefonbücher,
Wörterbücher,
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:
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.
Speicherplatz
Wird eine Kopie der Sortierfolge im Hauptspeicher gehalten?
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
finde das kleinste Element in der Folge/Restfolge und tausche es mit dem ersten Element der Folge/Restfolge
kleinstes Element der Folge/Restfolge an der richtigen Stelle; Restfolge um dieses Element verkleinern
solange Wiederholen, bis Folge durchsucht ist
Beispiel
Insertion Sort
Algorithmus
Folge von links nach rechts durchlaufen
aktuelles Element an die richtige Position in der Folge der bereits betrachteten Elemente bringen
fertig, wenn bei letztes Element eingeordnet ist
Beispiel
Bubble Sort
Algorithmus
Folge von links nach rechts durchlaufen
benachbarte Elemente gegebenfalls vertauschen (wenn linkes Element rechtes Element)
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
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
beliebiges Element wählen (z.B. das ganz rechte)
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
diese beiden Elemente vertauschen
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
die beiden Teilfolgen (links und rechts vom ausgewählten Element) mit derselben Methode sortieren (rekursiv)
Beispiel
Heap Sort
Grundlagen
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.
Heap-Bedingung
Betrachtet man einen bestimmten Knoten, so muß dieser größer als alle seine Nachfolger sein - Wurzel ist größtes Element
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
Aus der gegebenen Folge einen Heap erzeugen
Wurzel mit dem letzten Element vertauschen
Heap-Bedingung wiederherstellen, letztes Element dabei nicht mehr beachten
Wurzel mit dem vorletzten Element vertauschen
Heap-Bedingung wiederherstellen, die letzten beiden Elemente dabei nicht mehr beachten
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:
System: Amiga 500; 7.14 MHz
compiliertes ACE-Programm
Algorithmus
sortiert zufällig invers sortiert N
Selection Sort 0.0585937 0.0585937 0.078125004 25
Insertion Sort 0.0429687 0.0781250 0.1015625
Bubble Sort 0.0585937 0.0820312 0.097656254
Quick Sort 0.0195312 0.0195312 0.019531251
Selection Sort 0.19921875 0.26171876 0.33984376 50
Insertion Sort 0.1796875 0.28125001 0.37890626
Bubble Sort 0.1796875 0.25781251 0.35937501
Quick Sort 0.01953125 0.05859375 0.01953125
Selection Sort 0.41796876 0.57812503 0.80078128 75
Insertion Sort 0.42187501 0.63671878 0.85937503
Bubble Sort 0.42187501 0.60156253 0.82031253
Quick Sort 0.05859375 0.1015625 0.039062502
Selection Sort 0.7226562 1.0390625 1.4179687 100
Insertion Sort 0.7382812 1.1210937 1.5195312
Bubble Sort 0.7382812 1.078125 1.4570312
Quick Sort 0.0820312 0.12109375 0.1015625
Selection Sort 1.640625 2.359375 3.1992187 150
Insertion Sort 1.640625 2.5195312 3.4375
Bubble Sort 1.6992187 2.4804687 3.28125
Quick Sort 0.101562 0.1992187 0.1171875
Selection Sort 2.9375 4.1992187 5.6992187 200
Insertion Sort 2.9375 4.5585937 6.140625
Bubble Sort 3 4.4609375 5.8632812
Quick Sort 0.16015625 0.2773437 0.18359375
Selection Sort 6.582031 10.421875 13.859375 300
Insertion Sort 6.582031 9.539062 2.839843
Bubble Sort 6.761718 10.179687 13.199218
Quick Sort 0.242187 0.437500 0.26171876
Selection Sort 11.71875 16.699218 22.878906 400
Insertion Sort 11.738281 18.28125 24.660156
Bubble Sort 12.039062 17.902343 23.5
Quick Sort 0.359375 0.621093 0.40234376
Selection Sort 18.339843 25.898437 35.78125 500
Insertion Sort 18.339843 28.597656 38.578125
Bubble Sort 18.839843 28 36.742187
Quick Sort 0.421875 0.781250 0.46093751
Selection Sort 73.5625 98.75781 143.5 1000
Insertion Sort 73.55859 113.54296 154.78125
Bubble Sort 75.51953 111.23828 147.40234
Quick Sort 0.90234 1.6796 0.976562
|
