Wie ist die zeitliche Komplexität des Quicksort-Algorithmus im schlimmsten, durchschnittlichen und besten Fall?

Zeitkomplexität des Quicksort-Algorithmus:

• Schlimmster Fall: O(n²) — tritt auf, wenn das Pivotelement ungünstig gewählt wird (z.B. immer das größte oder kleinste Element), und das Array ungleichmäßig aufgeteilt wird.
• Durchschnittlicher Fall: O(n log n) — bei zufälliger Wahl des Pivotelements oder bei guter Aufteilung des Arrays.
• Bester Fall: O(n log n) — wenn das Array bei jedem Schritt in zwei ungefähr gleich große Teile aufgeteilt wird.

Daher arbeitet Quicksort in der Regel sehr effizient, kann im schlimmsten Fall jedoch auf quadratische Komplexität degradieren.