Nigdy, przenigdy nie wybieraj stałej osi - może to zostać zaatakowane w celu wykorzystania czasu wykonania O (n ^ 2) najgorszego przypadku algorytmu, który po prostu prosi o kłopoty. Najgorszy przypadek środowiska uruchomieniowego Quicksort występuje, gdy partycjonowanie daje jedną tablicę zawierającą 1 element i jedną tablicę zawierającą n-1 elementów. Załóżmy, że wybierasz pierwszy element jako partycję. Jeśli ktoś prześle tablicę do twojego algorytmu, która jest w porządku malejącym, twój pierwszy przestaw będzie największy, więc wszystko inne w tablicy przesunie się na lewo od niej. Następnie, gdy powtórzysz, pierwszy element będzie ponownie największy, więc jeszcze raz umieszczasz wszystko na lewo od niego i tak dalej.
Lepszą techniką jest metoda mediany-3, w której losowo wybierasz trzy elementy i wybierasz środek. Wiesz, że wybrany element nie będzie pierwszym ani ostatnim, ale także, zgodnie z centralnym twierdzeniem granicznym, rozkład środkowego elementu będzie normalny, co oznacza, że będziesz dążyć do środka (a zatem , n lg n czas).
Jeśli absolutnie chcesz zagwarantować czas wykonania algorytmu O (nlgn), metoda kolumna-5 do znajdowania mediany tablicy działa w czasie O (n), co oznacza, że równanie powtarzania dla szybkiego sortowania w najgorszym przypadku będzie be T (n) = O (n) (znajdź medianę) + O (n) (podział) + 2T (n / 2) (powtórz lewy i prawy.) Zgodnie z Twierdzeniem Głównym, to jest O (n lg n) . Jednak stały współczynnik będzie ogromny i jeśli najważniejsza jest wydajność w najgorszym przypadku, zamiast tego użyj sortowania przez scalanie, które jest tylko trochę wolniejsze niż średnio szybkie sortowanie i gwarantuje czas O (nlgn) (i będzie znacznie szybsze niż ta kiepska mediana quicksort).
Wyjaśnienie algorytmu mediany median