|
1.1 Parameter der Leistungsfähigkeit/
Laufzeit: ist die Zeit, die ein Algorithmus dazu benötigt eine Anzahl von n Elementen zu sortieren.
Stabilität: Ein Sortierverfahren wird stabil genannt, wenn es die Reihenfolge gleicher Schlüssel in der Datei beibehält, z.B. eine Menge von Schülern wird nach Noten (Schlüssel) sortiert. Bei einer stabilen Methode sind die Schüler noch immer in alphabetischer Reihenfolge in der Liste angeführt; bei einer instabilen ist von einer alphabetischen Reihenfolge keine Rede mehr.
1.2 Insertion Sort
Eine unsortierte bestehende Liste wird systematisch vom Anfang weg sortiert, indem die nächstkleinere Zahl links, die nächstgrößere Zahl rechts eingeordnet wird.
Der Insertion Sort ist sehr langsam, da nur benachbarte Elemente ausgetauscht werden.
1.3 Selection Sort
= Sortieren durch direktes Auswählen.
Der Selection Sort sucht aus einem Feld das kleinste Element und tauscht es gegen das an erster Stelle stehende Element. Dann wird das zweitkleinste Element gesucht und gegen das an zweiter Stelle stehende Element getauscht, u.sw. bis das gesamte Feld sortiert ist.
1. Durchgang 5 9 7 6 3
2. Durchgang 1 9 7 8 6
3. Durchgang 1 3 7 8 6
4. Durchgang 1 3 5 8 9
5. Durchgang 1 3 5 6 9
6. Durchgang 1 3 5 6 7 8 9
1.4 Bubble Sort
=Sortieren durch direktes Austauschen
Beim durchlaufen der Datei werden jeweils 2 Elemente paarweise verglichen. Wenn dabei das linke Element kleiner ist als das rechte, wird es vertauscht, wenn nicht, wird weitergegangen, bis das rechte Ende des Feldes erreicht ist.
1.5 Indirect Sort
Beim Insertion Sort sortiert man einen Index auf die Tabelle.
1.6 Shell Sort
Der Shell Sort stellt das schnellste Sortierverfahren dar, wobei niemand weiß wieso. Es ist auch das einzige Sortierverfahren, das sich Mathematisch nicht erklären läßt und in keine Formel packen läßt.
Der Insertion Sort ist sehr langsam, weil nur benachbarte Elemente ausgetauscht werden. Wenn sich zum Beispiel das kleinste Element zufällig am Ende des Feldes befindet, so werden n Schritte benötigt, um es dorthin zu bekommen, wo es hingehört. Shellsort ist einfach eine Erweiterung von Insertion Sort, bei dem eine Erhöhung der Geschwindigkeit dadurch erzielt wird, daß ein Vertauschen von Elementen ermöglicht wird, die weit voneinander entfernt sind.
Es wird eine Schrittreihenfolge gewählt (z.B. 13-h). Vom Ersten Element ausgehend wird jedes h-te Element herausgenommen und in die richtige Reihenfolge gebracht. Dieser Vorgang wird mit jedem Element durchgeführt bis man am Ende angelangt ist. Dann wird eine neue Schrittreihenfolge gewählt (kleiner als die erste z.B.: 5-h) und der Prozeß beginnt von vorne.
Aus Versuchsreihen hat es sich herausgestellt, daß die Distanzen 1,4,13,40,121,... (3n+1) das schnellste Sortierverfahren darstellen. Es ist allerdings möglich, den Shellsort mit anderen Folgen von Distanzen noch effizienter zu machen. Doch es ist für relativ große n schwer, das Programm um mehr als 20% schneller zu machen.
1.7 Quick Sort
=rennt rekursiv durch
1.7.1
Beim Quick Sort werden die 2 Teilfelder getrennt durchgegangen. Der linke Teil von links nach rechts, der rechte Teil von rechts nach links. Es wird immer dann unterbrochen, wenn ein Element kleiner ist als das Partitionselement ist. Wenn die beiden im Diagramm kleinen, nach oben zeigenden Pfeile stehengeblieben sind, werden die zwei Elemente vertauscht.
Der Nachteil des Quick Sort besteht darin, daß er rekursiv und störanfällig ist und daß er im Worst Case n² Operationen benötigt.
1.8 Distribution Counting
Eine sehr spezielle Situation, für die ein einfacher Sortieralgorithmus existiert, wenn eine Datei mit n Datensätzen viele verschiedene Zahlenschlüssel hat. Die Idee besteht darin, die Anzahl der Schlüssel mit jedem Wert zu ermitteln und dann die Ergebnisse der Zählung zu verwenden, um bei einem zweiten Durchlauf durch die Datei die Datensätze in die richtige Postition zu bringen.
|
