TIN066 Základní metody třídění
Heapsort[editovat | editovat zdroj]
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[editovat | editovat zdroj]
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[editovat | editovat zdroj]
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í[editovat | editovat zdroj]
Selection sort (n-krát najdu minimum), insertion sort (aka bubble sort).
Rozhodovací stromy[editovat | editovat zdroj]
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} $.
