https://www.512.cz/index.php?feed=atom&target=109.72.14.213&title=Speci%C3%A1ln%C3%AD%3AP%C5%99%C3%ADsp%C4%9Bvky%2F109.72.14.213 2026-10-22T05:04:29Z Z FAV wiki MediaWiki 1.17.0 https://www.512.cz/index.php?title=Algoritmy_%C5%99azen%C3%AD_O(N_logN) 2016-06-04T07:30:07Z

<p>109.72.14.213: /* Řazení haldou (heapsort) */</p> <hr /> <div>// přidat ukázky<br /> <br /> Společné pro všechny: Řadíme stromem.<br /> <br /> == Řazení haldou (heapsort) ==<br /> <br /> Na začátku je neseřazené pole. Postupně obnovujeme nad tímto polem haldu pro první dva, tři, čtyři atd. prvky, až<br /> máme na poli vytvořenu haldu. Následně zaměníme nejvyšší prvek (vyjmeme ho) s posledním a obnovíme<br /> vlastnost haldy na n−1 prvcích. Obnovení haldy je O(log n) a obnovujeme po každém výběru, tedy O(n log2n) <br /> To opakujeme až zbude jednoprvková halda a celé pole je seřazené. Nestabilní (složitost závisí na vstupních datech).<br /> <br /> V kostce: na poli uděláme haldu a max prvky vyměňujeme s posledními prvky haldy a haldu obnovujeme.<br /> <br /> Hezká vizualizace: http://varkor.com/mathematics/heapsort/?0,1,1,2,3,5,8,13,21,34,55,89,144,233<br /> <br /> == Shellovo řazení (shellsort) ==<br /> <br /> Posloupnost rozdělíme na podposloupnosti s krokem h (každý h-tý počínaje prvním, počínaje druhým až<br /> počínaje h − 1-ním), které nezávisle seradíme vkládáním (insertsortem). Následne snižujeme hodnotu h a<br /> provádíme totéž až do serazení s h = 1. Prvky daleko od své výsledné pozice se k ní dostanou v menším<br /> počtu kroků, než u obyčejného insertsortu.<br /> <br /> * Shell - počátecní h = polovina délky pole, snížení vydělením dvěma<br /> * Knuth - posloupnost 3i + 1, počáteční h = její prvek v nejbližší třetině délky pole<br /> <br /> Jednoduchý a efektivní algoritmus, složitá analýza, nestabilní.<br /> <br /> V kostce: rozdělení do stromu podle kroku (třeba na osminy), insertsort větví, a pak insertsort čtvrtin, polovin, konec<br /> <br /> Poměrně zajímavě udělaná ukázka z kartama: http://www.youtube.com/watch?v=QG8hs0wqmqk<br /> <br /> == Řazení dělením (splitsort, quicksort) ==<br /> <br /> Určíme prvek, jehož hodnota bude rozdělovat pole (pivot). Procházíme z obou stran pole a menší hodnoty<br /> vpravo prohazujeme s vetšími vlevo, až se oba průchody potkají. Na tuto pozici přesuneme pivot - vlevo jsou<br /> hodnoty menší, vpravo vetší. Totéž provedeme s částí pole vlevo od pivotu i vpravo od nej. Rekurze končí,<br /> je-li předán pouze jeden prvek k seřazení. Nejčasteji se pivot určuje jako krajní prvek pole (nezasahuje pak<br /> do procesu dělení). Lze použít zásobník místo rekurze. Snadno implementovatelné, nestabilní.<br /> <br /> V kostce: rozdělení do stromu podle pivotů (prvek velikostně cca uprostřed podstromu, ideálně medián, ale může být i náhodný), <br /> v každém podstromu vzájemně vyměníme větší a menší prvky než pivot.<br /> <br /> Výukové videjko: http://www.youtube.com/watch?v=y_G9BkAm6B8<br /> <br /> == Řazení slucováním (mergesort) ==<br /> <br /> Pole je rekurzivně rozdělováno na poloviny. Dojdeme až na úroveň dvojic prvku, které seřadíme (sloučíme).<br /> O úroven výše opět po dvojicích sloučíme (kopírujeme vždy menší prvek z obou polí a posuneme se za nej)<br /> a postupujeme až sloučíme obě poloviny původního pole. Je to nejčasteji používaná metoda a je stabilní.)<br /> <br /> V kostce: jako když mícháme karty - 2 balíčky a děláme [[Soubor:Mergesort.jpg]] <br /> ???????<br /> <br /> . Procházíme 2 podstromy a řadíme posunem <br /> 2 indexů, jeden v každém podstromu, a vždy zapíšeme větší prvek pod jedním z indexů, který posuneme<br /> <br /> Bezva video - http://www.youtube.com/watch?v=GCae1WNvnZM<br /> <br /> <br /> Nestabilní metody lze &quot;zestabilnit&quot; například zpřeházením dat na vstupu.<br /> <br /> Radix sort =???<br /> [[Kategorie:fav-kiv-bzinf]]</div>

