Lern Fabrik Lern-Fabrik Lern-Fabrik
Lern fabrik

Einführung in den Quick-Sort Algorithmus

Quick-Sort-Algorithmus

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.


Übungsaufgaben zum Quick-Sort

Hinweis: Alle Ergebnisse und Zwischenergebnisse müssen in Moodle abgegeben werden.

Übungen

Aufgabe

    Gegeben seien folgende Zahlen: 7,6,1,3,9,2,4,8,5

    (a) Sortiere die Zahlenreihe nach dem Quick-Sort-Algorithmus!
    (b) Gib die Anzahl der Vergleiche/Tausche an.
    (c) Gib die Zeitkomplexität im Best-Case, Worst-Case und im Average an.