Třídění ve vnitřní a vnější paměti (8×🎓)

{{Sources|

Založeno na <Státnice_-_Třídění> (pochází z poznámek k <Datové%20struktury%20I>, vnější třídění z <OZD%20I>)

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

{{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í

Soubor:Quicksort.gif

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ů%20I2#Rozděl%20a%20panuj>.

Implementace v Haskellu: qsort [] = []

qsort (pivot:tail) = qsort (filter (< pivot) tail) ++

[pivot] ++ qsort (filter (>= pivot) tail)

Složitost

nejhorší složitost - pivot špatně: T(n)=T(n-1)+Ө(n)=Ө(n²)

průměr složitost - pivot náhodně: O(n log n)

nejlepší složitost - pivot medián: T(n)=2T(n/2)+O(n) ⇒ a=2 b=2 d=1 ; 2=2¹  ⇒ Ө(n log n)

O(n) paměti

☀ pro kazdy pevne zadratovany algoritmus volby pivota existuje nejaky vstup, pro ktery alg. bezi v O(n²)

☀ zatimco pri nahodne volbe pivota/hledani medianu je čas horší (multipl.konstanta) než MERGESORT / HEAPSORT pro vsechny vstupy (nahodna volba i hledani medianu chce cas), takže se typicky bere median ze 3-5 pevne danych prvku

☀ pri zohledneni multiplikativni konstanty jde o nejrychlejsi znamy alg. pro trideni zalozeny na vzajemnem porovnavani prvku

Heapsort

nasypeme prvky do max-haldy a pak je po jednom odebirame O(n log n) Soubor:Mergesort.png

'''(Adaptabilní) '''Mergesort

• projdi posloupnost a rostoucí úseky hazej do fronty - pak je slejvej dokud nemáš jenom 1 úsek

☀ T(n) = 2T(n/2) + Θ(n)  ⇒ Θ(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. Soubor:Insert%20sort.png

Jednoduchá (sekvenční) 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.

• BUBBLESORT -- iterativně prochází posloupností a prohazuje inverze

{{collapse|A-sort - aplikace (a,b)-stromů, vhodný pro částečně setříděné posloupnosti, jinak k ničemu |

Tento algoritmus je aplikací $(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$ -- počet inverzí v posloupnosti. Celk. potřebuju $O(n)$ pro načtení prvků, $O(n)$ pro všechna štěpení dohromady ze všech běhů A-INSERTu a na každé vložení $O(h)$ pro nalezení místa, kde $h$ je výška, kam se z FIRST dostanu, přeskočím tak $f_i\ge a^{h-2}$ vrcholů (menších než vkládaný) a $h\in O(\log f_i)$. Součet $f_i$ za $\forall i$ dává: :${\sum }_{i=1}^n\log f_i=n\log ({\prod }_{i=1}^n{f}_i{)}^{\frac{1}{n}}\le 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)$ stromy. Pro míru $F\le n\log n$ má složitost $O(n\log \log n)$, v urč. případech i rychlejší než Quicksort.

}}

Porovnání algoritmů

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

}}

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

lineární třídění, O(n+počet přihrádek) nemusí být rychlejší než klasické algoritmy pokud jim nedáme speciální vstup

Soubor:Bucket.png

BUCKETSORT

Třídí jen n přirozených čísel z intervalu <0, m> a to zavedením $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)$, rozházení prvků pak $O(n)$, takže celkem **O(n + m) **.

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.

:Algoritmus: RADIX-SORT(A, d) :1 for i ← 1 to d

:2 do use a Bucket sort to sort array A on digit i

COUNTINGSORT

1. projdeme pole a poznamenáme si četnosti prvků do pomocného pole, pak projdeme pomocné pole a vždy četnost zvýšíme o četnosti prvnku před ním

2. projdeme pomocné pole a podle pole četností (nyní indexy výst.pole) plníme do výstupního pole, vždy po vypsání prvku na výstup snížíme jeho četnost

☀ BUCKETSORT je generalizace COUNTINGSORTU (pokud má BS kyblicky velke 1 degeneruje na CS)

{{collapse|Příklad COUNTINGSORT| V příkladu ukážeme, jak setřídit čísel 1, 4, 2, 4, 1, 3, 1.

Pomocné pole (číslo - počet výskytů):

1 - 3x 2 - 1x

3 - 1x 4 - 2x

Přepočet na hranice prvku (číslo - index konce pole)

1 - 3 2 - 4

3 - 5 4 - 7

V prvním kroce máme umístit číslo 1. Protože víme, že číslo jedna má 3 výskyty, umístíme jej na 3. pozici a snížíme v pomocném poli počet zbývajících výskytů na 2.

[ ][ ][1][ ][ ][ ][ ]

Pomocné pole po prvním kroku 1 - 2

2 - 4 3 - 5

4 - 7

Další kroky probíhají analogicky, zde je uvedeno, jak se bude postupně plnit seřazené pole:
[ ][ ][1][ ][3][ ][ ]

[ ][1][1][ ][3][ ][ ] [ ][1][1][ ][3][ ][4]

[ ][1][1][2][3][ ][4] [ ][1][1][2][3][4][4]

[1][1][1][2][3][4][4] - seřazené pole a algoritmus končí }}

Třídění na vnější paměti

{{multiple image

|align = tright |direction = vertical|

image1 = 2waymerge2.png|

width1 = 335| caption1=2-cestný externí MERGESORT|

image2 = Extmerge.png|

width2 = 335| caption2=n-cestný externí MERGESORT

}} {{image|

image = 2waymerge.png| width = 335|

caption =2-cestný externí MERGESORT}}

2-cestný '''MERGESORT''' na vnější paměti

• průchod 0: Přečíst stránku setřídit, zapsat (jenom 1 stránka bufferu je použita)

• průchod 1, 2, ..., atd.: (3 stránky bufferu použijeme)

každý průchod čteme a zapisujeme každou stránku do souboru

N stránek v souboru ⇒ počet průchodů 1 + ⌈log₂ N⌉

Celková složitost je: 2N * (1 + ⌈log₂ N⌉)

n-cestný '''MERGESORT''' na vnější paměti

Mám soubor s N stránkami a B buffer stránek v RAM:

• průchod 0: použij B stránek, vytvoř ⌈*N */ B⌉ setříděných běhů pomocí QS nebo HS v paměti, každý má B stránek

• průchod 1, 2, ..., atd.: slij B - 1 běhů

#počet průchodů = 1 + ⌈log_B *N */ B⌉

celková složitost = 2N * #počet průchodů {{collapse|Příklad:|

máme 5 stránek v bufferu, budeme třídit soubor s 108 stránkami:

• průchod 0: = 22 setříděných běhů, každý má 5 stránek

:: (poslední vytvořený běh má jenom 3 stránky), každá stránka se setřídí v paměti (využijeme i outputovou stránku): 108/5=22

• průchod 1: = 6 setříděných běhů, každý má 20 stránek

:: ( 5 = 4 využitelné stránky na input + 1 na output, 22/4=6, poslední vytvořený běh má jenom 8 stránek)

• průchod 2: 2 setříděné běhy, 80 a 28 stránek

• průchod 3: setříděný soubor s 108 stránkami

}} {{zdroje|

* [http://www.itu.dk/people/pagh/DBT07/sorting.pdf%5D%3Cnowiki%3E</nowiki>

• Celkem pěkně popsané ve skriptech Pokorný, Žemlička k OZD (jsou dostupné na Studnici) str 38.

}}

''Dolní odhady pro usporádání (rozhodovací stromy).'' (🎓🎓)

Soubor:RozhodovaciStrom.png

{{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 třídění)

Pro každý třídící algoritmus, založený na porovnávání prvků, existuje vstupní posloupnost, pro kterou provede $\Omega (n\log n)$ porovnání.

Důkaz

Nakreslím si rozhodovací strom jako model algoritmu A -- 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.

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.

Aby byl algoritmus korektní, musí mít strom listy se všemi n! 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). A tedy #listů ≥ n! .

Označím výšku jako h, pak ma nejvýše 2ʰ listů (max.počet listů ⇒ jsou na posl.hladině, na i-té hladině je vrcholů ≤ 2ⁱ )

:: a tedy: 2ʰ ≥ #listů ≥ n! a tedy 2ʰ ≥ n!, a to zlogaritmujeme na: h ≥ log n!,

nyní nám stačí odhad faktoriálu: n!* ≥ n/2 ^n/2* ( MiniDk: n! = 123*... obsahuje alespoň n/2 činitelů větších než n/2 )

:: ten zlogaritmujeme: log n! *≥ *log(n/2)^n/2= (n/2) log(n/2) ⇒ h ≥ (n/2) log(n/2) ⇒ Ω(n log n ) :: ☀ pro šťouraly (n/2) log₂(n/2) $\stackrel{\text{log podıˊlu je rozdıˊl log}}{=}$ (n/2) (log₂ n - 1) $\stackrel{\text{platıˊ pro n ≥ 4}}{\ge }$ (n/2) (log₂ n / 2) = (n/4) log₂ n ⇒ h ≥ (n/4) log₂ n ⇒ Ω(n log n ) :: ☀ případně můžu použít Stirlingův vzorec n! ≈ $\sqrt{2\pi n}(\frac{n}{e}{)}^n$a z pak *h ≥ log n! *dostáváme Θ(n log n) :: ☀ algoritmy, ktoré "porušují" dolný odhad zložitosti jsou třeba BUCKETSORT

{{Statnice I2}}