IB111 – cvičení 7
POKROČILEJŠÍ ÚLOHY NAD SEZNAMY
Miroslav Kadlec
Obsah
▪ https://www.fi.muni.cz/IB111/sbirka/07-
seznamy_algoritmy.html
▪ Pascalův trojuhelník
▪ Varianta přes kombinační čísla
▪ Varianta postupným počítáním řádků
▪ Řadicí algoritmy
▪ Bubble sort
▪ Select sort
▪ Insert sort
Pascalův trojuhelní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
▪ Pascalův trojúhelník s pomocí komb. Čísel
▪ Definovat funkci pro výpočet
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?
● Průchod opakuju
● Existuje nějaká část seznamu, kterou nemusím
opakovaně procházet, protože už je seřazená?
Ř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
● Myšlenka: 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/videos