Analyse Quicksort
worst case: sowohl Vergleiche wie Bewegungen quadratisch. Schlechtester Fall tritt ein, wenn Array bereits sortiert.
(N + 1) + (N) + ( N - 1) + ... + 3 Vergleiche
best case: Folgen werden in gleichlange Teilfolgen aufgeteilt, Aufrufbaum hat Tiefe log N, auf jeder Ebene maximal N Vergleiche, damit Laufzeit Q(N log N).
Mittlere Laufzeit fast so gut wie beste Laufzeit!!
Annahmen: Schlüssel 1, ..., N, alle Permutationen gleich wahrscheinlich
Average case Komplexität: O(N log N)