Quicksort Idee

Quicksort wählt ein Pivot, partitioniert in kleiner/grösser und sortiert die Seiten rekursiv. Erwartete Zeit $O(n \log n)$, Worst Case $O(n^{2})$ bei schlechten Pivots.

Randomisiertes Pivot oder Medians-of-three mindern den Worst Case.

Partition ohne vollstaendig zu sortieren: Kth Largest Element in an Array [1].

Wo gebraucht

In-Place-Durchschnitt $O(n \log n)$, Dual-Pivot in der JDK für primitive Arrays. Pivotstrategie entscheidet über Worst Cases und über Robustheit gegen adversarial Input.

Vertiefung

Quicksort wählt ein Pivotelement und ordnet die übrigen Werte in Bereiche relativ zum Pivot ein. Danach werden die Bereiche rekursiv sortiert. Anders als Merge Sort investiert es die lineare Arbeit vor den rekursiven Aufrufen in eine Partitionierung.

Ausgewogene Teilbereiche ergeben eine geringe Rekursionstiefe und eine sehr gute durchschnittliche Laufzeit. Wiederholt extrem ungleiche Teilungen erzeugen dagegen eine nahezu lineare Tiefe und quadratisch wachsende Gesamtarbeit. Zufällige oder robust gewählte Pivots verringern dieses Risiko.

Schwierigkeitsstufen

1. Pivotwahl, Partition und Rekursion als Phasen unterscheiden.
2. Rekursionsbäume für ausgewogene und schiefe Teilungen vergleichen.
3. Pivotstrategien bei vorsortierten und duplikatreichen Daten beurteilen.

Fallstricke

Das Pivot ist ein Wertkonzept, seine Position kann während der Partition wechseln. Rekursive Grenzen müssen die bereits abgeschlossenen Bereiche ausschliessen, sonst drohen Endlosschleifen.