Czas działania algorytmu

Złożoność obliczeniowa algorytmu sortowania szybkiego jest zależna od rozmiarów części, na jakie jest dzielona tablica. Jeżeli za każdym razem będzie wybierany pivot o wartości najmniejszej lub największej w tablicy, podział tablicy będzie nierównomierny. Tym samym poważnie wzrośnie czas działania algorytmu. W takim ujęciu przypadek optymistyczny i pesymistyczny nie są związane ze sposobem uporządkowania elementów w tablicy, ale z wyborem elementu osiowego, czyli ze sposobem dzielenia tablicy.

Rozważmy najpierw przypadek optymistyczny, którego złożoność obliczeniowa algorytmu wynosi O(n log n). Jeżeli tablica za każdym razem jest dzielona na dwie równe części, otrzymamy właśnie taki czas działania. Przedstawia to poniższy schemat:

RwGFU1wdspLEn

ilustracja przedstawia złożoność O(n logarytm drugiego stopnia z n). Na schemacie po lewej stronie jest ${\text{log}}_{2 }\mathrm{n}$. Następnie jest duża, pionowa klamra. Po prawej stronie klamry jest schemat. Na górze schematu litera n. Od litery n kreski w dół na lewo i prawo. Tam zapis n/2. Od każdego n/2 kreski do n/4 - dwa razy do każdego n/2. Od każdego n/2 po dwie kreski w dół do zapisu n/8. Na samym dole schematu czterokrotnie są trzy czerwone kropki. Po prawej stronie od n, n/2, n/4 oraz n/8 jest pozioma strzałka skierowana w stronę zapisu. Na początku każdej strzałki jest litera n.

W przypadku pesymistycznym tablica jest dzielona na dwie części, z których jedna zawiera jeden element, a druga resztę elementów. Złożoność obliczeniowa wynosi wtedy O(nIndeks górny 2²).

R13CeGVW0C5qo

Ilustracja przedstawia złożoność O(n kwadrat). Po lewej stronie ilustracji jest litera n, a obok niej pionowa otwarta klamra. Po prawej stronie klamry jest następujący schemat: z litery n wychodzą dwie linie - do 1 oraz n‑1, z n‑1 linia do 1 oraz n‑2, z n‑2 do 1 i n‑3. Z n‑3 trzy czerwone kropki biegną do cyfry 2. Od cyfry 2 linie do 1 oraz 1. Następnie do liczby dwa, z których linie idą do 1 i 1. Od góry schematu po prawej stronie od n jest pozioma strzałka w jego kierunku na początku strzałki jest litera n. Przy n‑1 po prawej stronie jest pozioma strzałka w kierunku zapisu, na początku strzałki jest litera n. Po prawej stronie od n‑2 jest pozioma strzałka w kierunku zapisu, na początku strzałki jest zapis n‑1. Po prawej stronie n‑3 jest pozioma strzałka w kierunku zapisu, na początku strzałki jest zapis n‑2. Od n‑2 trzy czerwone kropki w dół do liczby 2. Od liczby 2 strzałka w kierunku 1, które jest na samym dole po prawej stronie schematu.

Algorytm sortowania szybkiego – złożoność czasowa

Założeniem algorytmu sortowania szybkiego jest – jak sama nazwa wskazuje – możliwie najkrótszy czas sortowania kosztem większego wykorzystania pamięci (wywołania rekurencyjne).

Średnia złożoność czasowa algorytmu szybkiego sortowania wynosi:

$O(n\log n)$

Złożoność czasowa takiego algorytmu w przypadku pesymistycznym to:

$\frac{n^2}{2}$

Natomiast jego złożoność czasowa w przypadku optymistycznym to:

$n+2\mathrm{T}(\frac{n}{2})$,  gdzie T() oznacza liczbę porównań.