Máme posloupnost $n$ prvků, například čísel. Medián je takové číslo z posloupnosti čísel, že 50% čísel je větších nebo rovno mediánu, ale také 50% čísel je menších nebo rovno mediánu. Jinými slovy, když si posloupnost setřídíme, tak nazveme prvek, který leží uprostřed, mediánem. Pokud je prvků lichý počet, tak je medián ten prostřední prvek. Pokud je počet prvků sudý, tak máme mediány dva — spodní a horní medián. Abychom si zjednodušili výklad, budeme za medián považovat spodní medián.1

Medián se používá ve statistice, protože to je jedno číslo, které vypovídá něco typického o množině čísel. Podobným číslem je průměr.2

Poznámka: Kolik informace nám přinese údaj o průměrné mzdě v Heské republice? Pro běžné lidi je to jen číslo, kvůli kterému jsou nespokojeni, že nevydělávají dost. Pokud bude 10% obyvatel vydělávat 110tis. Kč/měsíc a zbylých 90% obyvatel jen 10tis. Kč/měsíc, tak je průměrná mzda v Heské republice 20tis. Kč. Ovšem kdo ji má? Naproti tomu medián platů v Heské republice je 10tis. Kč/měsíc. To je číslo, které mnohem lépe popisuje celou situaci.

Úkol: Dosteneme pole obsahující $n$ různých čísel.3 Jak co nejrychleji najít medián? Nebo když tento problém zobecníme, jak co nejrychleji najít $k$-tý nejmenší prvek?4

Řešení 1: Nejjednoduším řešením je, že si pole setřídíme a potom vypíšeme $k$-tý prvek. Třídění nám zabere čas $\OO(n\log n)$.

Řešení 2: Můžeme upravit Quicksort tak, aby po rozdělení úseku pole $\ARRAY{A}{l..p}$ pivotem nezpracovával levý i pravý úsek pole, ale aby už pracoval jen s úsekem, ve kterém leží $k$-tý nejmenší prvek.

QuickSelect($l$, $p$, $k$)
	if $l < p$ then 
		$pivot := \ARRAY{A}{\lfloor(l+p) / 2 \rfloor}$
		$q= partition(l,p,pivot)$
		if $pivot \le k$ then 
			quickselect($l$, $q$, $k$) 
		else
			quickselect($q+1$ ,$p$, $k$)
	Output( $\ARRAY{a}{l}$ )

Připomeňme, že 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. Implementace funkce je popsána u quicksortu na straně \pageref{quicksort}.

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, bude časová složitost tohoto řešení $\OO(n+ n/2 + n/4 + \dots) = \OO(2n)=\OO(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 časová složitost tohoto řešení $\OO(n+(n-1)+(n-2)+\dots+1) = \OO(n^2)$. Naštěstí, stejně jako u quicksortu, v průměrném případě nastane první varianta a časová složitost bude lineární.

Řešení 3: Předchozí řešení vylepšíme tak, že si v každé iteraci vybereme dobrého pivota, který leží dostatečně daleko od okrajů aktuálního úseku. Chceme, aby v úseku pole $\ARRAY{A}{l..p}$ délky $n$ vždy existovalo aspoň $3n/10$ prvků menších než pivot a $3n/10$ prvků věších než pivot. Pivota vybereme následovně:

  1. Prvky pole rozdělíme do pětic a v každé pětici nalezneme medián.
  2. Vezmeme pouze mediány ze všech pětic a rekurzivně pomocí QuickSelect() na nich najdeme medián.

Podívejme se na následující obrázek. V každé pětici jsou hodnoty setříděné podle velikosti a sloupce s pěticemi jsou seřazeny podle hodnot jejich mediánů. Algoritmus nepotřebuje nic třídit, pouze nalezne v každé pětici medián (znázorněn modře) a potom nalezne medián mediánů (na tomto obrázku má hodnotu $41$).

Všechny prvky, které leží v první šedé oblasti jsou menší než medián mediánů a všechny prvky ve druhé šedé oblasti jsou větší než medián mediánů. Prvků větších než medián mediánů je aspoň $3\cdot n/10 - 1\ge 3n/10-1$. Podobně prvků menších než medián mediánů je aspoň $3n/10-1$. (Protože $n$ nemusí být dělitelné $5$, může být v poslední pětici jen $1$ prvek. Proto musíme počítat pečlivěji než podle obrázku).

Analýza časové složitosti: Nechť $T(n)$ označuje časovou složitost algoritmu QuickSelect. Nalezení mediána mediánů bude trvat $\OO(n)+T(\lceil n/5 \rceil)$. Rekurzivní volání QuickSelect() na podúseku pole proběhne v čase $\OO(n)+T(7n/10 + 1)$. Celkem dostáváme $T(n)=T(7n/10 + 1)+T(\lceil n/5 \rceil)+\OO(n)$. Teď už stačí jen vyřešit tuto rekurenci.

Zkusíme hledat řešení rekurence ve tvaru $T(n)=cn$, pro nějakou zatím neznámou konstantu $c$. Dosazením do rekurence dostaneme $T(n) \le c(7n/10 + 1)+c(\lceil n/5 \rceil)+an \le c(9n/10+2) + an = cn - (cn/10-2c-an)$. Pokud bude $(cn/10-2c-an)\le 0$, tak máme vyhráno. Tato podmínka je ekvivalentní s $c\le 10a (n/(n-20))$. Stačí zvolit $c=10a$ a pro $n>20$ bude řešení $T(n)=cn$ platit. Pro $n\le 20$ je $T(n)=\OO(1)$.