Kostenanalyse für Sortieralgorithmen
Vergleiche zählen
Wir betrachten die bereits eingeführten Algorithmen zur Lösung des Sortierproblems. Ziel ist es, die Kosten bei der Ausführung der Algorithmen abzuschätzen.
Als Problemgröße wählen wir die Anzahl n der Datensätze (Listenelemente). Die Kosten T(n) sollen durch die Anzahl der Datensatzvergleiche bei der Ausführung des Algorithmus bei einer Problemgröße n erfasst werden.
Aufgabe 1
(a) Bilanziere die Kosten (Anzahl der Vergleiche) beim folgenden Sortiervorgang durch Auswählen.
| 25 17 32 56 25 19 8 66 29 6 20 29 Vergleiche: 11
^
6 | 17 32 56 25 19 8 66 29 25 20 29
^
6 8 | 32 56 25 19 17 66 29 25 20 29
^
6 8 17 | 56 25 19 32 66 29 25 20 29
^
6 8 17 19 | 25 56 32 66 29 25 20 29
^
6 8 17 19 20 | 56 32 66 29 25 25 29
^
6 8 17 19 20 25 | 32 66 29 56 25 29
^
6 8 17 19 20 25 25 | 66 29 56 32 29
^
6 8 17 19 20 25 25 29 | 66 56 32 29
^
6 8 17 19 20 25 25 29 29 | 56 32 66
^
6 8 17 19 20 25 25 29 29 32 | 56 66
^
6 8 17 19 20 25 25 29 29 32 56 | 66
Ändert sich die Bilanz, wenn andere Zahlen in der Liste stehen?
(b) Bilanziere die Kosten (Anzahl der Vergleiche) ebenso beim folgenden Sortiervorgang durch Einfügen.
25 | 17 32 56 25 19 8 66 29 6 20 29 Vergleiche: 1
17 25 | 32 56 25 19 8 66 29 6 20 29
17 25 32 | 56 25 19 8 66 29 6 20 29
17 25 32 56 | 25 19 8 66 29 6 20 29
17 25 25 32 56 | 19 8 66 29 6 20 29
17 19 25 25 32 56 | 8 66 29 6 20 29
...
Wie wirkt sich hier eine andere Ausgangsliste auf die Kostenbilanz aus?
Fallanalysen
Die Anzahl der Datensatzvergleiche bei der Ausführung eines Sortieralgorithmus hängt manchmal nicht nur von der Problemgröße n (d.h. der Anzahl der Listenelemente) ab, entscheidend ist auch, wie stark die Liste bereits vorsortiert ist.
Bei einer Kostenanalyse unterscheidet man daher oft die folgenden Fälle:
- best case (bester Fall): der Fall, in dem bei der Ausführung des Algorithmus die wenigsten Kosten anfallen
- worst case (schlechtester Fall): der Fall, in dem bei der Ausführung des Algorithmus die meisten Kosten anfallen
- average case (durchschnittlicher Fall): eine Mittelung der Kosten über alle Fälle
Für die Praxis am wichtigsten ist meist der durchschnittliche Fall. Dieser ist aber schwer zu ermitteln. Wir konzentrieren uns hier daher auf den besten und schlechtesten Fall, wobei letzterer meist der relevantere ist.
Beispiel: Sortieren durch Auswahl (Selectionsort)
Hier muss man in jedem Fall im ersten Schritt n-1 Vergleiche durchführen, im zweiten Schritt n-2 Vergleiche usw.. Es gilt also:
Tbest(n) = (n-1) + (n-2) + ... + 1
Tworst(n) = (n-1) + (n-2) + ... + 1
Beispiel: Sortieren durch Einfügen (Insertionsort)
Im ungünstigsten Fall muss beim Einfügen der gesamte bereits vorliegende sortierte Teil durchlaufen werden. Hier gilt dann:
Tworst(n) = 1 + 2 + ... + (n-1)
Im günstigsten Fall kann das nächste Element nach einem Vergleich an der richtigen Position eingefügt werden. Es gilt dann:
Tbest(n) = n-1
Aufgabe 2
Muss man bei der Aufwandsanalyse zum Bubblesort-Algorithmus unterschiedliche Fälle unterscheiden? Führe eine Aufwandsanalyse durch und bestimme eine Formel für T(n).
Aufgabe 3
(a) Erläutere anhand geeigneter Beispiele, dass der Vergleichsaufwand bei der Durchführung des Quicksort-Algorithmus stark von der Ausgangsliste abhängt.
(b) Begründe, dass der Vergleichsaufwand bei der Durchführung des Quicksort-Algorithmus im günstigsten Fall mit der Kostenfunktion Tbest(n) = n*log2(n) und im ungünstigsten Fall mit der Kostenfunktion Tworst(n) = n*(n-1)/2 angenähert beschrieben wird.
Aufgabe 4
Welches Sortierverfahren ist vorzuziehen, wenn eine Liste bereits größtenteils vorsortiert ist, und welches, wenn eine Liste völlig unsortiert ist?
