{{TOC float}}

{{Sources| Tento výcuc ke <Státnice> otázkám z <Státnice%20-%20Informatika%20-%20Datové%20struktury> pochází z poznámek k <Datové%20struktury%20I>, vnější třídění z <OZD%20I> -- User: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ř.) d  ⁣ d\,\!-<Státnice_-_Stromové_vyhledávací_struktury#Regul.C3.A1rn.C3.AD_haldy>, 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 O(nlog⁡n)  ⁣ O(n\log n)\,\! 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 O(n+m)  ⁣ O(n+m)\,\!, jsou-li 2 posloupnosti dlouhé n  ⁣ n\,\! a m  ⁣ m\,\! prvků. První rozházení vyžaduje lineární čas, potom každé projití všech prvků slitím vyrábí posloupnosti délky ≥2i−1  ⁣ \geq 2^{i-1}\,\!, tedy počet projití všech prvků je ⌈log⁡n⌉  ⁣ \lceil\log n\rceil\,\! a celková složitost O(nlog⁡n)  ⁣ O(n\log n)\,\!. 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%20-%20Metody%20tvorby%20algoritmů#Rozděl%20a%20panuj>.

  1. Vybere prvek a  ⁣ a\,\! (pivot).

  2. Vytvoří posloupnosti a1…ak−1  ⁣ a_1\dots a_{k-1}\,\! prvků menších než a  ⁣ a\,\! a ak+1…an  ⁣ a_{k+1}\dots a_n\,\! větších než a  ⁣ a\,\!.

  3. 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 k  ⁣ k\,\! nebo n−k  ⁣ n-k\,\! v jednom běhu, tj. pro a  ⁣ a\,\! medián, kdyby n−k=k  ⁣ n-k=k\,\!, by měl celý algoritmus složitost O(nlog⁡n)  ⁣ O(n\log n)\,\!. Medián lze nalézt v lineárním čase, ale pak by byly MERGESORT i HEAPSORT rychlejší, proto se jako a  ⁣ a\,\! bere např. první prvek posloupnosti.

Potom má procedura očekávaný čas O(nlog⁡n)  ⁣ O(n\log n)\,\!, ale nejhorší případ O(n2)  ⁣ O(n^2)\,\!, 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 ai,aj  ⁣ a_i,a_j\,\! jsou porovnávány maximálně jednou, a to když ai  ⁣ a_i\,\! nebo aj  ⁣ a_j\,\! je pivot a předtím ani jeden z nich pivot nebyl. Vezmeme si náhodnou veličinu Xi,j  ⁣ X_{i,j}\,\!, která má hodnotu 1  ⁣ 1\,\!, když QUICKSORT porovnal během výpočtu bi  ⁣ b_i\,\! a bj  ⁣ b_j\,\! z nějaké výsledné setříděné posloupnosti (bi)1≤i≤n  ⁣ (b_i)_{1\leq i\leq n}\,\!, a 00 jinak. Potom EXi,j=pi,j  ⁣ \mathbf{E}X_{i,j}=p_{i,j}\,\!, kde pi,j  ⁣ p_{i,j}\,\! je pravděpodobnost porovnání. Potom celk. počet porovnání v celém běhu je

:∑i=1n∑j=i+1nEXi,j=∑i=1n∑j=i+1npi,j  ⁣\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}\,\!

Pro výpočet pi,j  ⁣ p_{i,j}\,\! uvažujeme "strom rekurze", kde každý vrchol odpovídá jednomu rekurzivnímu volání procedury a s tím i nějaké podposloupnosti ai,…,aja_i,\dots,a_j (do té už se sahá jen v jeho podstromě). V jeho levém podstromě jsou operace na úsecích prvků menších než pivot ai,…al−1  ⁣ a_i,\dots a_{l-1}\,\! této posloupnosti a v pravém na větších al+1,…aj  ⁣ a_{l+1},\dots a_j\,\!. Přiřadíme každému vrcholu jeho pivot a očíslujeme vrcholy prohledáváním do šířky. Pak Xi,j=1X_{i,j} = 1, když bj  ⁣ b_j\,\! nebo bi  ⁣ b_i\,\! je první pivot z množiny {bi,…bj}\{b_i,\dots b_j\} v tomto očíslování (protože kdyby to byl jiný prvek z této množiny, rozdělím bib_i a bjb_j, aniž bych je porovnal; naopak prvky mimo tuto množinu coby pivoty od sebe bib_i a bjb_j neoddělí). Množina {bi,…,bj}\{b_i,\dots,b_j\} má j−i+1j-i+1 prvků, takže pi,j=2j−i+1  ⁣ p_{i,j}= \frac{2}{j-i+1}\,\!. Počet porovnání pak vyjde

