Quicksort ist das am häufigsten verwendete Verfahren. Es handelt sich dabei um einen instabilen, in-place Algorithmus. Grundlegend lässt sich sagen, dass man immer ein Element aus der Liste bestimmt, das sogenannte Pivotelement und dieses Element bildet dann den Maßstab für Vergleiche. Im Anschluss setzen wir alle anderen Elemente an ihre richtige Position. Die neuen Positionen bestimmt man immer auf Basis des Pivotelements. Wenn keine weiteren Elemente mehr zu sortieren sind, endet der Algorithmus.
Quicksort funktioniert nach dem "Teile-und-herrsche"-Prinzip ("divide and conquer"): Als erstes teilen wir die zu sortierenden Elemente auf zwei Bereiche auf – einen mit kleinen Elementen und einen mit großen Elementen. Welche Elemente klein sind und welche groß, entscheidet dabei das sogenannte Pivot-Element. Das Pivot-Element kann ein beliebiges Element aus dem Eingabe-Array sein.
Version 1 Lernvideo zum Quicksort Lernvideo Version 2 Lernvideo zum Quicksort Lernvideo
Die Laufzeitkomplexität beim Quicksort ist im: Best-Case: O(n log n) Average-Case: O(n log n) Worst-Case: O(n2), wobei n die Anzahl der zu sortierenden Elemente angibt.
Hinweis: Alle Ergebnisse und Zwischenergebnisse müssen in Moodle abgegeben werden.