In welchem typischen Fall benötigt Quicksort O(n²) Zeit?

Antwort: C. Die Daten sind bereits sortiert, und als Pivotelement wird immer das erste Element verwendet

Quicksort teilt die Elemente in solche, die kleiner, und solche, die größer als das Pivotelement sind, und teilt jeden Teil erneut. Sind die Daten bereits sortiert und ist das erste Element immer das Pivotelement, ist es jedes Mal das Minimum, und jede Teilung ist einseitig, mit null Elementen auf der einen und allen übrigen auf der anderen Seite; so entstehen n(n−1)/2 Vergleiche (4950 bei n = 100). Wählt man das Pivotelement zufällig oder als Median aus drei Werten, wird eine lange Folge einseitiger Teilungen äußerst unwahrscheinlich. Die Zahl der Elemente spielt dabei keine Rolle.