zdj
6 (5)

Czas działania Ouicksort

Najgorszy przypadek podziałów:

Zachodzi wtedy, gdy funkcja Partition zwraca taki indeks podziału, że jeden z obszarów ma n-1 elementów, a drugi zawiera tylko 1 element. Jeżeli taka sytuacja zachodzi w każdym kroku algorytmu, to liczba wykonywanych porównań jest największa. Np. dla

Ciąg: 1,2, 3, 4, 5.6.7, 8, 9. 10

W vklad 11

/7 + 1    1    ->    1

n + n-1 + // —2+... + 1 =--n - — n~ +—

14

Pr o £r amow;*ii e komputerów f

£ J