Sorting and Searching algos

Programovani 2 Matematici, teoreticke cviceni
10.03.2026 út


1. Searching algos

1.2 Proč vlastně chceme řadit (i) pole?
(Dat struct ... způsob organizace dat; analogie s dílnou; daný typ organizace přináší své výhody a nevýhody; "neexistuje dobrý DS pro všechny případy")

3. Sorting algos
3.2 Proč řadit?

3.4 visualgo: https://visualgo.net/en
- bacha na různé implementace daného algoritmu: idea vs. pseudokód vs. implementace; fine-tunning features

3.6 trackování algoritmů: insert/select/bubble sort

3.8 insert/select/bubble sort: jak vypadá: 
a] nejlepsi 
b] nejhorsi 
vstup vzhledem k poctu operaci/casove slozitosti a jake casove slozitosti to jsou odvození z pseudokódu

3.10
bubleSort: 
- mějme reverzně seřazenou vstupní posloupnost,
jak rychle se a] nejvetsi prvek (když je první) a b] nejmensi (když je posledni) "dostane na své místo"? 
- buduje/obsahuje take serazenou a neserezenou posloupnost?
- je nutné mít swapp? co způsobuje proměnná swap a co když ji nepoužijeme? bude algoritmus stále fungovat?

4. Mergesort
- mergesortem setridte posloupnost: ...
- slevání
- obrazek wiki: https://en.wikipedia.org/wiki/Merge_sort
resp.: https://upload.wikimedia.org/wikipedia/commons/thumb/e/e6/Merge_sort_algorithm_diagram.svg/960px-Merge_sort_algorithm_diagram.svg.png
- odvození složitosti mergesortu dle hloubky stromu a slevání
- rozšiřující příklad: navrhněte úpravu mergesortu inplace a jako má časovou složitost?

5. Opakovani dukazu dolni sloz radicich algos zaloz na porovnani

7. Counting a bucketsort 

Zajímavosti
9. 15 Sorting Algorithms in 6 Minutes (sound) - jak různý princip řešení\algoritmu (stejné úlohy řazení) reprezentovaný zvuky i značně jinak zní 
https://www.youtube.com/watch?v=kPRA0W1kECg

10. Quick sort with Hungarian, folk dance 
https://www.youtube.com/watch?v=3San3uKKHgg



11.1 kolik maximalne prvku ma binarni strom v k-vrstve (vrstvy stromu vs hloubka stromu)
11.3 kolik maximalne prvku ma binarni strom o k-vrstvach
s_n= a_1 * ((1-q^n)/(1-q))

*Počet vrcholů na úrovni k:
    Na úrovni k je maximálně 2^(k-1) vrcholů (každý vrchol předchozí úrovně může mít nejvýše dva potomky).

*Celkový maximální počet vrcholů pro výšku h:
    Součet maximálních počtů na všech úrovních 1..h: N_max(h) = sum_{k=1}^{h} 2^{k-1} = 2^0 + 2^1 + ... + 2^{h-1}.

*Vyhodnocení součtu geometrické posloupnosti:
    Součet prvních h členů geometrické posloupnosti se společným poměrem 2 je: N_max(h) = (2^h - 1) / (2 - 1) = 2^h - 1.


11.5 dokazte nebo vyvratte: mejme plne zaplneny binarni strom o k vrstvach; obsahuje k vrstva vice hodnot nezli cely strom bez k-te vrstvy?
11.6 Jaká je výška/hloubka plného binárního stromu obsahujících n prvků? 
11.7 Jaká je minimální a maximální výška/hloubka binárního stromu obsahujících n prvků? 





Programování

Implementování základních algoritmů - binární vyhledávání a řazení
("aspoň jednou za život", hraní si s poli a +- jedničkové problémy)


1.1 Implementujte funkci binárního vyhledávání binarySearch(list, x)
(co funkce vrací, co vrací v případě nalezeného prvku a co v případě nenalezeného prvku?)

1.2 Pro funkci binárního vyhledávání diskutujme a navrhněme sérii testů/testovacích dat, které prověří funkčnost vaší implementace
(jaké případy chování testujeme? např: řadné vstupy, krajní meze, neplatné vstupy)
(assert: např. https://realpython.com/python-assert-statement/)
(lehká zmínka o automatickém testování, typy testů, konkrétně unit testy a knihovna unittest)


2. Implementujte funkci selectSort(list)