Aufwandsanalyse
Vergleiche zählen
Wir betrachten die bereits eingeführten Algorithmen zur Lösung des Sortierproblems. Ziel ist es, den Aufwand bei der Ausführung der Algorithmen abzuschätzen.
Hierzu zählen wir die Anzahl T(n) der Vergleiche in Abhängigkeit von der Anzahl n der zu sortierenden Datenobjekte.
Aufgabe 1
(a) Bilanziere die 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 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 Vergleiche 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 der geringste Aufwand erforderlich ist
- worst case (schlechtester Fall): der Fall, in dem bei der Ausführung des Algorithmus der meiste Aufwand erforderlich is
- average case (durchschnittlicher Fall): eine Mittelung ü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?
