Obsah
27e - Řazení - algoritmy 1
Selection sort:
- řazení na princípe výberu
- nestabilná
- kvadratická zložitosť
Bubble sort:
- princíp rovnaký ako v selection sort, ale metóda výberu extrému je iná
- porovnáva prvky vedľa seba
- modifikácie:
- indikátor ukončenia
- index prvej výmeny
- shaker sort (z oboch strán striedavo)
- shuttle sort - keď prišlo k výmene tak ten prvok posúval až kým sa nedostal na svoje miesto a potom pokračoval
- najmenej efektívna metóda
- najrýchlejšia metóda pre řazení už zoradeného poľa
- najhorší prípad - najmenší prvok úplne na konci (môže sa presunúť vždy len o jedno miesto)
- stabilná
- prirodzená
- kvadratická časová zložitosť
Heap sort:
- štruktúra stromového typu
- platí, že medzi otcovským uzlom a všetkými synovskými uzlami platí rovnaká relácia usporiadania
- Rekonštrukcia hromady:
- po porušení pravidla hromady v niektorom uzle (najvýznamnejšie je pri porušení v koreni)
- Sift (preosiatie)
- logaritmická zložitosť
- postupne „utriasanie“, začínajúc najspodnejším a najpravejším podstromom (koreň a aspoň jeden syn)
- nestabilná
- nechová sa prirodzene
- linearitmická zložitosť
- přidávám ještě toto video: http://www.youtube.com/watch?v=GnnmnQUudsU - je to sice španělsky, ale je to tam je pěkně pomalu řešeno
Insertion sort:
- pole je rozdelené na 2 časti - už zoradená a ešte nezoradená
- nájdem kam ďalší prvok patrí, posuniem prvky, ktoré sú napravo od neho, vložím prvok
- stabilita závisí na spôsobe vyhľadávania miesta pre vkladaný prvok
- kvadratická zložitosť
Bubble - insert sort:
- kombinuje vyhľadanie miesta pre vkladanie a posun segmentu poľa v jednom cykle porovnávaním dvojíc prvkov
- zarážka
- stabilná
- prirodzená
- pracuje in situ
- kvadratická zložitosť