109.72.14.213 https://www.512.cz/index.php?title=Doln%C3%AD_omezen%C3%AD_pro_porovn%C3%A1vac%C3%AD_%C5%99azen%C3%AD 2016-06-04T06:56:56Z

<p>109.72.14.213: Informace</p> <hr /> <div>Celkem HC otázka, asi nejtěžší z PPA, kvůli matematice, kterou my programátoři moc nemusíme (kdo říká, že to není pravda, tak lže sám sobě, nebo neumí programovat s tím, co je k dispozici a vše si musí do podrobna analyzovat)<br /> <br /> Zkoumejme dolni omezeni počtu porovnani T(n) pro porovnávaci algoritmy řazení.<br /> <br /> [[Soubor:Dolni-omezeni.jpg]]<br /> <br /> <br /> Předpokladejme, že všechny prvky posloupnosti a1, a2, ..., an jsou různé. Porovnavací řazeni můžeme znázornit rozhodovacim stromem. Ve vnitřních vrcholech jsou prvky, ktere algoritmus porovná a v listech je permutace všech prvků původni posloupnosti, ktera je seřazena.<br /> <br /> Přiklad rozhodovaciho stromu pro řazeni vkladanim tři prvků:<br /> Jakykoliv 100% správný algoritmus (brutální síla) musi vytvořit každou z n! permutací prvků původní posloupnosti a zjistit, která je seřazená. Každou z takových permutací umístíme do stromu, ve kterém je v kořenech naznačeno porovnání, kterým se k permutacím dostaneme.<br /> <br /> Nejhoršim připadem počtu porovnani vykonanych algoritmem řazeni je nejdelši cesta od kořene stromu k listu, je tedy rovna vyšce stromu T(n) = h . <br /> <br /> Nyní musíme najít dolní omezení všech rozhodovacích stromů. Nechť rozhodovaci strom o výšce h má l listů, potom l = 2h (binární strom má maximálně 2h listů). Současně listů musi byt alespoň tolik, kolik je permutaci, tedy n! = l. <br /> Potom n! = l = 2h a po logaritmování (zjištění délky cesty, každá vrstva x grafu má 2x možných cest (2x listů), takže číslo vrstvy a tedy i délka ke kořeni je funkce inverzní, tedy log2x)<br /> <br /> log2 (n!) = log2 2h = h log22 = h * 1 = h = počet porovnání, kterým se dostneme k permutaci<br /> <br /> Použitim aproximace (n/e)n = n! je<br /> <br /> log2(n!)=n * log2 (n/e) = log2 n- n* log2 e,<br /> <br /> čim dostavame dolni omezeni pro nejhorši připad Ω(n*log2 n). (n * konstanta = n)<br /> <br /> Protože pro řazeni haldou a slučovanim jsou shora omezeny časem vypočtu Ω(n*log2 n), jsou tato řazeni asymptoticky optimalni.<br /> <br /> <br /> '''JE TO ŠPATNĚ !!!!!!!!!!!!!!! V TEXTU NEJSOU VIDĚT INDEX h^2 viz.: [http://www.kiv.zcu.cz/~netrvalo/vyuka/ppa2-11/ekniha/online/HTML/54/default.htm]'''<br /> <br /> <br /> [[Kategorie:fav-kiv-bzinf]]</div>

109.72.14.213