🔍 Vyhledávání a třídění

Hledání ve slovníku

O čem to je

Hledáš v papírovém slovníku slovo „mrak“. Nečteš ho od první stránky. Otevřeš ho někde uprostřed, uvidíš „lampa“ a víš, že „mrak“ je dál. Zahodíš celou první půlku. Za pár kroků jsi u cíle.

Funguje to jen proto, že slova jsou seřazená. Hledání a třídění patří k nejčastějším úlohám v programování: vyhledávač, e-shop, telefonní kontakty. A u velkých dat rozhoduje, jestli program odpoví za vteřinu, nebo za hodinu.

Nové pojmy

Lineární (sekvenční) vyhledáváníProcházíš prvky jeden po druhém od začátku, dokud hledaný nenajdeš. Funguje vždy, i na neseřazených datech.Hledáš kamaráda v řadě lidí tak, že se díváš na jednoho po druhém.

Binární vyhledávání (půlení intervalu)Funguje jen na seřazených datech. Podíváš se doprostřed. Je-li hledaná hodnota menší, pokračuješ v levé půlce, je-li větší, v pravé. Každý krok zmenší úsek na polovinu.Hra „myslím si číslo 1 až 100“, kde hádáš vždy polovinu.

Časová složitost a zápis OJak roste počet kroků algoritmu, když roste počet prvků n. Zápis O(…) (velké O) popisuje tento růst v nejhorším případě, bez konstant.O(n): dvakrát víc prvků = zhruba dvakrát víc kroků.

Logaritmus log₂ nKolikrát musíš n dělit dvěma, než dojdeš k 1. Roste velmi pomalu.log₂ 1 024 = 10, protože 2¹⁰ = 1 024.

Binární vyhledávání krok za krokem

Hledáme 23 v seřazeném seznamu [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] (indexy 0 až 9).

Krok	Úsek (indexy)	Prostředek `(od + do) // 2`	Hodnota	Rozhodnutí
1	0–9	4	16	23 > 16 → vpravo
2	5–9	7	56	23 < 56 → vlevo
3	5–6	5	23	nalezeno

Stačily 3 porovnání. Lineární vyhledávání by potřebovalo 6.

Porovnání

Podívej se na délky pruhů. Binární vyhledávání v milionu prvků potřebuje jen 20 porovnání, lineární až milion.

Kolik porovnání nejvýš potřebuje binární vyhledávání v seřazeném seznamu 1 000 prvků?

Úsek se půlí: 1 000 → 500 → 250 → 125 → 63 → 32 → 16 → 8 → 4 → 2 → 1. Je to 10 kroků, protože 2¹⁰ = 1 024 ≥ 1 000. Složitost O(log n).

Máš neseřazený seznam a hledáš v něm jednou jediné číslo. Které vyhledávání použiješ?

Lineární, O(n). Binární by vyžadovalo nejdřív seřadit, a třídění stojí víc než jedno lineární hledání.

✗Binárním vyhledáváním najdu prvek v jakémkoli seznamu.

✓Binární vyhledávání funguje jen na seřazeném seznamu.

Rozhodnutí „vlevo, nebo vpravo“ dává smysl jen tehdy, když vlevo jsou menší a vpravo větší hodnoty.

Lineární vyhledávání prochází prvky postupně, O(n), a funguje vždy. Binární půlí seřazený úsek, O(log n), a je u velkých dat mnohem rychlejší. Zápis O popisuje, jak roste počet kroků s n.

Třídicí algoritmy

O čem to je

Učitel má na stole hromádku písemek a chce je seřadit podle abecedy. Jeden bere vždy tu „nejmenší“ a dává ji navrch. Jiný bere jednu po druhé a zasouvá ji na správné místo. Oba dojdou k cíli, ale ne stejně rychle.

Třídicích algoritmů je mnoho. Ve škole se učí jednoduché, na kterých pochopíš princip a složitost, a jeden rychlý, který používají skutečné programy.

Nové pojmy

Třídění (řazení)Uspořádání prvků podle velikosti, obvykle vzestupně (od nejmenšího).[5, 2, 8, 1] → [1, 2, 5, 8]

Časová složitost O(…)Jak roste počet kroků, když roste počet prvků n, v nejhorším případě. O(n²): dvakrát víc prvků = zhruba čtyřikrát víc kroků.Pro n = 1 000 je n² milion kroků.

Výměna (swap)Prohození dvou prvků. V Pythonu jedním řádkem a[i], a[j] = a[j], a[i].[5, 2] → [2, 5]

Rozděl a panujZpůsob řešení: úlohu rozdělíš na menší části, ty vyřešíš (často rekurzí) a výsledky spojíš.Merge sort rozdělí seznam na půlky, seřadí je a slije.

Přehled algoritmů

Algoritmus	Princip	Složitost
bublinkové (bubble sort)	porovnává sousedy a prohazuje je; největší „probublá“ na konec	O(n²)
přímý výběr (selection sort)	najde nejmenší ze zbytku a dá ho na začátek zbytku	O(n²)
přímé vkládání (insertion sort)	bere prvky postupně a zasouvá je do už seřazené části	O(n²)
slučováním (merge sort)	rozdělí na půlky, seřadí je a slije	O(n log n)
rychlé (quicksort)	rozdělí podle pivota na menší a větší	průměrně O(n log n), nejhůř O(n²)

Bublinkové třídění ručně

for i in range(len(a) - 1):
for j in range(len(a) - 1 - i):
if a[j] > a[j + 1]:
a[j], a[j + 1] = a[j + 1], a[j]

Start: [5, 2, 8, 1].

1. průchod: 5 > 2 prohoď, 5 < 8 nech, 8 > 1 prohoď → [2, 5, 1, 8]. Osmička je na konci.

2. průchod: 2 < 5 nech, 5 > 1 prohoď → [2, 1, 5, 8].

3. průchod: 2 > 1 prohoď → [1, 2, 5, 8]. Hotovo.

Seřaď přímým výběrem [5, 2, 8, 1]. Napiš stav po každém průchodu.

1. nejmenší je 1, prohoď s 5 → [1, 2, 8, 5]. 2. nejmenší ze zbytku [2, 8, 5] je 2, už je na místě → [1, 2, 8, 5]. 3. nejmenší z [8, 5] je 5, prohoď → [1, 2, 5, 8].

Bublinkové třídění seřadí 1 000 prvků zhruba za 1 s. Jak dlouho bude třídit 10 000 prvků?

O(n²): desetkrát víc prvků = zhruba stokrát víc kroků, tedy asi 100 s. Algoritmus O(n log n) by se zpomalil jen asi 13krát.

V praxi nepíšeš třídění sám. Python má sorted(a) a a.sort(), které používají algoritmus Timsort se složitostí O(n log n).

✗Když je n² u bublinkového třídění „jen“ o něco víc než n log n, na rychlosti nezáleží.

✓Pro n = 1 000 000 je n² bilion kroků, n log₂ n jen asi 20 milionů.

Rozdíl roste s velikostí dat. U malých seznamů ho nepoznáš, u velkých rozhoduje o minutách a dnech.

Jednoduché třídění (bublinkové, výběrem, vkládáním) má složitost O(n²). Merge sort a quicksort využívají „rozděl a panuj“ a mají O(n log n). V Pythonu třiď přes sorted().

🪆Rekurze