TU Wien:Algorithmen und Datenstrukturen 1 VU (Raidl)/Übungen SS09/Beispiel 8
Sortieren Sie mit Hilfe von Quicksort die Zahlenfolge <6,0,5,4,1,10,13,14> Schreiben Sie dabei nach jedem Schritt des Algorithmus die entstandene Zahlenfolge auf und markieren Sie jeweils das aktuelle Pivotelement, alle bereits sortierten Elemente und die im jeweiligen Schritt vertauschten Elemente.
Geben Sie weiters ein Beispiel für eine Zahlenfolge der Länge 7 an, die einen Worst-Case für Quicksort (Implementierung laut Skriptum) darstellt. Wie groß ist der Aufwand in -Notation für diese von Ihnen gewählte Zahlenfolge?
Beispielfolge[Bearbeiten | Quelltext bearbeiten]
Pivotelement wird FETT markiert, schon sortierte Teile werden kursiv markiert
6,0,5,4,1,10,13,14
6,0,5,4,1,10,13,14
6,0,5,4,1,10,13,14
6,0,5,4,1,10,13,14
0,6,5,4,1,10,13,14
0,1,5,4,6,10,13,14
0,1,5,4,6,10,13,14
0,1,5,4,6,10,13,14
0,1,4,5,6,10,13,14
0,1,4,5,6,10,13,14
0,1,4,5,6,10,13,14
Worst-Case-Folge[Bearbeiten | Quelltext bearbeiten]
Eine Worst-Case-Folge für Quicksort wäre zu Beispiel die Zahlenfolge: <1,2,3,4,5,6,7>. Es würde auch <3,14,35,36,42,59,17835> gehen. Um es allgemein zu sagen, jede Folge die schon aufsteigend sortiert ist, ist ein Worst-Case-Fall. Aus dem einfachen Grund das immer nur ein Teil von der Folge wegfällt und man öfter die restliche Teilfolge durchgehen muss. Demnach ist die Laufzeit in einem Worst-Case (n²)