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:

RSCVQD687Q9FS

ilustracja przedstawia złożoność O(n logarytm drugiego stopnia z n). Na schemacie po lewej stronie jest log indeks dolny, dwa, koniec indeksu dolnego, 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²).

R1J84HJ75DVPC

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ść obliczeniowa

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ść obliczeniowa algorytmu szybkiego sortowania wynosi:

$O(n\log n)$

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

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

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

$n+2\mathrm{T}(\frac{n}{2})$