O(n) · visualised
Vizualizér algoritmů a datových struktur
Sleduj klasické algoritmy a datové struktury krok po kroku. Vyber si jeden a začni.
Řadicí algoritmy
Sleduj, jak se pole řadí krok za krokem.
Bubble sortBubble sort opakovaně prohazuje sousední prvky ve špatném pořadí — největší vždy „probublá“ na konec.Insertion sortInsertion sort staví seřazené pole po jednom prvku — každý nový prvek zasune na správné místo mezi předchozí.Selection sortSelection sort opakovaně najde nejmenší zbývající prvek a přesune ho dopředu.Merge sortMerge sort rozdělí pole na poloviny, každou seřadí a pak obě seřazené poloviny slije dohromady.Quick sortQuick sort zvolí pivot, rozdělí pole kolem něj a pak seřadí obě strany.Heap sortHeap sort postaví max-haldu a pak opakovaně přesouvá největší prvek na konec.Shell sortShell sort je insertion sort, který nejdřív porovnává vzdálené prvky a mezeru postupně zmenšuje.Cocktail sortCocktail sort je bubble sort, který prochází oběma směry — největší probublá nahoru, nejmenší dolů.Comb sortComb sort je bubble sort, který porovnává prvky vzdálené o velkou mezeru a tu postupně zmenšuje k 1.Gnome sortGnome sort jde vpřed, dokud je pořadí správné, a při chybě prohodí a couvne.Odd-even sortOdd-even sort porovnává pevné dvojice — nejdřív liché, pak sudé — a opakuje, dokud nějaká není ve špatném pořadí.Pancake sortPancake sort řadí jen otáčením předpony: největší hodnotu dostane dopředu a pak ji otočí na její místo.Cycle sortCycle sort uloží každou hodnotu rovnou na její konečné místo a udělá teoreticky nejmenší počet zápisů.Stooge sortStooge sort je rekurzivní kuriozita: seřaď první 2/3, pak poslední 2/3 a pak zase první 2/3.Counting sortCounting sort prvky neporovnává — spočítá, kolik je kterých hodnot, a pak je zapíše zpět v pořadí. Lineární čas, když je rozsah hodnot malý.Radix sortRadix sort řadí čísla po jedné číslici, od nejnižší, pomocí stabilního přihrádkového průchodu pro každou číslici. Žádná porovnání nejsou potřeba.
Vyhledávání
Najdi hodnotu v poli.
Linear searchLineární vyhledávání prochází pole zleva doprava a porovnává každý prvek s hledanou hodnotou, dokud ji nenajde.Binary searchBinární vyhledávání opakovaně půlí seřazené pole a porovnává prostřední prvek s hledanou hodnotou.Jump searchJump search prochází seřazené pole po pevných blocích a pak lineárně projde blok, který může obsahovat hledanou hodnotu.Interpolation searchInterpolation search odhadne, kde hledaná hodnota nejspíš je, interpolací mezi krajními hodnotami — rychlé na rovnoměrných datech.Exponential searchExponential search zdvojnásobuje index, dokud nepřekročí hledanou hodnotu, a pak binárně prohledá ohraničený rozsah.Ternary searchTernary search dělí seřazené pole na třetiny — v každém kroku zkouší dva body a zahodí dvě třetiny zbytku.Fibonacci searchFibonacci search zužuje seřazené pole pomocí Fibonacciho čísel — jen sčítání a odčítání, žádné dělení.
Vyhledávání v řetězci
Najdi vzor uvnitř textu.
Vyhledávání KMPKnuth-Morris-Pratt najde každý výskyt vzoru v textu, aniž by kdy znovu kontroloval znak — při neshodě posune vzor pomocí předpočítané tabulky selhání.Vyhledávání Rabin-KarpRabin-Karp porovnává klouzavý hash každého okna textu s hashem vzoru a znaky kontroluje, jen když se hashe shodují — díky O(1) aktualizaci hashe je v průměru rychlý.Vyhledávání Boyer-MooreBoyer-Moore porovnává vzor zprava a při neshodě skočí dopředu tak, že zarovná problematický znak textu s jeho posledním výskytem ve vzoru — často přeskočí mnoho pozic, díky čemuž je v praxi rychlý.
Výběr
Najdi k-tou nejmenší hodnotu.
Datové struktury
Jak se data ukládají, přidávají a odebírají.
Zásobník (LIFO)Zásobník je struktura last-in, first-out (LIFO): push přidá na vršek, pop odebere vršek.Fronta (FIFO)Fronta je struktura first-in, first-out (FIFO): enqueue přidá dozadu, dequeue odebere zepředu.DequeDeque (oboustranná fronta) umožňuje přidávat i odebírat z obou konců.Binary search treeBinární vyhledávací strom drží hodnoty uspořádané: vše vlevo od uzlu je menší, vše vpravo větší — takže hledání jde jednou cestou dolů.AVL stromAVL strom je binární vyhledávací strom, který se po každém vložení sám vyvažuje rotacemi, takže nikdy nezdegeneruje na pomalý řetěz — výška zůstává logaritmická.Binary heap (min)Binární min-halda drží nejmenší hodnotu v kořeni; insert probublá hodnotu nahoru a extract-min nechá nový kořen klesnout dolů.Linked listSpojový seznam řetězí uzly ukazateli — přidání na začátek O(1), ale cokoli najít znamená projít řetěz.Hash tableHash tabulka mapuje každou hodnotu do kbelíku hashovací funkcí — v průměru O(1) vyhledání; kolize sdílejí kbelík jako řetěz.Trie (prefixový strom)Trie ukládá slova podél sdílených cest od kořene, jeden znak na hranu. Slova se stejným prefixem sdílejí jeho uzly, takže vyhledání stojí jen délku slova.Union-Find (DSU)Struktura disjunktních množin sleduje rozdělení prvků do skupin, odpovídá "jsou tyhle dva ve stejné množině?" a slučuje množiny — v téměř konstantním čase na operaci.
Stromové algoritmy
Projdi strom uzel po uzlu.
In-order traversalIn-order průchod navštíví levý podstrom, pak uzel, pak pravý podstrom — u BST dá seřazené pořadí.Pre-order traversalPre-order průchod navštíví nejdřív uzel, pak levý a pravý podstrom — hodí se ke kopírování či serializaci stromu.Post-order traversalPost-order průchod navštíví nejdřív oba podstromy, pak uzel — hodí se k mazání nebo vyhodnocení stromu.Level-order traversalLevel-order průchod navštíví strom shora dolů, zleva doprava — je to prohledávání do šířky na stromě, s frontou.
Grafové algoritmy
Procházení uzlů a hran.
BFSProhledávání do šířky prochází graf po úrovních pomocí FIFO fronty.DFSProhledávání do hloubky jde po každé větvi co nejdál, než se vrátí zpět, a používá zásobník.Postupně se prohlubující DFSPostupně se prohlubující DFS opakovaně spouští hloubkově omezené DFS a každé kolo zvedne limit — získá tak postupný dosah BFS s nepatrnou pamětí DFS.Dijkstra (nejkratší cesta)Dijkstra najde nejkratší cestu z výchozího uzlu tím, že vždy rozvine nejbližší nenavštívený uzel — váha hrany je tu vzdálenost mezi uzly.Prim's MSTPrim nechá minimální kostru růst z výchozího uzlu — vždy přidá nejlevnější hranu, která dosáhne na nový uzel.Kruskal's MSTKruskal staví minimální kostru přidáváním hran od nejlevnější po nejdražší a přeskakuje ty, které by vytvořily cyklus.Borůvkova MSTBorůvka staví minimální kostru v kolech: každá komponenta naráz popadne svou nejlevnější odchozí hranu, takže se les rychle slučuje paralelně.Bellman-FordBellman-Ford najde nejkratší cesty relaxací každé hrany V-1krát — pomalejší než Dijkstra, ale zvládá záporné váhy hran.Topologické řazeníTopologické řazení seřadí vrcholy orientovaného acyklického grafu tak, aby každá hrana mířila dopředu — platné pořadí pro úkoly, které na sobě závisí.Floyd-WarshallFloyd-Warshall najde najednou nejkratší vzdálenost mezi každou dvojicí vrcholů tím, že se opakovaně ptá, zda není cesta přes další vrchol kratší.Komponenty silné souvislostiSCC je skupina vrcholů, které se navzájem dosáhnou. Kosarajův algoritmus je najde dvěma průchody do hloubky — jedním na grafu, druhým na jeho obráceném.Maximální tokKolik může protéct ze zdroje do spotřebiče sítí trubek s kapacitami? Edmonds-Karp to zjistí opakovaným tlačením toku po nejkratší cestě s volným místem.Artikulační body a mostyArtikulační bod je vrchol, jehož odebrání rozdělí graf; most je taková hrana. Tarjan najde obojí jedním DFS sledováním, jak daleko zpět každý podstrom dosáhne.Komponenty souvislostiKomponenty souvislosti jsou oddělené „ostrovy“ grafu — maximální skupiny vrcholů vzájemně dosažitelných. Záplavové vyplnění obarví každou jednou barvou.Test bipartitnostiGraf je bipartitní, pokud se jeho vrcholy rozdělí do dvou skupin tak, že každá hrana vede mezi nimi — ověří se obarvením dvěma barvami pomocí BFS.Detekce cykluDetekce cyklu zjišťuje, zda neorientovaný graf obsahuje smyčku — DFS ji najde ve chvíli, kdy narazí na zpětnou hranu k dřívějšímu vrcholu.
Hledání cesty v mřížce
Najdi cestu bludištěm zdí.
Hledání cesty BFSProhledávání do šířky prozkoumává mřížku v prstencích stejné vzdálenosti, takže když poprvé dosáhne cíle, má nejkratší cestu — rozšiřuje se ale do všech směrů.Hledání cesty A*A* je BFS se smyslem pro směr: vždy rozvíjí buňku s nejlepším odhadem celkové ceny, takže míří k cíli a prozkoumá mnohem méně buněk.Hladové prohledáváníHladové prohledávání (best-first) vždy míří k buňce, která vypadá nejblíž cíli. Je rychlé a přímočaré, ale dá se zmást a najít delší, neoptimální cestu.Obousměrné hledáníObousměrné hledání spustí dvě vlny BFS najednou — jednu ze startu, druhou z cíle — a zastaví se tam, kde se potkají, takže prozkoumá mnohem méně buněk než jediné hledání.Dijkstra (vážená mřížka)Dijkstra na mřížce, kde vstup do buněk stojí různě, najde nejlevnější trasu — která se může vinout kolem drahého terénu místo nejmenšího počtu kroků.Generování bludištěRekurzivní backtracker vytvoří bludiště náhodným prohledáváním do hloubky — proráží vpřed, boří zdi a vrací se ze slepých uliček, dokud nedosáhne každé buňky.Záplavové vyplněníZáplavové vyplnění je plechovka barvy: z jedné buňky se rozšíří do každé propojené volné buňky a zastaví se u zdí — vyplní celou oblast jedním průchodem.Bludiště — PrimRandomizovaný Prim nechá bludiště růst ze zárodku ven: udržuje frontu místností sousedících s bludištěm a pořád připojuje náhodnou, dokud nejsou všechny uvnitř.Bludiště — WilsonWilsonův algoritmus tvoří bludiště smyčky-mažícími náhodnými procházkami — bloumá z nenavštívených místností, dokud nenarazí na bludiště — takže každé možné bludiště je stejně pravděpodobné.
Dynamické programování
Vyplň tabulku, využívej podproblémy.
Editační vzdálenostEditační vzdálenost (Levenshtein) je nejmenší počet vložení, smazání a záměn jednoho znaku, kterými se jeden řetězec změní na druhý — počítá se v tabulce.Nejdelší společná podposloupnostNejdelší společná podposloupnost je nejdelší sled znaků, který se vyskytuje v obou řetězcích ve stejném pořadí, ne nutně vedle sebe — najde se DP tabulkou.Mince na částkuCoin change najde nejmenší počet mincí, které dají dohromady cílovou částku, s neomezenou zásobou každé hodnoty — sestavuje se v tabulce, částka po částce.Součet podmnožinySubset sum se ptá, zda nějaká podmnožina sady čísel dá v součtu cíl — tabulka označí každou dvojici (číslo, součet) jako dosažitelnou či ne.Nejdelší rostoucí podposloupnostNejdelší rostoucí podposloupnost je nejdelší sled hodnot, který zleva doprava roste — prvky se berou v pořadí, ale ne nutně vedle sebe.Problém batohu 0/1Problém batohu 0/1 vybere nejhodnotnější množinu předmětů, která se vejde do váhového limitu — každý předmět celý, nebo vůbec — vyplňuje se kapacita po kapacitě.Neomezený batohNeomezený batoh maximalizuje hodnotu ve váhovém limitu, když lze každý předmět vzít libovolněkrát — takže nejlepší sloupec vlevo přihrává do stejného řádku.RozděleníProblém rozdělení se ptá, zda lze sadu čísel rozdělit do dvou skupin se stejnými součty — což jde jen tehdy, je-li celek sudý a nějaká podmnožina dosáhne jeho poloviny.Kadaneovo maximální podpoleKadaneův algoritmus najde největší součet libovolného souvislého úseku jedním průchodem — prodlužuje běžící okno a opustí ho ve chvíli, kdy jeho součet klesne pod nulu.Fibonacci (DP)Fibonacciho posloupnost stavěná zdola nahoru: každý člen je součtem dvou předchozích a vyplňuje jednořádkovou tabulku zleva doprava v lineárním čase.
Výpočetní geometrie
Tvary a body v rovině.
Teorie čísel
Prvočísla, dělitelé a triky s čísly.
Eratosthenovo sítoStarobylý a elegantní způsob, jak najít všechna prvočísla do n: vypiš čísla, pak opakovaně vezmi další neškrtnuté a vyškrtej všechny jeho násobky.Euklidův největší společný dělitelNejvětší společný dělitel a a b jako geometrie: strana největšího čtverce, kterým beze zbytku vydláždíš obdélník a×b.Eulerova funkce φ (síto)φ(n) udává, kolik čísel od 1 do n nemá s n žádného společného dělitele. Síto spočítá všechna φ najednou.Pascalův trojúhelníkKaždé číslo je součet dvou přímo nad ním; kraje jsou 1. Řádek n vypisuje binomické koeficienty C(n,0..n).Collatzova hypotéza (3n+1)Z n: je-li sudé, vyděl dvěma, jinak 3n+1. Nedokázaná hypotéza: vždy nakonec dojdeš k 1.Řetězový zlomekZapiš a/b jako a₀ + 1/(a₁ + 1/(a₂ + …)). Členy jsou přesně podíly Euklidova algoritmu.Rozklad na prvočísla (faktorizační strom)Opakovaně rozděl číslo na jeho nejmenší prvočíselný dělitel a zbytek, dokud v listech nezůstanou jen prvočísla.Sundaramovo sítoNalézá všechna prvočísla do n označením párů i+j+2ij jako generátorů složenin; zbytek jsou prvočísla.Lineární síto (NSF)Prosévá prvočísla a zaznamenává nejmenšího prvočíselného dělitele každého složeného čísla v čase O(n).Počet dělitelů τ(n)Počítá počet dělitelů každého čísla 2..n přičítáním 1 ke každému násobku každého d.Alikvotní součet a klasifikaceKlasifikuje každé číslo 2..n jako dokonalé, nadbytečné nebo nedostatkové podle součtu jeho vlastních dělitelů.Šťastná číslaUrčuje, která čísla 2..n jsou šťastná — jejich iterovaný součet čtverců číslic nakonec dosáhne 1.Síto bezčtvercových číselOznačuje každé číslo 2..n jako bezčtvercové (žádné p² ho nedělí) nebo ne-bezčtvercové sítováním přes čtverce prvočísel.Dělitelé čísla nZkušebně dělí každé d od 1 do n a zvýrazní přesně dělitele n zeleně.Figurální číslaOznačuje trojúhelníková, čtvercová a pentagonální čísla v 1..n různými barvami procházením indexu k.Časy zastavení Collatzovy posloupnostiBarví každé m ve 2..n podle toho, kolik Collatzových kroků potřebuje k dosažení 1, čímž vzniká heatmapa.Goldbachova domněnkaNalezne první Goldbachův rozklad (největšího sudého ≤ n) jako součet dvou prvočísel prohledáváním nahoru.Pascalův trojúhelník mod 2 (Sierpiński)Pascalův trojúhelník redukovaný modulo 2 odhaluje soběpodobný fraktál — Sierpińského trojúhelník.Catalanův trojúhelníkČíselný trojúhelník, jehož diagonální prvky jsou slavná Catalanova čísla 1, 1, 2, 5, 14, 42, …Stirlingova čísla (2. druhu)S(n,k) udává počet způsobů, jak rozdělit množinu n prvků na právě k neprázdných podmnožin.Bellův trojúhelníkAitkenovo Bellovo schéma, jehož levý okraj generuje Bellova čísla 1, 1, 2, 5, 15, 52, …Eulerova číslaA(n,k) počítá permutace množiny 1…n, které mají právě k vzestupů (pozic, kde je následující prvek větší).Digitální kořenOpakovaně sčítáme cifry čísla n, dokud nezůstane jediná cifra — ta je digitálním kořenem.Šťastné číslo — stopaNahrazujeme n součtem čtverců jeho číslic; zastavíme se při 1 (šťastné) nebo při opakování hodnoty (nešťastné).Říkej co vidíšKaždý člen přečteme nahlas — stejné číslice v řadě nahradíme jejich počtem a hodnotou — a tím vznikne člen další.Recamánova posloupnosta(0)=0; každé a(k) skočí k kroků dozadu je-li výsledek kladný a nový, jinak k kroků dopředu.Faktoriálová posloupnostSestrojí posloupnost 0!, 1!, 2!, …, n! postupným násobením každého členu jeho indexem.Mocniny dvouSestrojí posloupnost 2⁰, 2¹, 2², …, 2ⁿ zdvojováním každého členu.Fareyova posloupnostVypíše všechny zkrácené zlomky v [0, 1] se jmenovatelem ≤ n ve vzestupném pořadí.Nejmenší společný násobekNajde nejmenší kladné celé číslo dělitelné oběma hodnotami procházením násobků většího čísla.Převod soustavPřevede celé číslo a do číselné soustavy se základem b (omezeno na 2–16) opakovaným výpočtem zbytků po dělení.Josephův problémSimuluje kruh n lidí, kteří se postupně vyřazují po každém k-tém, dokud nezůstane jediný přeživší.