Může se stát, že program bude na většině dat fungovat celkem rychle, akorát na pár “blbých” výjimkách poběží hrozně dlouho. Abychom lépe popsali časovou složitost takového algoritmu, tak kromě časové složitosti v nejhorším případě uvedeme i průměrnou časovou složitost. Tu spočítáme jako průměr časových složitostí přes všechny možné vstupy.

Často není rychlost odpovědi otázkou života a smrti a proto nám nebude vadit, když si ve výjimečných případech počkáme déle. Důležité je, že v průměru budeme dostávat odpovědi relativně rychle.

Příkladem programu, který má průměrnou časovou složitost lepší než časovou složitost v nejhorším případě, je quicksort. Při nevhodné volbě pivota může mít až kvadratickou časovou složitost, ale v průměrném případě je jeho složitost $\OO(n\log n)$. Přesným výpočtem se dá ukázat, že konstanta před $n\log n$ je o proti jiným třídícím algoritmům malá. To je důvod, proč se v praxi quicksort tolik používá.

QuickSort

Quicksort využívá techniku Rozděl a Panuj (Divide et Empera) o které si povíme později v sekci [ref]section-rozdel-a-panuj[/ref].

Algoritmus dostane $n$ čísel v poli $\ARRAY{A}{\cdot}$ a má je setřídit od nejmenšího po největší.

Quicksort funguje rekurzivně. Dostene úsek pole $\ARRAY{A}{l..p}$, který nejprve rozdělí na dva podúseky $\ARRAY{A}{l..q}$ a $\ARRAY{A}{q+1..p}$ podle hodnoty, které se říká pivot. První podúsek obsahuje všechny prvky menší nebo rovné pivotu a druhý podúsek všechny prvky větší než pivot. Nakonec quicksort nechá oba podúseky setřídit rekurzivně.

Quicksort($l$, $p$)
	if $l<p$  then
		 $pivot := \ARRAY{A}{\lfloor (l+p)/2 \rfloor}$ 
		 $q := $   Partition($l$, $r$, $pivot$ )
		 Quicksort($l$, $q$ )
		 Quicksort($q+1$, $p$ )

Funkce $q:=$Partition($l$, $p$, $pivot$) rozdělí úsek pole $\ARRAY{A}{l..p}$ na dva úseky $\ARRAY{A}{l..q}$ a $\ARRAY{A}{q+1..p}$, kde první úsek obsahuje pouze prvky menší nebo rovny pivotu a druhý úsek pouze prvky větší než pivot. Funkce vrátí index $q$, který odpovídá hranici mezi podúseky.

Partition($l$, $p$, $pivot$ )
	while $l<p$ do while $\ARRAY{A}{l} \le pivot$ do $l:=l+1$ while $\ARRAY{A}{p} > pivot$  do $p:=p-1$ 
		 Prohoď($l$, $p$ )
	return $p$ 

V ideálním případě, kdy se nám podaří vybrat všechny pivoty tak, aby se každý úsek pole rozdělil přesně napůl, dosteneme v nulté hladině rekurze 1 úsek o $n$ prvcích, v první hladině rekurze 2 úseky o $n/2$ prvcích, ve druhé hladině rekurze 4 úseky o $n/4$ prvcích,… Časová složitost quicksortu při tomto dělení úseků je $\OO( n+2(n/2)+4(n/4)+\dots+2^{\lceil\log n\rceil} \cdot 1 )= \OO( \lceil\log n\rceil \cdot n )=\OO(n\log n)$.

Ovšem pokud budeme mít smůlu a pivot bude vždy nejmenším nebo největším prvkem z aktuálního úseku, tak bude bude časová složitost quicksortu $\OO( n + (n-1) + (n-2) +\dots = \OO(n^2)$.

Quicksort má v nejhorším případě kvadratickou časovou složitost, ale dá se o něm ukázat, že časová složitost v průměrném případě je pouze $\OO(n \log n)$. Upočítání vyžaduje dobrou znalost teorie pravděpodobnosti a proto ho přenecháme jiným knížkám (ale jinak je to jednoduché).

Poznámky k implementaci: Při implementaci quicksortu můžeme místo rekurze využít zásobníku, na který si budeme ukládat úseky pole, které je potřeba setřídit pomocí quicksortu. Při zpracování úseku uloženého na vrcholu zásobníku vyrobíme 2 nové podúseky. Myslíte, že záleží na pořadí, v jakém nové podúseky uložíme na zásobník? Samozřejmě, že ano. Vždy uložíme větší úsek pole dospod. Rozmyslete si, jak to ovlivní velikost paměti potřebné pro zásobník.

Druhým trikem při implementaci je pozorování, že pro malé vstupy je Insersort rychlejší než Quicksort. Proto od určité velikosti podúseků skončíme s rekurzivním voláním Quicksortu a podúsek dotřídíme Insertsortem.