Quicksort ist ein Divide-and-Conquer-Sortieralgorithmus, der ein Pivot auswählt, Elemente in solche kleiner und größer als dieses unterteilt und dann jede Seite rekursiv sortiert. Durchschnitt O(n log n), schlimmster Fall O(n²).
Die Idee
Die Partitionierung platziert das Pivot an seiner endgültigen sortierten Position; alles links ist kleiner, alles rechts ist größer. Rekursiv auf beide Seiten anwenden.
