Algoritmy v akcii
Algoritmy v akcii je bezplatná interaktívna simulácia zo StudyFi Lab. Beží priamo v prehliadači, bez registrácie a bez inštalácie.
Triedenie a vyhľadávanie krok za krokom
Pokusy
Bublinkové triedenie
Bublinkové triedenie porovnáva susedné prvky a vymení ich, keď sú v zlom poradí. Po každom prechode „prebuble“ najväčší prvok na koniec, takže sa nezoradená časť skracuje. Keď prechod nič nevymení, pole je zoradené. V najhoršom prípade potrebuje n(n−1)/2 porovnaní, teda O(n²).
Vyskúšaj: Zvoľ obrátené poradie a porovnaj počet porovnaní s n(n−1)/2. Potom skús takmer zoradené pole — skončí po pár prechodoch.
Triedenie vkladaním
Triedenie vkladaním funguje ako triedenie kariet v ruke: ľavá časť je už zoradená a každý ďalší prvok (key) posúvaš doľava, kým nenarazíš na menší. Väčšie prvky sa pritom posunú o miesto doprava. Na náhodných dátach je to O(n²), ale na takmer zoradených skoro O(n) — zoradené pole potrebuje len n−1 porovnaní.
Vyskúšaj: Spusti ho na takmer zoradenom poli a potom na obrátenom. Koľkokrát viac posunov potrebuje obrátené pole?
Triedenie zlučovaním
Triedenie zlučovaním rozdelí pole na polovice, každú zoradí rovnakým spôsobom (rekurziou) a potom dve zoradené polovice zlúči do jednej: vždy vezme menší z čelných prvkov. Polenie dá log₂ n úrovní a každá úroveň spracuje všetkých n prvkov, takže časová zložitosť je vždy O(n log n). Pri zhode berie prvok z ľavej polovice, preto je stabilné.
Vyskúšaj: Skús obrátené a potom takmer zoradené pole s rovnakou veľkosťou. Počet porovnaní sa zmení len málo — na poradí vstupu takmer nezáleží.
Rýchle triedenie
Rýchle triedenie zvolí pivot — tu posledný prvok úseku (Lomutovo delenie) — a preusporiada úsek tak, aby menšie prvky boli vľavo a ostatné vpravo. Pivot tým skončí na svojom konečnom mieste a obe časti sa zoradia rovnako. Priemerne je to O(n log n), ale keď pivot delí zle (napríklad pri už zoradenom alebo obrátenom poli), klesne na O(n²).
Vyskúšaj: Porovnaj náhodný vstup s obráteným. Pri obrátenom poli je pivot vždy najväčší alebo najmenší — sleduj, ako vyskočí počet porovnaní.
Lineárne vs. binárne vyhľadávanie
Lineárne vyhľadávanie prechádza prvky jeden po druhom, takže v najhoršom prípade potrebuje n krokov — O(n). Binárne vyhľadávanie funguje len na zoradenom poli: pozrie sa do stredu a podľa výsledku zahodí celú polovicu. Po každom kroku zostane najviac polovica, preto stačí najviac ⌈log₂(n+1)⌉ krokov — O(log n). Pre 40 prvkov je to 6 krokov namiesto 40.
Vyskúšaj: Nastav 40 prvkov a hľadaj poslednú hodnotu. Potom zvoľ číslo, ktoré v poli nie je — koľko krokov potrebuje každé vyhľadávanie, kým to zistí?
Preteky triediacich algoritmov
Všetky štyri algoritmy triedia rovnaký vstup a v každej dráhe sa za jeden krok urobí jedno porovnanie alebo jeden presun. Algoritmy O(n²) (bublinkové a vkladaním) rastú s veľkosťou poľa oveľa rýchlejšie než O(n log n) (zlučovaním a rýchle). Poradie však závisí aj od vstupu: na takmer zoradenom poli triedenie vkladaním často vyhrá.
Vyskúšaj: Spusti preteky na náhodnom poli so 40 prvkami, potom prepni na takmer zoradené. Zmení sa víťaz?
Časté otázky
Čo je Algoritmy v akcii?
Algoritmy v akcii je bezplatná interaktívna simulácia zo StudyFi Lab. Beží priamo v prehliadači, bez registrácie a bez inštalácie. Triedenie a vyhľadávanie krok za krokom
Je aplikácia Algoritmy v akcii zadarmo?
Áno. Aplikácia Algoritmy v akcii je úplne zadarmo. Funguje v prehliadači na počítači, tablete aj telefóne a nepotrebuješ k nej účet.
Čo môžem preskúmať v aplikácii Algoritmy v akcii?
Bublinkové triedenie, Triedenie vkladaním, Triedenie zlučovaním, Rýchle triedenie, Lineárne vs. binárne vyhľadávanie, Preteky triediacich algoritmov.
Čo ukazuje pokus „Bublinkové triedenie“?
Bublinkové triedenie porovnáva susedné prvky a vymení ich, keď sú v zlom poradí. Po každom prechode „prebuble“ najväčší prvok na koniec, takže sa nezoradená časť skracuje. Keď prechod nič nevymení, pole je zoradené. V najhoršom prípade potrebuje n(n−1)/2 porovnaní, teda O(n²).
Čo ukazuje pokus „Triedenie vkladaním“?
Triedenie vkladaním funguje ako triedenie kariet v ruke: ľavá časť je už zoradená a každý ďalší prvok (key) posúvaš doľava, kým nenarazíš na menší. Väčšie prvky sa pritom posunú o miesto doprava. Na náhodných dátach je to O(n²), ale na takmer zoradených skoro O(n) — zoradené pole potrebuje len n−1 porovnaní.
Učíš sa na test?
Nahraj svoje poznámky a StudyFi z nich urobí kartičky, testy a podcasty.