Obsah
27f - Řazení - algoritmy 2
Vkladanie s binárnym vyhľadávaním:
- hľadanie miesta na vloženie pomocou Dijkstrovej varianty ⇒ urýchlenie porovnávania (ale nie presunu)
- stabilná
- prirodzená
- in situ
- kvadratická zložitosť
Quick Sort - řazení rozdeľovaním:
- delenie položiek na 2 podmnožiny, 1. s menšími kľúčami ako istá hodnota, 2. s väčšími kľúčami
- mechanizmus rozdelenia (partition):
- máme medián (číslo, od ktorého je polovica čísel menšia a polovica väčšia)
- pôjdeme zľava a hľadáme prvé číslo, ktoré je väčšie ako medián, keď ho nájdeme, zastavíme
- potom pôjdeme sprava a hľadáme prvé číslo, ktoré je menšie ako medián a vymením ho s číslom z predchádzajúceho kroku
- pseudomedián:
- nahradenie mediánu ľubovoľnou hodnotou z danej množiny čísel
- najvhodnejším je číslo zo stredu intervalu
- použitie zarážky
- nerekurzívny zápis:
- využíva zásobník - veľkosť zásobníku log2(N)
- pole sa rozdelí na 2 segmenty, menší ďalej delím, hraničné indexy väčšieho dám na zásobník
- 2 cykly:
- vnútorný cyklus - opakovane delí segment poľa a uchováva hraničné indexy druhého segmentu dám na zásobník, keď už nie je čo deliť, cyklus sa ukončí
- vonkajší cyklus - zoberie zo zásobníku hraničné body ďalšieho segmentu a vstúpi do vnútorného cyklu, ukončí sa, keď je zásobník prázdny a už nie je žiadny ďalší segment na delenie
- nestabilná
- nechová sa prirodzene
- patrí medzi najrýchlejšie algoritmy pre řazení
- časová zložitosť je linearitmická
- doporučuju toto: http://www.youtube.com/watch?v=Fju_NstEy3M
Shell-sort:
- treba vedieť vysvetliť, nie napísať kód
- základom je bublinový priechod
- máme pole, rozdelíme ho na niekoľko podpolí, ktoré budú tvoriť prvky vzdialené o istý krok
- každým podpoľom urobím bublinový priechod
- opakujem to, ale s menším krokom (končíme s krokom 1)
- veľkosť kroku - najprv N/2, potom N/4, atď.
- je pomalší ako Quicksort, ale nepotrebuje ani rekurziu ani zásobník
- rýchlejší ako Heap sort a nepotrebuje hromadu
- veľmi rýchly algoritmus
- nestabilná
- pracuje in situ
