Interne sortieralgorithmen - der kern der sache

  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." [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       Anhang     [1] Wirth, Niklaus Algorithmen und Datenstrukturen B.H. Teubner, Stuttgart 4. Auflage, 1995   [2] Ottmann, Thomas Algorithmen und Datenstrukturen Bibliographisches Institut & F.A.

Brockhaus AG 2. Auflage, 1993

Suchen artikel im kategorien
Schlüsselwort    Kategorien    - kategorien - astronomiebiographienbiologiechemiedeutschenglischfranzosischgeographiegeschichtehauswirtschaftinformatikitalienischkunstlateinliteraturmathematikmusikphilosophiephysikpolitikpsychologierechtsozialkundesporttechnikwirtschaft	•  Zusammenfassung Der Vorleser  •  sachtextanalyse  •  interpretation zwist  •  Fabel interpretation  •  literarische charakteristik  •  interpretation bender heimkehr  •  felix lateinbuch  •  interpretation der taucher von schiller  •  textbeschreibung  •  charakterisierung eduard selicke

Anmerkungen: * Name: * Email: URL: * Diskussion: (NO HTML)

| impressum | datenschutz