TIN066 Základní metody třídění

Z ωικι.matfyz.cz
Verze z 21. 1. 2014, 12:36, kterou vytvořil 78.128.169.81 (diskuse) (Rozhodovací stromy)

(rozdíl) ← Starší verze | zobrazit aktuální verzi (rozdíl) | Novější verze → (rozdíl)
Přejít na: navigace, hledání
Tato část je neúplná a potřebuje rozšířit. la la la

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} $.