{{TOC float}}
{{Sources|
''Tento výcuc ke [[Státnice|magisterským státnicovým]] otázkám z [[Státnice - Informatika - Datové struktury|datových struktur]] pochází z poznámek k [[Datové struktury I|Datovým strukturám]], vnější třídění z [[OZD I|Organizace a zpracování dat I]] -- [[User:Tuetschek|Tuetschek]] 01:08, 18 Aug 2010 (CEST)''
}}
{{TODO|A-sort?, dodat tabulky!}}
==Třídění==
{{TODO|dodat hezčí popisky z bakalářských textů}}
Existuje mnoho algoritmů, známe i (za určitých podmínek) dolní odhad složitosti.
'''HEAPSORT''' je třídění pomocí (např.) <math> d\,\!</math>-regulárních hald, akorát s duální podmínkou haldy a funkcí DELETEMAX (která ale funguje stejně jako DELETEMIN). Pak se postupně odebírají maxima a setříděná posloupnost se staví na jejich místě od konce pole.
'''MERGESORT''' je snad nejstarší, pracuje s frontou, do které na počátku nahází "předtříděné" rostoucí úseky, potom je v cyklu vybírá a jejich slití vrací zpátky, dokud nemá jen 1 posloupnost. Slití je vybrání vždy menšího na výstup a na konci dokopírování zbytků. MERGE vyžaduje <math> O(n+m)\,\!</math>, jsou-li 2 posloupnosti dlouhé <math> n\,\!</math> a <math> m\,\!</math> prvků. První rozházení vyžaduje lineární čas, potom každé projití všech prvků slitím vyrábí posloupnosti délky <math> \geq 2^{i-1}\,\!</math>, tedy počet projití všech prvků je <math> \lceil\log n\rceil\,\!</math> a celk. složitost <math> O(n\log n)\,\!</math>. Je adaptivní na předtříděné posloupnosti a při omezeném počtu rostoucích úseků dosahuje lineární složitosti.
'''QUICKSORT''' je asi nejpoužívanější, v průměru má při rovnoměrném rozložení nejnižší očekávaný čas. Vybere prvek <math> a\,\!</math> a vytvoří posloupnosti <math> a_1\dots a_{k-1}\,\!</math> prvků menších než <math> a\,\!</math> a <math> a_{k+1}\dots a_n\,\!</math> větších než <math> k\,\!</math>. Na ty sám sebe zavolá rekurzivně, do výsledku zapíše za sebe obě setříděné poloviny. Procedura (bez rekurze) vyžaduje čas <math> k\,\!</math> nebo <math> n-k\,\!</math> v 1 běhu, tj. pro <math> a\,\!</math> medián, kdyby <math> n-k=k\,\!</math>, by měl celý algoritmus složitost <math> O(n\log n)\,\!</math>. Medián lze nalézt v lin. čase, ale pak by byly MERGESORT i HEAPSORT rychlejší, proto se jako <math> a\,\!</math> bral např. první prvek posloupnosti. Potom má procedura očekávaný čas <math> O(n\log n)\,\!</math>, ale nejhorší případ <math> O(n^2)\,\!</math> -- pro neznámé rozdělení nevhodné. Volba náhodně by celý běh také mohla dost zpomalit, proto se bere medián 3-5 pevně zvolených prvků.
'''Očekávaný čas QUICKSORTu''': prvky <math> a_i,a_j\,\!</math> jsou porovnávány max. <math> 1\times\,\!</math>, a to když <math> a_i\,\!</math> nebo <math> a_j\,\!</math> je pivot a předtím ani jeden z nich pivot nebyl. Vezmeme si náhodnou veličinu <math> X_{i,j}\,\!</math>, která má hodnotu <math> 1\,\!</math>, když QUICKSORT porovnal během výpočtu <math> b_i\,\!</math> a <math> b_j\,\!</math> z nějaké výsledné setříděné posloupnosti <math> (b_i)_{1\leq i\leq n}\,\!</math>. Potom <math> \mathbf{E}X_{i,j}=p_{i,j}\,\!</math>, kde <math> p_{i,j}\,\!</math> je pravděpodobnost porovnání. Potom celk. počet porovnání v celém běhu je
:<math>\sum_{i=1}^n\sum_{j=i+1}^n\mathbf{E}X_{i,j}=\sum_{i=1}^n\sum_{j=i+1}^n p_{i,j}\,\!</math>
Pro výpočet <math> p_{i,j}\,\!</math> uvažujeme "strom rekurze", kde každý vrchol odpovídá jednomu rek. volání procedury -- potom v levém podstromě jsou operace na úsecích prvků menších než pivot <math> a_i,\dots a_{l-1}\,\!</math> této posloupnosti a v pravém na větších <math> a_{l+1},\dots a_j\,\!</math>. Celkem tedy ke každému vrcholu patří <math> j-i+1\,\!</math> prvků a <math> b_j\,\!</math> nebo <math> b_i\,\!</math> je v nějakém běhu pivot, právě když jemu odp. prvek je první z těchto <math> j-i+1\,\!</math> prvků. Takže <math> p_{i,j}= \frac{2}{j-i+1}\,\!</math>. Počet porovnání pak vyjde
:<math>\sum_{i=1}^n\sum_{j=i+1}^n\frac{2}{j-i+1}=\sum_{i=1}^n\sum_{k=2}^{n-i+1}\frac{2}{k}\leq 2n\sum_{k=2}^n\frac{1}{k}\leq 2n\int_{1}^n\frac{1}{x}\textrm{d}x=2n\ln n\,\!</math>
'''SELECTIONSORT''' třídí vybíráním nejmenšího prvku a jeho prohozením s levým krajním v nesetříděném úseku. '''INSERTIONSORT''' vkládá do setříděného úseku další prvek a postupným vyměňováním ho řadí na správné místo.
====Porovnání algoritmů====
::TABLE DELETED <math> c\,\!</math> je nějaká konstanta, <math> F\,\!</math> značí počet inverzí v posloupnosti, PP -- přímý přístup, AD -- adaptivní na předtříděné.
Pro krátké posloupnosti je do délky <math> 22\,\!</math> vhodný SELECTIONSORT, do <math> 15\,\!</math> INSERTIONSORT, jinak QUICKSORT, což vede na hybridní algoritmus. Pro A-SORT jsou nejvhodnější <math> (2,3)\,\!</math>-stromy. Poměr časů QUICKSORT, MERGESORT, HEAPSORT je v průměru <math> 1:1.33:2.22\,\!</math>, platilo to ale v roce 1984 :-).
====Vylepšení MERGERSORTu====
Nedosahuji optimálních výsledků, pokud slévané posloupnosti ve frontách nejsou přibližně stejně dlouhé. Proto provedu úvahu: mějme algoritmus, který slévá rostoucí posloupnosti a uvažujme jeho "slévací" strom <math> T\,\!</math> (kde posloupnost <math> P(v)\,\!</math> odp. vrcholu <math> v\,\!</math> (délky <math> l(P(v))\,\!</math>) vznikne slitím posloupností z jeho synů). Součet časů pro MERGESORT je pak <math> O(\sum\{l(P(v))|v\,\!</math> vnitřní vrchol <math> T\})=O(\sum\{d(t)l(P(t))|t\,\!</math> list <math> T\}\,\!</math>. Dále pracujeme jen s délkami posloupností, vytvoříme algoritmus '''OPTIM''', který při slévání sumu minimalizuje -- na začátku dá každé jednoprvkové posl. hodnotu <math> c\,\!</math>, která odpovídá hodnotě jejího prvku (?). Pro slévání vybírá posloupnosti (stromy) s nejmenším <math> c\,\!</math> a slitému stromu přiřadí <math> c_1+c_2\,\!</math>. Nakonec zbyde v množině stromů jen jeden, a ten je optimální. Pro třídění fronty podle <math> c\,\!</math> se používá BUCKETSORT. Celkem pracuje v čase <math> O(\sum_{i=1}^n l(P_i))\,\!</math> na posloupnosti rostoucích úseků <math> P_1,\dots,P_n\,\!</math>.
==Rozhodovací stromy==
{{TODO|sloučit se sekcí ve Složitosti}}
Práce většiny třídících algoritmů je založená na porovnávání, takže ji lze popsat binárním stromem, jehož vnitřní vrcholy jsou ohodnoceny porovnáním dvojic prvků. Posloupnost dat (odp. permutaci <math> \pi\,\!</math> na <math> \{1,\dots,n\}\,\!</math>) prochází stromem -- začíná v kořeni a ve vrcholu ohodnoceném porovnáním <math> a_i\,\!</math> a <math> a_j\,\!</math> jde pro <math> \pi(i)<\pi(j)\,\!</math> do levého syna, jinak do pravého. Končí, když dojde do listu.
Aby byl algoritmus korektní, musí pro každé dvě různé permutace existovat dva listy, tj. listů musí být <math> \geq n!\,\!</math>. Délka cesty reprezentuje dobu výpočtu algoritmu, takže výška stromu je dolní odhad doby výpočtu, což umožňuje získat dolní odhad složitosti třídících algoritmů. Konkrétní strom je daný algoritmem, nezáleží ale na konkrétních prvcích, jen jejich vztazích (proto je možné uvažovat jen permutace <math> \{1,\dots,n\}\,\!</math>). Pro plýtvající algoritmus mohou existovat listy, neodpovídající žádné permutaci, tj. porovnává stejnou dvojici prvků <math> 2\times\,\!</math> (a jedna z možností už nemůže nastat).
''Rozhodovací strom třídícího algoritmu '''A'' pro n-prvkové posloupnosti''' je binární strom, jehož vrcholy jsou ohodnocené porovnáními, a v němž pro každou permutaci <math> \pi\,\!</math> na <math> \{1,\dots,n\}\,\!</math> platí, že posloupnost při třídění permutace <math> \pi\,\!</math> algoritmem '''A''' je stejná jako posloupnost porovnání při průchodu permutace tímto stromem.
Pro rovnoměrné rozdělení je očekávaný čas průměrná délka cesty od kořene k listům, nejhorší čas je výška stromu. Definujeme <math> S(n)\,\!</math> jako minimum délek nejdelších cest z kořene do listu přes všechny stromy s <math> n!\,\!</math> listy a <math> A(n)\,\!</math> minimum průměrných délek. Potom <math> S(n)\geq\log(n!)\,\!</math> a ze Stirlingova vzorce <math> n!=\sqrt{2\pi n}(\frac{n}{e})^n(1+\frac{1}{12n}+O(\frac{1}{n^2})\,\!</math> a faktu, že <math> \frac{1}{\ln 2}=\log e\,\!</math> dostanu odhad
:<math>S(n) \geq \log n!\geq \left(n+\frac{1}{2}\right)\log n-\frac{n}{\ln 2}\,\!</math>
Pro odhad <math> A(n)\,\!</math> definujeme <math> B(k)\,\!</math> jako minimum součtů délek všech cest z kořene do listů přes všechny stromy s <math> k\,\!</math> listy. Dokážeme, že <math> B(k)=k\log k\,\!</math>, proto se stačí omezit na úplné binární stromy (u všech ost. dostanu větší hodnoty) a postupovat indukcí (ze dvou podstromů s <math> k_1,k_2\,\!</math> listy dělám jeden s <math> k=k_1+k_2\,\!</math> listy). Dostanu nerovnost <math> k_1+k_2+k_1\log k_1+k_2\log k_2\geq k\log k\,\!</math> a převedu ji na funkci <math> f(x)=x\log x+(k-x)\log (k-x)+k-k\log k\,\!</math>, najdu, že její minimum je <math> 0\,\!</math>, takže původní nerovnost platí.
==Přihrádkové třídění==
Algoritmus '''BUCKETSORT''' třídí jen přirozená čísla z intervalu <math> <0,m>\,\!</math> a to zavedením <math> m+1\,\!</math> množin, do kterých je rozhází a nakonec tyto spojí do výsledku. Třídění je stabilní pro opakující se prvky, inicializace množin a projití při konkatenaci potřebují <math> O(m)\,\!</math>, rozházení prvků pak <math> O(n)\,\!</math>, takže celkem <math> O(n+m)\,\!</math>.
Sofistikovanější verze '''HYBRIDSORT''' třídí reálná čísla z <math> <0,1>\,\!</math>, má dané <math> \alpha\,\!</math> (počet přihrádek v poměru k <math> n\,\!</math>), rozhazuje do <math> k=\alpha n\,\!</math> přihrádek a ty pak třídí haldou. Nejhorší možný čas je <math> O(n\log n)\,\!</math>, protože nejhůře se může stát, že všechny prvky nacpu do 1 přihrádky. Očekávaný čas pro nezávislé rovnoměrně rozdělené prvky je <math> O(n)\,\!</math> -- pravděpodobnost velikostí množin se řídí binomickým rozdělením s parametrem <math> 1/k\,\!</math>, střední hodnota pak je <math> k+k\left(\frac{n(n-1)}{k^2}+\frac{n}{k}\right)=O(n)\,\!</math>. I kdybychom použili algoritmus s kvadratickou složitostí ve třídění jednotl. přihrádek, zůstane očekávaná složitost lineární.
'''WORDSORT''' je modifikace pro třídění slov: Příprava: rozhodí slova do množin <math> L_i\,\!</math> podle jejich délky, pak vytvoří <math> \{(j,a_i[j])\}\,\!</math>, kterou setřídí podle druhé složky BUCKETSORTem a výsledek setřídí podle první složky (stejně). Výsledek (dvojice) pak rozstrká do množin <math> S_i\,\!</math> podle pořadí písmena ve slově, když odstraní duplicity.
Pak v hlavním cyklus postupuju od největší možné délky a pro každé <math> i\,\!</math> nejdřív podle <math> i\,\!</math>-tého písmena rozhodím všechna slova délky <math> \geq i\,\!</math> do množin <math> T_x\,\!</math>. Potom podle množiny <math> S_i\,\!</math> vyberu všechna neprázdná <math> T_x\,\!</math> a seřadím je za sebe.
Výpočet délek slov, inicializace <math> L_i\,\!</math> a zařazení slov do <math> L_i\,\!</math> vyžadují čas <math> O(l)\,\!</math>, kde <math> L\,\!</math> je součet délek všech řetězců. Vytvoření seznamu dvojic a jeho třídění vyžaduje také <math> O(l)\,\!</math>. Založení <math> S_i\,\!</math> a přeházení dvojic do nich také <math> O(l)\,\!</math>. Inicializace <math> T_x\,\!</math> je <math> O(|\Sigma|)\,\!</math>, kde <math> |\Sigma|\,\!</math> je velikost abecedy. V hlavním cyklu v každém kroku potřebuji dvakrát čas <math> O(l_i)\,\!</math> (součet délek slov dlouhých <math> i\,\!</math> nebo víc). Celkem tedy <math> O(l+|\Sigma|)\,\!</math>.
==Pořadové statistiky==
{{TODO|sloučit se složitostí -- mediány}}
Chceme nalézt <math> k\,\!</math>-tý nejmenší prvek nějaké množiny. První algoritmus '''FIND''' se chová podobně jako QUICKSORT: zvolí si pivot, rozdělí posloupnost na množiny prvků větších a menších než pivot a pokračuje v jedné z nich, v té, ve které by se <math> k\,\!</math>-tý nejmenší měl nacházet (podle jejich velikostí). Takto jde, dokud neoddělí množinu velikosti <math> 1\,\!</math>. V nejhorším případě má složitost <math> O(n^2)\,\!</math>. Očekávaný čas odhadneme na <math> 4n\,\!</math> a dokážeme indukcí z rekurzivního vzorce <math> T(n,i)=n+\frac{1}{n}(\sum_{k=1}^{i-1}T(n-k,i-k)+\sum_{k=i+1}^n T(k,i)\,\!</math>.
Alogritmus '''SELECT''' najde <math> k\,\!</math>-tý nejmenší i v nejhorším případě v lineárním čase. Má threshold <math> n=100\,\!</math>, pod kterým množinu přímo třídí, pro větší rozdělí do 5-tic a z pro každou z nich najde (přímo) medián. Pak z mediánů pětic najde medián rekurzivně. Prvky rozdělí na větší a menší než medián mediánů a pokračuje rekurzivně na jedné z množin. Korektní je podobně jako FIND, složitost plyne z toho, že v každém kroku (který už přímo netřídí) se zbavím alespoň <math> \lfloor\frac{3n}{10}\rfloor-1\,\!</math>, takže mi zbyde <math> \leq \frac{8n}{11}\,\!</math>, důkaz počtu kroků z rekurentního vzorce indukcí.
FIND bývá rychlejší než SELECT pro většinu případů. Je známo, že medián lze nalézt na <math> 3n\,\!</math> porovnání a že dolní odhad počtu porovnání je <math> 2n\,\!</math>.
{{Statnice I3}}
