TIN066 Přihrádkové třídění
Bucket sort
Mějme n prvků v rozsahu 0..m; připravíme si m+1 množin a do každé rozházíme prvky se stejným číslem, množiny pak spojíme za sebe a máme výsledek. Třídění zachovává pořadí.
Pro inicializiaci potřebujeme O(m), pro rozházení O(n), pro konkatenaci ideálně zase O(m), takže celkem třídění zabere O(m+n) času.
Hybrid sort
Bucketsort umí jen přirozená čísla a potřebuje hodně přihrádek; zkusme zmenšit počet přihrádek, klidně mít více prvků v jedné, ale zachovat očekávanou lineární složitost.
Mějme zase n prvků, tentokrát z $ [0,1] $, a dané $ \alpha $ jako "hustota přihrádek"; počet přihrádek bude $ k=\alpha n $; uvnitř přihrádky budeme třídit prvky třeba heapsortem. Jak vidno, v nejhorším případě spadnou všechny prvky do jedné přihrádky a skončím na O(nlogn). (Inicializace struktury trvá O(n).)
Ale co v průměru (pro rovnoměrně rozdělený vstup)? Velikosti přihrádek se řídí binomickým pravděpodobnostním rozdělením s parametrem p=1/k. (Binomické rozdělení popisuje pravděpodobnost, že při a hodech mincí (jeden hod má pravděpodobnost právě parametr p) se jich b povede. Pravděpodobnost, že mince spadne do naší přihrádky, je 1/k.) Jedno přidání do přihrádky velikosti $ X_i $ je $ O(1+X_i\log X_i) $, průměrný čas třídění pak zapíšeme takto:
$ \mathbb{E}\left(\sum_{i=0}^{k} (1 + X_i \log X_i) \right) = k + k \mathbb{E}(X_i) \mathbb{E}(\log X_i) \le k + k \mathbb{E}(X_i) \mathbb{E}(X_i) $
Střední hodnota velikosti přihrádky i je v binomickém rozdělení $ \mathbb{E}X_i = n/k $. To lze nahlédnout intuitivně, provést "důkaz Wikipedií", nebo odvodit algebraicky (jako Koubek ve skriptech). Každopádně pak už si jen stačí ještě vzpomenout, jak jsme definovali k, a dostaneme:
$ \ = k + k (n/k) (n/k) = k + n^2/k = \alpha n + n/\alpha = O(n) $
Word sort
Chceme třídit větší objekty než jen přihrádkovatelná čísla - slova (často se teprve tomuto algoritmu říká bucketsort nebo radixsort). Mějme úplně uspořádanou abecedu, chceme lexikograficky setřídit různě dlouhá slova $ a_1, \ldots, a_n $.
Jaká je idea? (Chvíle googlení. Chvíle čtení fór. Chvíle zoufalství. Přišla chvíle zalistovat ve Knuthov!) Představme si balíček karet, který chceme setřídit (primárně dle barvy, sekundárně dle hodnoty). Můžeme na to jít mnoha způsoby, ale šikovné je si nejdříve udělat hromádku pro každou hodnotu, rozházet karty a položit hromádky na sebe ve správném pořadí. V druhém průchodu si zase uděláme hromádku pro každou barvu, znovu rozházíme karty a hromádky zpátky položíme na sebe. A... a je to! Díky tomu, že bucketsort je stabilní, máme balíček správně setříděný. Pro slova delší než 2 iterujeme vícekrát.
To je fajn, ale máme problém, slova totiž mohou být různě dlouhá. Díky tomu se nám algoritmus zkomplikuje, když se ale rozumně vyloží ve správném pořadí (což se zatím kdovíproč dařilo málokomu), je z něj ta idea stále vidět.
Mějme množinu slov, nejdříve si ji rozdělme bucketsortem do přihrádek dle délky. Výstupní množina T bude na začátku prázdná. Postupně budujme množinu slov T od nejdelších k nejkratším; v každé iteraci snížíme limit i na délku slova, na začátek množiny T přidáme nově povolená slova, a bucketsortem setřídíme T podle i-tého písmenka (díky jeho stabilitě jsme tím nerozbili setřídění z předchozích iterací). V poslední iteraci skončíme s T obsahující setříděná všechna slova. Lze snadno nahlédnout, že kdyby měla všechna slova stejnou délku, bude to přesně náš karetní algoritmus.
No jo, ale tohle nebude moc efektivní - řekli jsme, že bucketsortem setřídíme T, ale to znamená vždy při výstavbě nové verze T projít n přihrádek pro celou abecedu, takže složitost hlavního cyklu bude nějaká ošklivá - možná třeba (bez záruky) O(l*(m + n)) (kde n je velikost abecedy, m je počet slov a l je délka nejdelšího - l-krát otočím hlavní cyklus, zpracuju až m slov, a zkonkatenuju obsah n přihrádek); respektive přesněji O(L + l*n) (L je součet délek všech slov). Bylo by hezké, abychom vždy procházeli jen přihrádky, ve kterých něco je.
Tak uděláme další preprocessing! Rozdrobíme slova na "písmenka se souřadnicemi" $ P=\{(j,a_i^j)\} $ (buď $ a_i^j $ j-tý znak i-tého slova). P setřídíme bucketsortem nejdříve podle druhé složky, zapojíme přihrádky zpátky do posloupnosti a pak znovu zbucketsortíme podle první složky, získáme tak přihrádky $ S_x $: $ S_1 $ jsou všechna první písmenka, $ S_2 $ všechna druhá, atd. - uvnitř každé přihrádky máme písmenka lexikograficky setříděná. Tím jsme si vlastně vyrobili lookup table, ze které snadno zjistíme, v které hloubce máme která písmena, dokonce postupné procházení seznamu v přihrádce vyrábí přirozenou operaci NEXT. To, že v nich je typicky mnoho duplicit nevadí, každé písmenko v této pomocné struktuře projdu za celý běh algoritmu jen jednou (celkem $ O(L) $). Podle této pomocné tabulky pak budu při vytváření množiny T procházet jen neprázdné kyblíky.
Složitost
V následujícím značíme $ L $ součet délek slov, $ n $ velikost abecedy, $ l $ délku nejdelšího slova a $ m $ počet slov.
Preprocessing - vytvoření dvojic $ (j,a_i^j) $ trvá $ O(L) $, sort podle $ a_i^j $ trvá $ O(L + n) $ a podle $ j $ zabere $ O(L + l)=O(L) $, dohromady $ O(L + n) $.
Vlastní algoritmus - rozhození podle délek slov trvá $ O(L + l)=O(L) $, iterací třídění je sice l, ale protože máme pomocnou strukturu tak to zvládneme za celkem $ O(L) $.
Složitost celého algoritmu pak bude Složitost preprocessingu + Složitost samotného třídění $ = O(n+L) + O(L) = O(n + L) $.
(IMHO je v běžném případě ten preprocessing málo muziky za hodně peněz, ale máme-li velikou abecedu nebo dlouhatánská slova...)
