TIN066 Základní metody třídění
Heapsort
Nasypeme do haldy (třeba d-regulární) a pak postupně vytahujeme kořeny a stavíme z nich výstup. Jestli chceme dělat heapsort in-place, hodí se mít haldu duální (maximum v kořeni) a maxima přidávat na konec pole haldy, kde se nám uvolňuje odebíráním místo.
Mergesort
Iterovaně slévá podúseky. Je stabilní, ke cachím přátelský, adaptivní na předtříděné posloupnosti, O(N log N). Algoritmus ve skriptech startuje tak, že vstupní posloupnost rozseká na rostoucí úseky, a ty pak slévá - vede k tomu, že při omezeném počtu rostoucích úseků má lineární složitost.
Nechovám se optimálně, když neslévám posloupnosti stejných délek. Proto si na začátku vytvořím seznam posloupností A setříděný podle jejich délek a vždycky merguju dvě nejkratší posloupnosti. (Nadále jsou posloupnosti reprezentovány svými délkami.) Nově vzniklé posloupnosti sypu do seznamu B (přicházejí mi v rostoucím pořadí (podle délek), takže to nemusím nijak třídit). Dvojici posloupností, které mám mergovat, pak získám takhle (ála mergesort): kouknu co mám na první pozici v A a v B, vezmu to menší (tj. kratší posloupnost), znova kouknu na začátek A a B, opět vezmu to menší, to zmerguju, to co mi vznikne hodím na konec B, a takhle iteruju, dokud neskončím s jednou výslednou posloupností. Ve skriptech je to metoda Optim.
Příklad:
vstupní posloupnost: 1 13 4 5 12 6 17 3 11 18 19 22 26 29 rozdělím na úseky: 1 13, 4 5 12, 6 17, 3 11 18 19 22 26 29 očísluju si tyhle posloupnosti: p1, p2, p3, p4 setřídím podle délek A = 2 (p1), 2 (p3), 3 (p2), 7 (p4) B = ∅ nyní se točím v cyklu s touto podmínkou while(|A| + |B| > 1) pro merge vybírám: a1 = min (A[0], B[0]) = p1 nyní A = 2 (p3), 3 (p2), 7 (p4) a2 = min (A[0], B[0]) = p3 nyní A = 3 (p2), 7 (p4) m1 = merge (a1, a2) (jak dělám mergesort je snad jasné - vždycky jdu v obou posloupnostech ukazatelema zleva a beru minimum, zde tedy 1, 6, 13, 17) m1 dám do B nyní B = 4 (m1) (protože m1 má délku 4)
pro připomenutí: A = 3 (p2), 7 (p4) B = 4 (m1)
pro merge vybírám: a1 = min (A[0], B[0]) = p2 nyní A = 7 (p4) a2 = min (A[0], B[0]) = m1 nyní B = ∅ m2 = merge (a1, a2) = 1 4 5 6 12 13 17 m2 dám do B nyní B = 7 (m2) (protože m2 má délku 7)
pro připomenutí: A = 7 (p4) B = 7 (m2)
pro merge vybírám: a1 = min (A[0], B[0]) = p4 nyní A = ∅ a2 = min (A[0], B[0]) = m2 nyní B = ∅ m3 = merge (a1, a2) = 1 3 4 5 6 11 12 13 17 18 19 22 26 29 m3 dám do B nyní B = 14 (m3)
pro připomenutí: A = ∅ B = 14 (m3)
nyní zasáhne podmínka while-cyklu (while(|A| + |B| > 1)), tj. stop, result = m3
Quicksort
Populární, při rovnoměrném rozložení má nejnižší očekávaný čas, ale až kvadratický nejhorší. Zvolíme pivot a, ten nám vstup rozdělí na část menší než a, část větší než a; výsledné pole bude (qsort(mensi), a, qsort(vetsi)). Pro maličké pole můžeme roztřídit "ručně". Ideální pivot by byl medián, ale ten trvá najít lineární čas; tak bereme třeba vždy první prvek, ale to je nevyzpytatelné - nejpopulárnější je dnes vzít medián 3 až 5 náhodných prvků.
Očekávaný čas = počet porovnání dvou prvků v průměrném případě. Velmi hrubá idea: V každé iteraci projdeme N prvků, ale nejpravděpodobnější je, že interval rozdělíme "zhruba v půlce", takže iterací bude logN. Formálně:
- Máme matici X rozměrů $ n \times n $. X(i,j) = 1, právě když algoritmus při svém běhu porovnal prvky i, j (i-tý a j-tý). Algoritmy porovnávají dva prvky nejvýše jednou, proto BÚNO nechť jsou pod diagonálou nuly.
- Nechť $ p_{i,j} $ je pravděpodobnost porovnání prvků i, j. Očekávaný čas je pak součet $ p_{i,j} $ přes horní trojúhelník X. Formálně $ \sum_{i=1}^n\sum_{j=i+1}^n p_{i,j} $.
- Malá vsuvka: Select sort (n-krát vyberu minimum) porovná vždy každý s každým, $ p_{i,j} = 1 $, jedničky nad diagonálou, tedy očekávaný čas $ \frac{n^2 - n}{2} $ ... (celý čtverec - diagonála) / dvěma.
- Quicksort porovná prvky i,j, právě když jsou spolu v jedné "fázi" algoritmu a jeden z nich byl zvolen pivotem.
- Máme pole čísel obsahující $ a_i, a_j $ (BÚNO i<j) a náhodně volíme pivota $ a_k $. Pokud $ a_k<a_i $ nebo $ a_j<a_k $, budu volit pivota znovu a tyto případy "zahodím". Zajímají nás pouze případy $ a_i \leq a_k \leq a_j $. Pokud $ a_i < a_k < a_j $, prvky se nikdy neporovnají. Porovnají se pouze při zvolení $ a_i, a_j $, což se stane s pravděpodobností $ p_{i,j} = \frac{2}{(j-i)+1} $ (dvě možnosti ku délka intervalu).
- $ \sum_{i=1}^n\sum_{j=i+1}^n {2 \over j-i+1} = 2\sum_{i=1}^n\sum_{k=2}^{n-i+1}{1 \over k} \le 2n\sum_{k=2}^n{1 \over k} = 2n\ln n $
C.f.: http://www.cs.cmu.edu/~avrim/451f09/lectures/lect0901.pdf (velmi přívětivé vysvětlení téhož + alternativní důkaz)
Obskurní
Selection sort (n-krát najdu minimum), insertion sort (aka bubble sort).
Rozhodovací stromy
Mějme algoritmus A, který třídí n-prvkovou posloupnost pomocí porovnání dvou prvků. Pak řekneme, že binární strom T je rozhodovacím stromem algoritmu A, pokud jsou vnitřní uzly ohodnoceny porovnáními $ a_i \leq a_j $, listy odpovídají permutacím a pro každou n-prvkovou posloupnost platí:
- pořadí porovnání při běhu A odpovídá cestě v T od kořene k listu, kde v listu je správná permutace, pomocí která A setřídí posloupnost
Správnost A zaručí, že různě uspořádané posloupnosti skončí v různých listech. Dolním odhadem času běhu A je nejkratší cesta kořen-list v T, horním odhadem je nejdelší cesta v T. Očekávaný čas algoritmu je průměrná délka cesty kořen-list.
Definice :
- S(n) je minimum délky nejdelší cesty kořen-list přes všechna T s n! listy.
- A(n) je minimum průměrné délky cesty kořen-list přes všechna T s n! listy.
Když nejdelší cesta kořen-list v T má délku k, pak T má nejvýše $ 2^k $ listů, proto $ n! \leq 2^{S(n)} $, což znamená $ \log_2 n! \leq S(n) $. Stirlingův vzorec:
- $ n! = \sqrt{ 2 \pi n } \left( \frac{n}{e} \right)^n \left( 1 + \frac{1}{12n} + O\left(\frac{1}{n^2}\right) \right) $
Po šílených úpravách dojdeme k výrazu:
- $ S(n) \geq \log_2 n! \geq \left( n + \frac{1}{2}\right) \log_2n - \frac{n}{ln 2} $
Nechť Bs(T) je součet všech délek cest kořen-list v T. $ B(k) = min\{Bs(T)\} $ pro T binární strom s k listy (nemusí být rozhodovací strom). Pokud by platilo, že $ B(k) \geq k \cdot \log_2 k $, pak:
- $ A(n) \geq \frac{B(n!)}{n!} \geq \frac{n! \log_2 n!}{n!} = log_2 n! \geq \left( n + \frac{1}{2}\right) \log_2n - \frac{n}{ln 2} $.
