TIN066 Vyhledávání k-tého nejmenšího prvku
V nesetříděném poli S mám najít k-tý nejmenší prvek (pokud $ k = \frac{|S|}{2} $, říkáme mu medián).
Quickselect
Quickselect (FIND) funguje na principu QuickSortu. Zvolíme pivot $ a \in S $, prvky rozdělíme na S1 (menší než a) a S2 (větší než a). Pokud $ |S1| = k $, hledaným prvkem je náš pivot a. Pokud $ |S1| > k $, hledáme k-tý nejmenší v S1, jinak hledáme (k-|S1|-1)-tý nejmenší v S2.
Složitost záleží na volbě pivota. V nejhorším případě $ O(n^2) $, zato v průměrném případě můžeme očekávat $ O(n) $.
Median-of-Medians (Blum, BFPRT)
Chtěli bychom zajistit lineární složitost, nezávisející na náhodě. Nepříliš složitá modifikace Quickselectu, jen budeme volit pivota chytřeji (chtěli bychom jako pivota zvolit aspoň přibližný medián).
Uvažujme funkci select(M, k), která najde k-tý nejmenší prvek v M. Medián lze najít zavoláním select(M, ceil(|S|/2)) - hledání mediánu je tedy jen spec. případem hledání k-tého nejmenšího prvku, řešíme tedy obecnější problém.
Idea je simulovat Quickselect, ale vybrat pivota chytřeji, cca medián. Jak na to? Nejdříve si M rozdělíme na pětice a vyrobíme N - pole mediánů pro každou pětici (tedy $ |N| = \lceil |M|/5 \rceil $). Z pole N vybereme medián (který nemusí být mediánem M) rekurzivním zavolámím select(N,ceil(|N|/2)). To, co se nám vrátí (median-of-medians), použijeme jako pivota, a dál pokračujeme v klasickém běhu Quickselectu.
Algoritmus zjevně funguje, protože Quickselect funguje pro jakýkoliv výběr pivota. Jelikož námi zvolený pivot je cca medián, quickselectová část běží v $ O(n) $. Jak složitý je ale výběr "deluxe" pivota? Důkaz spočívá v masivní zlomkové ekvilibristice, až z toho oči slzí. Po chvilce úvah však lze uvěřit, že deluxe pivota najdeme v lineárním čase (pivoty pětic v O(c*n), jejich medián v O(n/5), rozdělení na 2 půlky dle pivota v O(n)).
Quickselect se používá častěji než Median-of-Medians, i když má horší složitost v nejhorším případě (paralela: Quicksort se používá častěji, než Heapsort, i když má horší složitost v nejhorším případě).
