Algoritmy v akci
Algoritmy v akci je bezplatná interaktivní simulace ze StudyFi Lab. Běží přímo v prohlížeči, bez registrace a bez instalace.
Řazení a vyhledávání krok za krokem
Pokusy
Bublinkové řazení
Bublinkové řazení porovnává sousední prvky a prohodí je, když jsou ve špatném pořadí. Po každém průchodu „probublá“ největší prvek na konec, takže se neseřazená část zkracuje. Když průchod nic neprohodí, pole je seřazené. V nejhorším případě potřebuje n(n−1)/2 porovnání, tedy O(n²).
Vyzkoušej: Zvol obrácené pořadí a porovnej počet porovnání s n(n−1)/2. Pak zkus téměř seřazené pole — skončí po pár průchodech.
Řazení vkládáním
Řazení vkládáním funguje jako řazení karet v ruce: levá část je už seřazená a každý další prvek (key) posouváš doleva, dokud nenarazíš na menší. Větší prvky se při tom posunou o místo doprava. Na náhodných datech je to O(n²), ale na téměř seřazených skoro O(n) — seřazené pole potřebuje jen n−1 porovnání.
Vyzkoušej: Spusť ho na téměř seřazeném poli a pak na obráceném. Kolikrát víc posunů potřebuje obrácené pole?
Řazení slučováním
Řazení slučováním pole rozdělí na poloviny, každou seřadí stejným způsobem (rekurzí) a pak dvě seřazené poloviny slije do jedné: vždy vezme menší z čelních prvků. Půlení dá log₂ n úrovní a každá úroveň zpracuje všech n prvků, takže časová složitost je O(n log n) vždy. Při shodě bere prvek z levé poloviny, proto je stabilní.
Vyzkoušej: Zkus obrácené a pak téměř seřazené pole se stejnou velikostí. Počet porovnání se změní jen málo — na pořadí vstupu skoro nezáleží.
Rychlé řazení
Rychlé řazení zvolí pivot — tady poslední prvek úseku (Lomutovo dělení) — a přeskládá úsek tak, aby menší prvky byly vlevo a ostatní vpravo. Pivot tím skončí na svém konečném místě a obě části se seřadí stejně. Průměrně je to O(n log n), ale když pivot dělí špatně (třeba u už seřazeného nebo obráceného pole), klesne na O(n²).
Vyzkoušej: Porovnej náhodný vstup s obráceným. U obráceného pole je pivot vždy největší nebo nejmenší — sleduj, jak vyskočí počet porovnání.
Lineární vs. binární vyhledávání
Lineární vyhledávání prochází prvky jeden po druhém, takže v nejhorším případě potřebuje n kroků — O(n). Binární vyhledávání funguje jen na seřazeném poli: podívá se doprostřed a podle výsledku zahodí celou polovinu. Po každém kroku zbude nejvýš polovina, proto stačí nejvýš ⌈log₂(n+1)⌉ kroků — O(log n). Pro 40 prvků je to 6 kroků místo 40.
Vyzkoušej: Nastav 40 prvků a hledej poslední hodnotu. Pak zvol číslo, které v poli není — kolik kroků potřebuje každé vyhledávání, než to zjistí?
Závod řadicích algoritmů
Všechny čtyři algoritmy řadí stejný vstup a v každé dráze se za jeden krok udělá jedno porovnání nebo jeden přesun. Algoritmy O(n²) (bublinkové a vkládáním) rostou s velikostí pole mnohem rychleji než O(n log n) (slučováním a rychlé). Pořadí ale závisí i na vstupu: na téměř seřazeném poli řazení vkládáním často vyhraje.
Vyzkoušej: Spusť závod na náhodném poli se 40 prvky, pak přepni na téměř seřazené. Změní se vítěz?
Časté otázky
Co je Algoritmy v akci?
Algoritmy v akci je bezplatná interaktivní simulace ze StudyFi Lab. Běží přímo v prohlížeči, bez registrace a bez instalace. Řazení a vyhledávání krok za krokem
Je aplikace Algoritmy v akci zdarma?
Ano. Aplikace Algoritmy v akci je úplně zdarma. Funguje v prohlížeči na počítači, tabletu i telefonu a nepotřebuješ k ní účet.
Co můžu prozkoumat v aplikaci Algoritmy v akci?
Bublinkové řazení, Řazení vkládáním, Řazení slučováním, Rychlé řazení, Lineární vs. binární vyhledávání, Závod řadicích algoritmů.
Co ukazuje pokus „Bublinkové řazení“?
Bublinkové řazení porovnává sousední prvky a prohodí je, když jsou ve špatném pořadí. Po každém průchodu „probublá“ největší prvek na konec, takže se neseřazená část zkracuje. Když průchod nic neprohodí, pole je seřazené. V nejhorším případě potřebuje n(n−1)/2 porovnání, tedy O(n²).
Co ukazuje pokus „Řazení vkládáním“?
Řazení vkládáním funguje jako řazení karet v ruce: levá část je už seřazená a každý další prvek (key) posouváš doleva, dokud nenarazíš na menší. Větší prvky se při tom posunou o místo doprava. Na náhodných datech je to O(n²), ale na téměř seřazených skoro O(n) — seřazené pole potřebuje jen n−1 porovnání.
Učíš se na test?
Nahraj svoje zápisky a StudyFi z nich udělá kartičky, testy a podcasty.