IB111 – cv. 7 Pokročilejší algoritmy nad seznamy
Miroslav Kadlec

Obsah
●

Opakování
●

Indexování, kopie Varianta přes kombinační čísla Varianta postupným počítáním řádků Bubble sort Select sort ?? Insert sort

●

Pascalův trojuhelník
● ●

●

Řadicí algoritmy
● ● ●

Pascalův trojúhelník
●

Průprava – Trojúhelník
●

Tím si vlastně napíšeme strukturu, pak už jen doplníme logiku výpočtu konkrétního prvku Definovat funkci pro výpočet
– –

●

Pascalův trojúhelník s pomocí komb. čísel
●

Kombinačního čísla (jaké parametry?) Faktoriálu (už známe)

●

Varianta postupným počítáním řádků
●

Hlavní úskalí může být v indexování – počítáme prvky delšího seznamu, než máme za podklad

Řadicí algoritmy
●

Vstup: seznam Výstup: seřazený seznam Různé algoritmy mají různé výpočetní složitosti Bubble sort
●

●

●

●

Myšlenka: Projdu celý seznam a u každého prvku se podívám, jestli není větší, než prvek za ním.
–

Když jo, tak je prohodím
●

Co můžu říct o prvním a posledním prvku po průchodu? Existuje nějaká část seznamu, kterou nemusím opakovaně procházet, protože už je seřazená?

●

Průchod opakuju
●

Řadicí algoritmy
●

Select sort
●

Myšlenka: najdu nejmenší prvek a vyměním ho s prvkem na indexu 0 Opakuju pro druhý nejmenší prvek atd.
–

●

Po i-tém kole výpočtu mám na začátku seřazenou část o délce i (v ní je i nejmenších prvků) a za ní neseřazenou část

●

Insert sort
● ●

opět si vytvářím seřazený podseznam v levé části Změna – v i-tém kole zpracovávám prvek na indexu i (tj hned za seřazenou částí) a "protlačím" ho tak hluboko do seřazené části, jak je potřeba

Řadicí algoritmy
● ●

Ukázka principu řadicích algoritmů na videu https://www.youtube.com/user/AlgoRythmics/vi deos