{{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)''
}}
==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.
===A-sort===
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 :-).
===Vylepšení Mergesortu===
{{TODO|Patří to sem vůbec? Pokud ano, je potřeba líp vysvětlit}}
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>.
==Pořadové statistiky (hledání mediánu)==
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>.
{{Statnice I3}}