:∑i=1n∑j=i+1n2j−i+1=∑i=1n∑k=2n−i+12k≤2n∑k=2n1k≤2n∫1n1xdx=2nln⁡n  ⁣\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\,\!

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ě INSERTSORTem třídí sekvence složené z každého kk-tého prvku pro klesající k→1k\to 1 (sekvence klesajících kk 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í (a,b)  ⁣ (a,b)\,\! 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 F  ⁣ F\,\! -- počet inverzí v posloupnosti. Celk. potřebuju O(n)  ⁣ O(n)\,\! pro načtení prvků, O(n)  ⁣ O(n)\,\! pro všechna štěpení dohromady ze všech běhů A-INSERTu a na každé vložení O(h)  ⁣ O(h)\,\! pro nalezení místa, kde h  ⁣ h\,\! je výška, kam se z FIRST dostanu, přeskočím tak fi≥ah−2  ⁣ f_i\geq a^{h-2}\,\! vrcholů (menších než vkládaný) a h∈O(log⁡fi)  ⁣ h\in O(\log f_i)\,\!. Součet fi  ⁣ f_i\,\! za ∀i  ⁣ \forall i\,\! dává:

:∑i=1nlog⁡fi=nlog⁡(∏i=1nfi)1n≤nlog⁡∑i=1nfin=nlog⁡Fn  ⁣\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}\,\!

Protože se nepoužívá DELETE, hodí se na toto (2,3)  ⁣ (2,3)\,\! stromy. Pro míru F≤nlog⁡n  ⁣ F\leq n\log n\,\! má složitost O(nlog⁡log⁡n)  ⁣ O(n\log\log n)\,\!, v urč. případech i rychlejší než Quicksort.

Porovnání algoritmů

