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:

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.

X

Fehler melden

X

Suche