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:Aist 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.
Eine große Herausforderung ist es, das Pivot-Element geschickt zu wählen. Am einfachsten ist es, als Pivot-Element das erste Element der Liste zu wählen. Für die Laufzeit ist es optimal, ein Element aus der Mitte der Liste zu wählen. Wenn man darauf zu viel Zeit verwendet, ist der Laufzeitvorteil aber auch wieder dahin.
Laufzeit
Um die Liste in zwei Haufen zu unterteilen, muss man alle Elemente betrachten, ist also in . Das Zusammenfügen am Ende hat eine Laufzeit, die nicht von der Länge der Eingabeliste abhängt, ist also in . 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 Mal in Haufen unterteilt werden, es ergibt sich eine Laufzeit in .
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 Mal in Haufen unterteilt werden; es ergibt sich eine Laufzeit in .
