Quicksort

Quicksort ist ein Sortieralgorithmus, der nach dem Prinzip Divide and Conquer arbeitet; und zwar wie folgt:

Gegeben: Liste A der Länge n.

• Falls n < 2: A ist sortiert, brich ab. Ansonsten…
• Wähle ein Element aus der Liste, das so genannte Pivot-Element
• Teile die Liste in zwei Haufen. Auf einen Haufen kommen die Elemente, die kleiner sind als das Pivot-Element, auf den anderen Haufen die Elemente, die größer sind.
• Sortiere beide Haufen mit Quicksort; du erhältst zwei sortierte Listen
• Füge die beiden sortierten Teillisten mit dem Pivot-Element zu einer sortierten Gesamtliste zusammen.

Laufzeit

Um die Liste in zwei Haufen zu unterteilen, muss man alle n Elemente betrachten, ist also in ${\mathcal {O}}(n)$. Das Zusammenfügen am Ende hat eine Laufzeit, die nicht von der Länge der Eingabeliste abhängt, ist also in ${\mathcal {O}}(1)$. Die Frage ist nun, wie oft die Liste unterteilt werden muss.

Worst Case

Im schlechtesten Fall wählt man das Pivot-Element so ungeschickt, dass der gesamte Rest der Liste immer auf einem Haufen landet. Dies ist der Fall, wenn man als Pivot-Element das größte oder das kleinste Element der Liste wählt. In diesem Fall muss die Liste n-1 Mal in Haufen unterteilt werden, es ergibt sich eine Laufzeit in ${\mathcal {O}}(n^{2})$.

Best Case

Im besten Fall wählt man das Pivot-Element so geschickt, dass man die Liste immer in zwei exakt gleich große Haufen teilt. Dann muss die Liste etwa $\log n$ Mal in Haufen unterteilt werden; es ergibt sich eine Laufzeit in ${\mathcal {O}}(n\log n)$.

Weblinks

• Sortieralgorithmen auf VisuAlgo.net 🇬🇧 🇨🇳 🇮🇩

Sortieralgorithmen

Bubblesort | Selectionsort | Insertionsort | Quicksort | Mergesort | Gnomesort