Thema 3: Sortierverfahren I
- SelectionSort
- InsertionSort
- BubbleSort
- QuickSort
- HeapSort
Aufgabe:
Messe jeweils die Zeiten für die Sortierung einer (fast) sortierten, einer umgekehrt sortierten, sowie einer zufällig erzeugten Folge. Biete dem Benutzer eine Auswahl der Algorithmen oder einen vollständigen Vergleich aller Algorithmen an. Stelle die Ergebnisse übersichtlich dar und erlaube die Auswahl der Größe der zu sortierenden Folgen.
1 Einleitung
Grundlage für diese Ausarbeitung ist ein Programm, mit dem man Zahlenfolgen nach verschiedenen Algorithmen sortieren kann und das die durchschnittliche Zeit, die für den Vorgang benötigt wird, ausgibt. Bei Ausführung des Programms wird der Benutzer gefragt, ob er die im Programm als Standard implementierte vorsortierte bzw. rückwärts sortierte Folge benutzen, oder ob er selbst eine Folge von Zahlen eingeben und dann sortieren möchte. Ist diese Entscheidung getroffen, steht nun noch die Auswahl an, nach welchem Algorithmus die Folge sortiert werden soll. Zur Auswahl stehen an dieser Stelle BubbleSort, SelectionSort, InsertionSort, QuickSort und HeapSort. Außerdem wurde hier ein weiterer Auswahlpunkt ‚Vergleich‘ eingefügt. Dieser gibt dem Benutzer die Möglichkeit zum Vergleich der Algorithmen bezüglich der von Ihnen zum sortieren benötigten Zeiten. Die Zeiten werden mit den dazugehörigen Algorithmennamen ausgegeben. Die hieraus resultierenden Versuchsergebnisse werden im letzten Teil dieser Arbeit ausgewertet. Im folgenden werde ich auf die verwendeten Sortieralgorithmen genauer eingehen und ihre Funktionsweise erläutern. Als erstes zu den drei sogenannten elementaren Verfahren.
1. Sortierverfahren und ihre Funktionsweise
1.1 SelectionSort (Sortieren durch auswählen):
Dieser Algorithmus benötigt ca. n²/2 Vergleiche, aber nur n Austauschoperationen. Im ungünstigsten Fall ist die Komplexität aber auch O(n²). Nun zur Funktionsweise des Algorithmus.
Ziel der inneren Schleife ist es, das kleinste Element der Folge zu finden. Dies geschieht folgendermaßen: Das erste Element der Folge wird als Minimum gespeichert und mit allen nachfolgenden Elementen verglichen. Falls auf ein kleineres Element gestoßen wird, wird dieses mit dem an der ersten Stelle stehenden Element ausgetauscht und als neues Minimum gespeichert. Dann wird die Suche nach kleineren Elementen mit den neuen Parametern fortgesetzt. Nach dem ersten Durchlauf steht dann das kleinste Element auf der ersten Stelle des Feldes, also auf seiner endgültigen Position, und bedarf keiner Beachtung mehr. Dies wird wie bei BubbleSort durch die äußere Schleife erledigt. Der Anfangsindex für das Sortieren wird mit jedem Durchlauf um erhöht, was bewirkt, daß im zweiten Durchlauf das zweite Element als Anfangsminimum gesetzt wird und dann erst ab dem dritten Element nach kleineren Elementen gesucht wird. Dadurch werden wie bei BubbleSort einigen Schleifendurchläufe gespart. Da bei SelectionSort jedes Element nur einmal bewegt wird, ist dies ein bevorzugtes Verfahren um Dateien mit großen Datensätzen und kleinen Schlüsseln zu sortieren.
1.2 BubbleSort (Sortieren durch austauschen):
BubbleSort vergleicht immer ein Element der Folge mit dem vorigen. Ist das vorige Element größer, werden beide Elemente vertauscht. Dann wird der Index um 1 erhöht, das heißt in der Folge wird um ein Element nach rechts gegangen. Dieses Element wird wiederum mit seinem Vorgänger verglichen und gegebenenfalls ausgetauscht. Mit dieser Methode wird das größte Element aus dem Feld gesucht und an die letzte Stelle des Feldes gesetzt. Dieses Element steht nun an seiner endgültigen Stelle und braucht im weiteren Verlauf des Programmes also nicht mehr beachtet werden. Dies wird durch die äußere Schleife realisiert. Diese ermöglicht, daß ein Index nach jedem durchlauf um 1 verringert wird, was zur Folge hat, daß das Feld nur noch bis zur Stelle vor dem als letztes einsortierten Element sortiert wird.
Die Nachteile von BubbleSort liegen in der Komplexität. Der Algorithmus benötigt im schlechtesten Fall, sowie im Durchschnitt n²/2 Vergleiche und genauso viele Austauschoperationen. Dies entspricht einer Komplexität O(n²) (n sei die Anzahl der Elemente der Folge). Der ungünstigste Fall für BubbleSort ist eine umgekehrt sortierte Folge. Dafür ist BubbleSort für bereits sortierte Folgen von linearer Komplexität.
1.3 InsertionSort (Sortieren durch einfügen):
Dieser Algorithmus sortiert die Folge, indem er das aktuelle Element an die richtige Stelle zwischen den bereits sortierten Elementen einfügt. Daher auch der Name. Die innere Schleife ist eine „whileTrue - Schleife“ sortiert jeweils das aktuelle Element in die bis dahin sortierte Folge nach folgender Methode ein. Man nehme ein Element (Voraussetzung alle Elemente links von diesem sind bereits sortiert), speichere es temporär und vergleiche es mit dem Element davor. Ist dieses größer als das aktuelle Element, wird es um eine Stelle nach rechts geschoben. Nun wird das aktuelle Element mit dem nächsten links folgendem Verglichen und so weiter. Dies wird wiederholt, bis auf ein kleineres Element gestoßen wird, welches nicht nach rechts verschoben wird. In die nun in der Folge vorhandene Lücke wird das zwischen-gespeicherte (aktuelle) Element eingefügt. Für den Fall, daß man gerade mit dem bisher kleinsten Element arbeitet, mußte bei der Implementation der inneren Schleife eine extra Abbruchbedingung eingefügt werden. Der im Feld nach links wandernde Zeiger würde in diesem Fall irgendwann auf die Stelle 0 zeigen. Dies führt bei Smalltalk zu einer Fehlermeldung. Deshalb wird vor erneutem Aufruf getestet, ob die Stelle links neben dem Zeiger noch innerhalb des Feldes liegt. Wenn nicht, ist das aktuelle Element das momentan kleinste und kann daher an der nun freien ersten Stelle des Feldes eingefügt werden. Hier kommt nun auch die künstlich erzeugte Abbruchbedingung zum Einsatz, um aus der whileTrue - Schleife heraus zu kommen. Die äußere Schleife sorgt dafür, daß das Sortieren mit dem nächsten Element fortgesetzt wird.
Es benötigt im schlechtesten Fall n²/2 Vergleiche und n²/4 Austauschoperationen. Im Durchschnitt benötigt InsertionSort sogar nur halb so viele Operationen und Vergleiche. Somit ist InsertionSort schneller als die beiden zuvor betrachteten Algorithmen. Der Algorithmus ist für bereits vorsortierte Folgen linear, d.h., er kann aus der bereits vorhandenen Ordnung Nutzen ziehen.
1.4 QuickSort
Der Algorithmus der QuickSort zu Grunde liegt, arbeitet nach dem „Divide & Conquer“ (Teile und Herrsche) - Verfahren. Das heißt soviel wie, teile das Feld in zwei Hälften und sortiere diese separat. QuickSort ist außerdem rekursiv, es ruft sich immer wieder selbst auf. Zuerst zum aufteilen des Feldes. In der vorliegenden Implementation wird mit zwei Zeigern gearbeitet. Das letzte Element wird gespeichert und soll nach dem ersten Durchlauf an seiner endgültigen Stelle stehen. Dann sucht man von links ausgehend das erste Element, welches größer ist als das Gespeicherte. Dann wird vom vorletzten Element ausgehend nach rechts nach einem kleineren Element gesucht. Werden beide gefunden, ohne das der Index der von rechts ausging kleiner oder gleich dem der von links ausging ist, werden diese beiden Element vertauscht. Nun wird diese Suche fortgesetzt und Elemente werden gegebenenfalls ausgetauscht, bis beide Indizes gleich sind. In diesem Algorithmus zeigen in dem Fall immer beide Indizes auf ein Element, welches größer ist als das Gespeicherte. Es wird mit dem Element auf der letzten Stelle des Feldes vertauscht, welches nun auf seiner endgültigen Position steht. Alle Elemente links von ihm sind kleiner und alle die rechts von ihm stehen sind größer. Durch die rekursiven Aufruf von QuickSort werden die Teilfolgen links und rechts von dem eben sortierten Element nach gleichem Schema sortiert. Die Rekursion bricht ab, wenn in den Teilfolgen nur noch zwei Elemente stehen, welche beide auf ihre endgültige Stelle positioniert werden.
QuickSort benötigt im Schnitt (2n log n) Vergleiche. Im schlechtesten Fall (rückwärts sortierte Folge) hat es eine Komplexität O(n²) und im Durchschnitt O(n log n). Den vorliegenden Algorithmus kann man noch effektiver machen, indem man nicht das letzte Element der Folge als Vergleichselement genommen wird, sondern das mittlere aus drei zufällig gewählten, um die Wahrscheinlichkeit des schlechtesten Falles auf ein Minimum zu reduzieren. Eine andere Verbesserungsmöglichkeit besteht darin, die Rekursion zu beseitigen.
1.5 HeapSort
Ein Heap ist eine Datenstruktur, die als binärer Baum darstellbar ist. Dieser binäre Baum muß der Heapeigenschaft genügen, welche aussagt, daß das größte Element an der Wurzel stehen muß und das dann diesem Knoten nach unten recht und links zwei Knoten folgen, deren Wert kleiner ist, als der des sogenannten „parents“ oder Vorgängers. Jeder der Nachfolger, oder auch „children“ genannten Knoten hat wiederum maximal zwei vom Wert kleinere Nachfolger.
Der Aufbau dieses Heaps aus der zu sortierenden Folge, geschieht in der vorliegenden Implementation, in der Methode HEAPSORT. Hier werden die Elemente der ersten Hälfte der Folge nacheinander an die Wurzel gesetzt und diese versickern dann in der Methode DOWNHEAP bis zu einer Position im Heap, an der sie die Heapbedingung erfüllen, daß heißt, bis ein Element vor ihm steht, das größer und die beiden nachfolgenden Elemente kleiner sind. Nun werden alle Elemente von rechts an der Reihe nach an die Wurzel des Heaps gesetzt und dann wiederum mit DOWNHEAP versickert. Nach dieser Prozedur ist die Folge als ein der Heapbedingung genügender binärer Baum in Form einer Liste aufgebaut.
Durch die in der Hauptmethode HEAP aufgerufene Schleife wird realisiert, daß das jeweils größte Element, welches an der Wurzel steht, gespeichert und dann entfernt. Anschließend wird das letzte Element des Heaps an die Wurzel gesetzt und mit DOWNHEAP solange nach unten gereicht, bis der Baum wieder der Heapbedingung genügt. Der Heap wird so um eine Stelle verkürzt. Das gespeicherte Element wird nun zur Sicherheit mit dem Element, welches jetzt an der Wurzel des Heaps steht verglichen, da ansonsten Fehler aufgrund der bisher vernachlässigten Betrachtung von rechtem und linkem Nachfolger auftreten können. Ist das Element an der Wurzel größer als das gespeicherte, werden beide vertauscht, ansonsten wird das Gespeicherte in die Ergebnisfolge an die erste Stelle angefügt. Der ursprüngliche Algorithmus wird somit Element für Element vom Größten an abgebaut und die Elemente entsprechend an den Anfang der Ergebnisfolge angefügt.
HeapSort ist einer der beständigsten Algorithmen, besonders, wenn es um große Folgen geht. Er ist nicht so sehr von der Beschaffenheit der zu sortierenden Folge abhängig, wie die anderen betrachteten Algorithmen. Aber HeapSort spielt seine Vorteile gegenüber QuickSort erst beim sortieren von großen Folgen mit mehr als 500 Elementen aus. Hier kommt es zu erkennbaren Vorteilen gegenüber den anderen Algorithmen. HeapSort hat die Komplexität O(n log n). Bei sehr kleinen Folgen (bis 70-80 Elemente) dagegen hat das hier implementierte HeapSort Nachteile und läuft wesentlich langsamer als die meisten anderen Algorithmen.
| Sortierverfahren |
300 Elem. |
200 Elem. |
100 Elem. |
50 Elem. |
20 Elem. |
| Quicksort |
23,72 ms |
10,51 ms |
2,68 ms |
0,81 ms |
0,19 ms |
| Selectionsort |
40,75 ms |
19,05 ms |
4,75 ms |
1,2 ms |
0,21 ms |
| Insertionsort |
0,48 ms |
0,39 ms |
0,19 ms |
0,1 ms |
0,03 ms |
| Bubblesort |
40,24 ms |
18,34 ms |
4,58 ms |
1,17 ms |
0,2 ms |
| Heapsort |
11,01 ms |
6,79 ms |
3,04 ms |
1,44 ms |
0,49 ms |
Besonders auffällig ist, daß Insertionsort erheblich schneller ist, als alle anderen Sortieralgorithmen. Dies liegt natürlich an seiner Arbeitsweise, denn bei einer vorsortierten Folge ist mit Insertionsort nicht viel zu tun. Tauscht eben nur nicht sortierte Elemente um.
Quicksort und Heapsort sind auch noch recht schnell.
| Sortierverfahren |
300 Elem. |
200 Elem. |
100 Elem. |
50 Elem. |
20 Elem. |
| Quicksort |
23,6 ms |
10,73 ms |
3,03 ms |
0,86 ms |
0,21 ms |
| Selectionsort |
39,63 ms |
18,45 ms |
4,46 ms |
1,22 ms |
0,22 ms |
| Insertionsort |
62,72 ms |
28,32 ms |
7,2 ms |
1,8 ms |
0,28 ms |
| Bubblesort |
117,48 ms |
53,21 ms |
13,28 ms |
3,17 ms |
0,57 ms |
| Heapsort |
9,66 ms |
6,35 ms |
2,84 ms |
1,33 ms |
0,44 ms |
Bei einer großen Anzahl von Elementen schlägt Heapsort die anderen Sortieralgorithmen deutlich. Quicksort ist auch recht schnell.
| Sortierverfahren |
300 Elem. |
200 Elem. |
100 Elem. |
50 Elem. |
20 Elem. |
| Quicksort |
5,44 ms |
2,94 ms |
1,14 ms |
0,53 ms |
0,15 ms |
| Selectionsort |
41,17 ms |
18,57 ms |
4,75 ms |
1,32 ms |
0,24 ms |
| Insertionsort |
34,52 ms |
15,57 ms |
9,94 ms |
0,98 ms |
0,20 ms |
| Bubblesort |
84,54 ms |
37,64 ms |
8,25 ms |
2,26 ms |
0,41 ms |
| Heapsort |
10,57 ms |
6,7 ms |
3,12 ms |
1,39 ms |
0,49 ms |
Quicksort und Heapsort sind am schnellsten.
| Sortierverfahren |
300 Elem. |
200 Elem. |
100 Elem. |
50 Elem. |
20 Elem. |
| Quicksort |
3,08 ms |
2,13 ms |
0,95 ms |
0,43 ms |
0,15 ms |
| Selectionsort |
42,27 ms |
18,45 ms |
4,87 ms |
1,26 ms |
0,29 ms |
| Insertionsort |
34,79 ms |
14,27 ms |
3,91 ms |
0,89 ms |
0,18 ms |
| Bubblesort |
85,73 ms |
36,31 ms |
9,5 ms |
2,15 ms |
0,34 ms |
| Heapsort |
10,99 ms |
6,68 ms |
3,1 ms |
1,38 ms |
0,61 ms |
Quicksort und Heapsort wie bei der benutzerdef. Folge am schnellsten, denn im Prinzip handelt es sich hierbei, um die selbe Art von Folgen.
Beim Vergleich aller Folgen fällt auf, daß Heapsort und Quicksort die schnellsten Sortieralgorithmen sind.
Durchschnitt aller Folgen (vorsortierte, rückwärtssortierte, benutzerdef., zufällige):
| Sortierverfahren |
300 Elem. |
200 Elem. |
100 Elem. |
50 Elem. |
20 Elem. |
| Quicksort |
13,96 ms |
6,58 ms |
1,95 ms |
0,66 ms |
0,18 ms |
| Selectionsort |
40,95 ms |
18,63 ms |
4,71 ms |
1,25 ms |
0,24 ms |
| Insertionsort |
33,13 ms |
12,14 ms |
5,21 ms |
0,94 ms |
0,17 ms |
| Bubblesort |
82,00 ms |
36,38 ms |
8,9 ms |
2,19 ms |
0,38 ms |
| Heapsort |
10,56 ms |
6,61 ms |
3,03 ms |
1,39 ms |
0,51 ms |
Anhand dieser Tabelle wird deutlich, daß die Stärke des recht aufwendigen Heapsorts erst bei einer größeren Anzahl von Elementen liegt. Deshalb findet Quicksort auch häufiger Verwendung in der Praxis. Somit ist festzustellen, daß die Verwendung der Sortieralgorithmen immer in Abhängigkeit der Anzahl der Elemente steht.
3. Literatur
Robert Sedgewick: Algorithmen; unveränderter Nachdruck 1997