= Třídění ve vnitřní a vnější paměti (8×🎓)=
{{TOC float}}
{{Sources|
''Založeno na [[Státnice_-_Třídění|Třídění]] (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]])
Více prakticky pro I2
09/10: Trídení ve vnitrní a vnejší pameti, casová složitost algoritmu vyjádrená v poctu I/O operací.
14/15: Trídení ve vnitrní a vnejší pameti. Dolní odhady pro usporádání (rozhodovací stromy).
}}
{{TODO|projít a doplnit podle zkazek}}
{{zkazky| 1=
* '''Triedenie vo vnutornej a vonkajsej pamati (2014)''' - BS, SS, HS, MS, QS, Bucket + jemne Radix + odhady na zlozitost, hladanie pivota atd, - zlievanie, n-cestne zlievanie, dlhe behy pomocou dvojitej haldy
* '''Třídění ve vnitřní a vnější paměti (2012)''' - Napsal jsem dva algoritmy třídění ve vnitřní paměti - QuickSort a MergeSort. U obou jsem dokázal časovou složitost ( u QuickSortu v průměrném případě). Dále jsem popsal externí mergesort + jak se vyrábějí běhy pomocí dvojité haldy. Úplně nakonec jsem popsal a dokázal dolní odhad časové složitosti třídění pomocí porovnávání. Zkoušející se zeptal jenom na třídění bez porovnávání - řekl jsem CountSort se zmínkou o složitosti a to mu stačilo.
* '''Triedenia na vonkajsej a vnutornej pamati (2011, Kopecky/Mares)''' - Popisal som vsetky zname mergesorty, haldy a ich variacie na vonk. pamati a klasika quick-, merge-, heap-, insertion-, bubble-, ... -sorty na vnutornej pamati. Pre vsetky som ukazal ich casovu zlozitost. Otazky sa tykali ich porovnania v roznych pripadoch rozdelenia dat, pamatovej zlozitosti, atd. Bolo to celkom prijemne a vysledna znamka asi 1.
* '''Vnitřní a vnější třidění (2010, Kopecký)''' - Vnitřní=CPU operace, vější=přistupy na disk. Rozdělení (porovnávání prvků/ostatní). Příklady. U quicksortu hledání pivota v lineárním čase. U merge jak se to má s výhodamy/nevýhodami s různým počtem pásek. Vytváření běhů pomocí haldy/dvojité haldy.
* '''Triedenia vo vonkajsej a vnutornej pamati (2010, Surynek)''' - mal som si vybrat z kazdeho jedno a dokazat jeho zlozitost. Tu som sa celkom zlakol, pretoze som sa celu tuto otazku ucil prehladovo stylom "mergersort,rozdelim, zlejem, nlongn, heapsort,halda,trham,nlogn" a ziaden konkretny dokaz, takze k tejto otazke sa urcite oplati nejaky sa naucit. Nastastie som si spomenul na merge sortcez master theorem, co som sa ucil na otazku rozdeluj a panuj, tak som to tam napisal aj so znenim master theorem. Tu sa ma pytal,ako by sa to dalo dokazat inak,tak som povedal ze substituciou (on vravel,ze este indukciou) a substituciu som mu musel ukazat. Este chcel vediet, ako presne prebieha zlievanie (chcel pocut, ze sa berie vzdy mensi prvok z kazdeho behu). Potom som povedal dve vety o heapsorte (halda v O(n), n krat trham + oprava -> nlogn). K vonkajsim triedeniam som popisal n-cestny algoritmus, napisal vzorec pre zlozitost a povedal, ktore pismenka v tom vzorci co znamenaju. Na zaver chcel, aby som dokazal zlozitost problemu triedenia, to som len tak slovne, nieco sa mu tam nepacilo ale moc som nepochopil co, nasledne chcel aby som mu to dokazal, kde som nebol schopny odvodit vysku stromu v zavislosti na pocte listov Kazdopadne mi nakoniec povedal, ze to uz bolo nad ramec a len chcel vediet, ci viem pocitat... co zjavne neviem.
* '''Trideni ve vnitrni a vnejsi pameti (2009)''' - asi nejjednodusii otazka, co tam vubec je
* '''Triedenie vo vonkajšej pamäti(2008, Koubkova)''' - no comment
* '''Trideni ve vnitrni pameti (2008, Zemlicka)''' - Klasika, nejake ty vychytanejsi, kdy jaky se vyplati vic (asort s malo inverzemi, prihradkove pri malem univerzu). celkem o.k., meli jsme trochu problemy s terminologii, jelikoz zemlicka pouziva jinou nez koubek
* http://www.algovision.org/Algovision/Algovision.html
I1/I4:
* '''Třídění ve vnitřní a vnější paměti (2013, Fiala) -''' Pokažen Mergesort v externí paměti. Rozhodovací strom.
}}
==Třídění založené na porovnávání==
Existuje mnoho algoritmů, známe i (za určitých podmínek) dolní odhad složitosti.
=== Heapsort ===
'''HEAPSORT''' je třídění pomocí (např.) <math> d\,\!</math>-[[Státnice_-_Stromové_vyhledávací_struktury#Regul.C3.A1rn.C3.AD_haldy|regulárních hald]], jen lokální podmínku haldy používáme v duální podobě a máme funkci '''DELETEMAX''' (která ale funguje stejně jako '''DELETEMIN'''). Postupně se odebírají maxima a setříděná posloupnost se staví na jejich místě od konce pole. Iterace končí, když v haldě zbývá jen jeden prvek. Celkem <math> O(n\log n)\,\!</math> operací.
=== Mergesort ===
'''MERGESORT''' je snad nejstarší "chytrý" třídící algoritmus. 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 jednu posloupnost. Slití je vybrání vždy menšího na výstup a na konci dokopírování zbytků.
Jedna operace slití 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 celková 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 ===
'''QUICKSORT''' je asi nejpoužívanější třídící algoritmus, v průměru má při rovnoměrném rozložení nejnižší očekávaný čas. Využívá techniky [[Státnice - Metody tvorby algoritmů#Rozděl a panuj|rozděl a panuj]].
# Vybere prvek <math> a\,\!</math> (pivot).
# 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> a\,\!</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 jednom 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 lineárním čase, ale pak by byly '''MERGESORT''' i '''HEAPSORT''' rychlejší, proto se jako <math> a\,\!</math> bere 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>, což je pro neznámé rozdělení dat nevhodné. Náhodná volba by celý běh také mohla dost zpomalit, proto se v praxi bere medián tří až pěti pevně zvolených prvků.
==== Očekávaný čas Quicksortu ====
Dva libovolné prvky <math> a_i,a_j\,\!</math> jsou porovnávány maximálně jednou, 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>, a <math>0</math> jinak. 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 rekurzivnímu volání procedury a s tím i nějaké podposloupnosti <math>a_i,\dots,a_j</math> (do té už se sahá jen v jeho podstromě). V jeho 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>. Přiřadíme každému vrcholu jeho pivot a očíslujeme vrcholy prohledáváním do šířky. Pak <math>X_{i,j} = 1</math>, když <math> b_j\,\!</math> nebo <math> b_i\,\!</math> je první pivot z množiny <math>\{b_i,\dots b_j\}</math> v tomto očíslování (protože kdyby to byl jiný prvek z této množiny, rozdělím <math>b_i</math> a <math>b_j</math>, aniž bych je porovnal; naopak prvky mimo tuto množinu coby pivoty od sebe <math>b_i</math> a <math>b_j</math> neoddělí). Množina <math>\{b_i,\dots,b_j\}</math> má <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>
=== Jednoduché třídění ===
* '''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.
* '''INSERTSORT''' vkládá do setříděného úseku další prvek a postupným vyměňováním ho řadí na správné místo.
* '''SHELLSORT''' je jeho vylepšení -- postupně '''INSERTSORT'''em třídí sekvence složené z každého <math>k</math>-tého prvku pro klesající <math>k\to 1</math> (sekvence klesajících <math>k</math> musí být zvolena "šikovně").
* '''BUBBLESORT''' -- iterativně prochází posloupností a prohazuje inverze
* Jeho varianta '''SHAKESORT''', která posloupnosti prochází tam a zpátky.
{{collapse|A-sort - aplikace (a,b)-stromů, vhodný pro částečně setříděné posloupnosti, jinak k ničemu |
Tento algoritmus je aplikací <math> (a,b)\,\!</math> stromů v třídících algoritmech, vhodnou pro částečně předtříděné posloupnosti. Jinak proti klasickým algoritmům nemá žádné výhody. Pro algoritmus je nutné znát list s nejmenším prvekm FIRST, cestu k němu od kořene a pro každý list ukazatele na následující v uspořádání NEXT.
'''Postup:''' Odzadu (od "předtříděně největšího") vkládat prvky do stromu modifikovaným A-INSERTem a pak přečíst posloupnost listů (jít po NEXT). A-INSERT pracuje tak, že místo pro vložení prvku hledá od FIRST (jde postupně nahoru po otcích a hledá, kde nejdřív může slézt zas k listům).
'''Složitost:''' Pomalejší než běžné třídění na libovolná data (asymptoticky stejné), ale rychlejší na částečně předtříděná. Vezmeme <math> F\,\!</math> -- počet inverzí v posloupnosti. Celk. potřebuju <math> O(n)\,\!</math> pro načtení prvků, <math> O(n)\,\!</math> pro všechna štěpení dohromady ze všech běhů A-INSERTu a na každé vložení <math> O(h)\,\!</math> pro nalezení místa, kde <math> h\,\!</math> je výška, kam se z FIRST dostanu, přeskočím tak <math> f_i\geq a^{h-2}\,\!</math> vrcholů (menších než vkládaný) a <math> h\in O(\log f_i)\,\!</math>. Součet <math> f_i\,\!</math> za <math> \forall i\,\!</math> dává:
:<math>\sum_{i=1}^n \log f_i = n\log(\prod_{i=1}^{n}f_i)^{\frac{1}{n}}\leq n\log\frac{\sum_{i=1}^n f_i}{n}=n\log\frac{F}{n}\,\!</math>
Protože se nepoužívá DELETE, hodí se na toto <math> (2,3)\,\!</math> stromy. Pro míru <math> F\leq n\log n\,\!</math> má složitost <math> O(n\log\log n)\,\!</math>, v urč. případech i rychlejší než Quicksort.
}}
===Porovnání algoritmů===
{| border="1" cellspacing="0"
|Algoritmus || Čas nejhůř || Čas <math>\varnothing</math> || Porov. nejhůř || Porov. <math>\varnothing</math> || PP || Paměť || AD
|-
|'''QUICKSORT''' || <math>\Theta(n^2)</math> || <math>9n\log n</math> || <math>n^2/2</math> || <math>1.44n\log n</math> || A || <math>n+\log n+c</math> || N
|-
|'''HEAPSORT''' || <math>20n\log n</math> || <math>\leq 20n\log n</math> || <math>2n\log n</math> || <math>2n\log n</math> || A || <math>n+c</math> || N
|-
|'''MERGESORT''' || <math>12n\log n</math> || <math>\leq 12n\log n</math> || <math>n\log n</math> || <math>n\log n</math> || N || <math>2n+c</math> || A
|-
|'''A-SORT''' || <math>O(n\log(F/n))</math> || <math>O(n\log(F/n))</math> || <math>O(n\log(F/n))</math>|| <math>O(n\log(F/n))</math>|| A || <math>5n+c</math> || A
|-
|'''SELECTIONSORT''' || <math>2n^2</math> || <math>2n^2</math> || <math>n^2/2</math> || <math>n^2/2</math> || A || <math>n+c</math> || N
|-
|'''INSERTSORT''' || <math>O(n^2)</math> || <math>O(n^2)</math> || <math>n^2/2</math> || <math>n^2/4</math> || N || <math>n+c</math> || A
|}
<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> '''INSERTSORT''', jinak '''QUICKSORT''', což vede k hybridnímu algoritmu. 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 :-).
{{collapse|1=Vylepšení Mergesortu|2=
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>.
}}
==Přihrádkové třídění==
=== Bucketsort (Counting sort) ===
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>.
Varianta '''RADIXSORT''' umí třídit i ve větších intervalech, když používá BUCKETSORT na každou jednotlivou číslici. Protože BUCKETSORT je stabilní, bude to celé fungovat.
=== Hybrid Sort ===
Sofistikovanější verze '''HYBRIDSORT''' třídí reálná čísla z <math>\langle 0,1\rangle\,\!</math> (a obecně tedy jakékoliv klíče). 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>\mathbf{E}(\sum_{i=1}^k (1 + X_i\log X_i)) \leq \mathbf{E}(\sum_{i=1}^k (1 + X_i^2)) = k+k\left(\frac{n(n-1)}{k^2}+\frac{n}{k}\right)=O(n)\,\!</math>
Jak je vidět z odhadu, i kdybychom použili algoritmus s kvadratickou složitostí ve třídění jednotlivých přihrádek, zůstane očekávaná složitost lineární.
=== Wordsort ===
'''WORDSORT''' je modifikace BUCKETSORTu pro třídění slov. Příprava:
# Rozhodí slova do množin <math> L_i\,\!</math> podle jejich délky.
# Vytvoří dvojice pozice-písmeno <math> \{(j,a_i[j])\}\,\!</math>, kterou setřídí podle druhé složky BUCKETSORTem, výsledek setřídí podle první složky (stejně), tj. má seznam setříděných dvojic pozice-písmeno, které se ale mohou opakovat.
# Dvojice rozstrká do množin <math> S_i\,\!</math> pro každou pozici <math>i</math> a odstraní duplicity.
Pak v hlavním cyklu postupuje od největší možné délky a pro každé <math> i\,\!</math> pracuju jen s množinou slov délky <math>\geq i</math>:
# Podle <math> i\,\!</math>-tého písmena rozhodím všechna aktuálně tříděná slova 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 sliju je za sebe.
# Pro další krok přidávám kratší slova vždy na začátek množiny aktuálně tříděných.
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>.
{{collapse|1=Pořadové statistiky (hledání mediánu) - už se asi nezkouší|2=
Vstupem je (neuspořádáná) posloupnost <math> n\,\!</math> (navzájem různých) čísel. Výstup je <math> \lfloor\frac{n}{2}\rfloor\,\!</math>-té, nebo obecně <math>k</math>-té nejmenší číslo z nich. Složitost budeme měřit ''počtem porovnání''.
Z dvou následujících '''FIND''' bývá rychlejší než '''SELECT''' pro většinu případů, ale nemá zaručenou asymptotickou složitost. 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>.
;Hledání mediánu technikou rozděl a panuj (algoritmus FIND)
Tento algoritmus používá techniku "rozděl a panuj". chová se podobně jako '''QUICKSORT''' a hledá obecně <math> k\,\!</math>-té nejmenší číslo:
# Vybrat pivota a rozdělit posloupnost pomocí <math> n-1\,\!</math> porovnání na 3 oddíly: čísla menší než pivot (<math> a\,\!</math> prvků), pivota samotného a čísla větší než pivot (<math> n-a-1\,\!</math> prvků).
#
## Pokud je <math> a + 1 < k\,\!</math>, hledám rekurzivně <math> k-a+1\,\!</math>-tý prvek v <math> n-a-1\,\!</math> prvcích
## Pokud je <math> a + 1 = k\,\!</math>, vracím pivot
## Pokud je <math> a + 1 > k\,\!</math>, hledám rekurzivně <math> k\,\!</math>-tý prvek v <math> a\,\!</math> prvcích
Rekurzivní vzorec <math> T(n) = T(n-1) + (n-1)\,\!</math> v nejhorším případě, což dává <math> \Theta(n^2)\,\!</math>. Očekávaný čas odhadneme na <math> 4n\,\!</math> a dokážeme indukcí podle <math>n</math> z rekurzivního vzorce <math> T(n,i)=n+\frac{1}{n}\left(\sum_{k=1}^{i-1}T(n-k,i-k)+\sum_{k=i+1}^n T(k,i)\right)\,\!</math>.
;Zaručeně lineární hledání mediánu (algoritmus SELECT)
Vylepšení, garantující dobrý výběr pivota a lineární složitost i v nejhorším čase:
# Rozdělit posloupnost na pětice (poslední může být neúplná, mějme threshold např. <math> n=100\,\!</math>, pod kterým množinu přímo třídíme)
# V každé pětici najít medián
# Rekurzivně najít medián těchto mediánů
# Použít ho jako pivot pro dělení celé posloupnosti, protože je větší než alespoň 3 prvky z alespoň <math> 1/2\,\!</math> pětic (až na zakrouhlení), je větší než alespoň <math> 1/2 \cdot 3/5 = 3/10\,\!</math> prvků (a také menší než alespoň <math> 3/10\,\!</math> prvků)
# Z toho mám vždy zaručeno, že zahodím alespoň <math> 3/10\,\!</math> prvků pro následující krok.
Vzorec potom vychází: <math> T(n) = c\cdot\frac{n}{5} + T(\frac{n}{5}) + (n-1) + T(\frac{7}{10}n)\,\!</math> a podle Master Theoremu nebo substituční metodou se dá [[Státnice - Metody tvorby algoritmů#Analýza složitosti algoritmů rozděl a panuj|vyčíslit]] jako <math> T(n) = \Theta(n)\,\!</math>.
}}
== Třídění na vnější paměti ==
[[http://www.itu.dk/people/pagh/DBT07/sorting.pdf]]
Pro třídění něčeho, co se nevejde do operační paměti, se používá '''MERGESORT''':
# Ze dvou souborů vezmu dva prvky
# Vyberu menší z nich, zapíšu ho na výstup
# Ze souboru, odkud ten menší pocházel, načtu další.
# Konec setříděného úseku poznám tak, že další načtený prvek je menší než ten vypsaný. Pokud dojdu na konec setříděného úseku na jednom ze vstupů, dokopíruju zbytek setříděného úseku i z druhého vstupu na výstup.
Postupně dostávám delší setříděné kusy. Původní použití - setříděni kousků, které se vešly do paměti, a slévání na páskách. Dnes je použitelné i na HDD.
N-cestný '''MERGESORT''' na vnější paměti: Mám-li <math>n+1</math> stránek v paměti:
# Vytvořit setříděné běhy velikosti <math>n</math> stránek (použít '''HEAPSORT''' nebo '''QUICKSORT''').
# Pak v každém kroku slévat (maximálně) <math>n</math> nejkratších běhů, výsledek ukládat jako 1 běh.
Pro <math> M\,\!</math> stránek v celém souboru je složitost <math> O(2M\lceil\log_n M/n\rceil)\,\!</math> - celé projde <math> \log_n(M/n)\,\!</math>-krát procesem slévání.
'''HEAPSORT''' může vytvořit i delší běhy, než co se vejde do paměti:
# Průběžně odebírám a vypisuju minimální prvky a načítám další.
# Pokud je načtený prvek větší než minimum, hodím ho na haldu.
# Pokud je menší, dám ho do aktuálně vznikající haldy na druhém konci pole.
Až se vyčerpá halda, začnu nový běh. V nejhorším případě dopadne stejně jako třídění v paměti, průměrně je 2x lepší, ideálně setřídí všechno.
=Dolní odhady pro usporádání (🎓🎓)=
''Dolní odhady pro usporádání (rozhodovací stromy).''
{{zkazky|
* '''Dolní odhady pro uspořádání (2009)'''}}
====Definice (Složitost problému)====
''Složitost problému'' je složitost asymptoticky nejlepšího ''možného'' algoritmu, který řeší daný problém (ne nejlepšího známého).
Každý konkrétní algoritmus dává horní odhad složitosti. Dolní odhady (až na triviální -- velikost vstupu, výstupu) jsou složitější.
====Věta (Dolní odhad složitosti mediánu)====
Pro výběr <math> k\,\!</math>-tého z <math> n\,\!</math> prvků je třeba alespoň <math> n-1\,\!</math> porovnání, tj. problém je <math> \Omega(n)\,\!</math>.
====Důkaz====
{{TODO|}}
Intuitivně potřebuju medián, i kdyby mi spadnul z nebe, porovnat se všemi ostatními prvky, abych vůbec zjistil, jestli to je medián ...
====Věta (Dolní odhad složitosti třídění)====
Pro každý třídící algoritmus, založený na porovnávání prvků, existuje vstupní posloupnost, pro kterou provede <math> \Omega(n\log n)\,\!</math> porovnání.
====Důkaz====
Nakreslím si rozhodovací strom jako model algoritmu -- všechny vnitřní uzly odpovídají nějakému porovnání, které algoritmus provedl, jejich synové jsou operace, které nasledovaly po různých výsledcích toho porovnání (BÚNO jsou-li prvky různé, bude strom binární). Listy odpovídají setříděným posloupnostem. Aby byl algoritmus korektní, musí mít strom listy se všemi <math> n!\,\!</math> možnými pořadími prvků.
Pro plýtvající algoritmus mohou existovat listy, neodpovídající žádné permutaci, tj. porovnává stejnou dvojici prvků dvakrát (a jedna z možností už nemůže nastat). 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.
Označím výšku jako <math> h\,\!</math>, pak počet listů je <math> \leq 2^h\,\!</math> a tedy <math> n!\leq 2^h\,\!</math>, tj. <math> h\geq \log n!\,\!</math>, pro dolní odhad <math>\Omega(n\log n)</math> stačí odhad faktoriálu <math> n! < n^{\frac{n}{2}}\,\!</math>, případně můžu použít Stirlingův vzorec <math> n!\approx \sqrt{2\pi n}(\frac{n}{e})^n\,\!</math> a dostávám <math>\Theta(n\log n)</math>.
{{Statnice I2}}