c  ⁣ c\,\! je nějaká konstanta, F  ⁣ F\,\! 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 22  ⁣ 22\,\! vhodný SELECTIONSORT, do 15  ⁣ 15\,\! INSERTSORT, jinak QUICKSORT, což vede k hybridnímu algoritmu. Pro A-SORT jsou nejvhodnější (2,3)  ⁣ (2,3)\,\!-stromy. Poměr časů QUICKSORT, MERGESORT, HEAPSORT je v průměru 1:1.33:2.22  ⁣ 1:1.33:2.22\,\!, 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 T  ⁣ T\,\! (kde posloupnost P(v)  ⁣ P(v)\,\! odp. vrcholu v  ⁣ v\,\! (délky l(P(v))  ⁣ l(P(v))\,\!) vznikne slitím posloupností z jeho synů). Součet časů pro MERGESORT je pak O(∑{l(P(v))∣v  ⁣ O(\sum\{l(P(v))|v\,\! vnitřní vrchol T})=O(∑{d(t)l(P(t))∣t  ⁣ T\})=O(\sum\{d(t)l(P(t))|t\,\! list T}  ⁣ T\}\,\!. 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 c  ⁣ c\,\!, která odpovídá hodnotě jejího prvku (?). Pro slévání vybírá posloupnosti (stromy) s nejmenším c  ⁣ c\,\! a slitému stromu přiřadí c1+c2  ⁣ c_1+c_2\,\!. Nakonec zbyde v množině stromů jen jeden, a ten je optimální. Pro třídění fronty podle c  ⁣ c\,\! se používá BUCKETSORT. Celkem pracuje v čase O(∑i=1nl(Pi))  ⁣ O(\sum_{i=1}^n l(P_i))\,\! na posloupnosti rostoucích úseků P1,…,Pn  ⁣ P_1,\dots,P_n\,\!.

Přihrádkové třídění

Bucketsort (Counting sort)

Algoritmus BUCKETSORT třídí jen přirozená čísla z intervalu <0,m>  ⁣ <0,m>\,\! a to zavedením m+1  ⁣ m+1\,\! 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í O(m)  ⁣ O(m)\,\!, rozházení prvků pak O(n)  ⁣ O(n)\,\!, takže celkem O(n+m)  ⁣ O(n+m)\,\!.

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 ⟨0,1⟩  ⁣\langle 0,1\rangle\,\! (a obecně tedy jakékoliv klíče). Má dané α  ⁣ \alpha\,\! (počet přihrádek v poměru k n  ⁣ n\,\!), rozhazuje do k=αn  ⁣ k=\alpha n\,\! přihrádek a ty pak třídí haldou.

Nejhorší možný čas je O(nlog⁡n)  ⁣ O(n\log n)\,\!, 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 O(n)  ⁣ O(n)\,\! -- pravděpodobnost velikostí množin se řídí binomickým rozdělením s parametrem 1/k  ⁣ 1/k\,\!, střední hodnota pak je: :E(∑i=1k(1+Xilog⁡Xi))≤E(∑i=1k(1+Xi2))=k+k(n(n−1)k2+nk)=O(n)  ⁣\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)\,\!

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:

  1. Rozhodí slova do množin Li  ⁣ L_i\,\! podle jejich délky.

  2. Vytvoří dvojice pozice-písmeno

    ParseError: KaTeX parse error: Undefined control sequence: \[ at position 10: \{(j,a_i\̲[̲j])\}\,\!

    , 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.

  3. Dvojice rozstrká do množin Si  ⁣ S_i\,\! pro každou pozici ii a odstraní duplicity.

Pak v hlavním cyklu postupuje od největší možné délky a pro každé i  ⁣ i\,\! pracuju jen s množinou slov délky ≥i\geq i:

  1. Podle i  ⁣ i\,\!-tého písmena rozhodím všechna aktuálně tříděná slova do množin Tx  ⁣ T_x\,\!.

  2. Potom podle množiny Si  ⁣ S_i\,\! vyberu všechna neprázdná Tx  ⁣ T_x\,\! a sliju je za sebe.

  3. 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 Li  ⁣ L_i\,\! a zařazení slov do Li  ⁣ L_i\,\! vyžadují čas O(L)  ⁣ O(L)\,\!, kde L  ⁣ L\,\! je součet délek všech řetězců. Vytvoření seznamu dvojic a jeho třídění vyžaduje také O(L)  ⁣ O(L)\,\!. Založení Si  ⁣ S_i\,\! a přeházení dvojic do nich také O(L)  ⁣ O(L)\,\!. Inicializace Tx  ⁣ T_x\,\! je O(∣Σ∣)  ⁣ O(|\Sigma|)\,\!, kde ∣Σ∣  ⁣ |\Sigma|\,\! je velikost abecedy. V hlavním cyklu v každém kroku potřebuji dvakrát čas O(li)  ⁣ O(l_i)\,\! (součet délek slov dlouhých i  ⁣i\,\! nebo víc). Celkem tedy O(L+∣Σ∣)  ⁣ O(L+|\Sigma|)\,\!.

Pořadové statistiky (hledání mediánu)

Vstupem je (neuspořádáná) posloupnost n  ⁣ n\,\! (navzájem různých) čísel. Výstup je ⌊n2⌋  ⁣ \lfloor\frac{n}{2}\rfloor\,\!-té, nebo obecně kk-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 3n  ⁣ 3n\,\! porovnání a že dolní odhad počtu porovnání je 2n  ⁣ 2n\,\!.

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ě k  ⁣ k\,\!-té nejmenší číslo:

  1. Vybrat pivota a rozdělit posloupnost pomocí n−1  ⁣ n-1\,\! porovnání na 3 oddíly: čísla menší než pivot (a  ⁣ a\,\! prvků), pivota samotného a čísla větší než pivot (n−a−1  ⁣ n-a-1\,\! prvků).

    1. Pokud je a+1<k  ⁣ a + 1 <k\,\!, hledám rekurzivně k−a+1  ⁣ k-a+1\,\!-tý prvek v n−a−1  ⁣ n-a-1\,\! prvcích

    2. Pokud je a+1=k  ⁣ a + 1 = k\,\!, vracím pivot

    3. Pokud je a+1>k  ⁣ a + 1 > k\,\!, hledám rekurzivně k  ⁣ k\,\!-tý prvek v a  ⁣ a\,\! prvcích

Rekurzivní vzorec T(n)=T(n−1)+(n−1)  ⁣ T(n) = T(n-1) + (n-1)\,\! v nejhorším případě, což dává Θ(n2)  ⁣ \Theta(n^2)\,\!. Očekávaný čas odhadneme na 4n  ⁣ 4n\,\! a dokážeme indukcí podle nn z rekurzivního vzorce T(n,i)=n+1n(∑k=1i−1T(n−k,i−k)+∑k=i+1nT(k,i))  ⁣ 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)\,\!.

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:

  1. Rozdělit posloupnost na pětice (poslední může být neúplná, mějme threshold např. n=100  ⁣ n=100\,\!, pod kterým množinu přímo třídíme)

  2. V každé pětici najít medián

  3. Rekurzivně najít medián těchto mediánů

  4. Použít ho jako pivot pro dělení celé posloupnosti, protože je větší než alespoň 3 prvky z alespoň 1/2  ⁣ 1/2\,\! pětic (až na zakrouhlení), je větší než alespoň 1/2⋅3/5=3/10  ⁣ 1/2 \cdot 3/5 = 3/10\,\! prvků (a také menší než alespoň 3/10  ⁣ 3/10\,\! prvků)

  5. Z toho mám vždy zaručeno, že zahodím alespoň 3/10  ⁣ 3/10\,\! prvků pro následující krok.

Vzorec potom vychází: T(n)=c⋅n5+T(n5)+(n−1)+T(710n)  ⁣ T(n) = c\cdot\frac{n}{5} + T(\frac{n}{5}) + (n-1) + T(\frac{7}{10}n)\,\! a podle Master Theoremu nebo substituční metodou se dá <Státnice%20-%20Metody%20tvorby%20algoritmů#Analýza%20složitosti%20algoritmů%20rozděl%20a%20panuj> jako T(n)=Θ(n)  ⁣ T(n) = \Theta(n)\,\!.

{{Statnice I3}}