Time and Space Complexity

Zeitkomplexität:

• Durchschnittsfall (Average Case): O(n log n)
  • Ein ausgewogener Pivot teilt das Array jedes Mal grob in zwei Hälften, was etwa log n Ebenen mit O(n) Partitionierungsaufwand ergibt.
• Schlechtester Fall (Worst Case): O(n²)
  • Wenn der Pivot immer das kleinste oder größte Element ist (zum Beispiel bei einem bereits sortierten Array mit dem letzten Element als Pivot), ist eine Seite jedes Mal leer und die Rekursion wird n Ebenen tief.

Platzkomplexität:

• O(n) für die Version, die wir hier bauen, da wir bei jedem Schritt neue kleinere und größere Listen erstellen. Der klassische In-Place Quick Sort verbessert dies auf O(log n) zusätzlichen Speicherplatz.

Zusammenfassung:

• Quick Sort ist im Durchschnitt sehr schnell und ist in der Praxis ein Standard-Sortieralgorithmus.
• Eine schlechte Pivot-Wahl kann ihn auf O(n²) degradieren; gute Pivot-Strategien (wie die Wahl eines zufälligen oder des Median-Elements) vermeiden dies.