Top algoritmy a datové struktury, které opravdu potřebujete znát

Pokud se chcete stát softwarovým inženýrem, ale nevíte, kde začít, ušetříme vás napětí: jsou to algoritmy a datové struktury.

Jakmile pochopíte podstatu těchto pilířů programování, začnete je vídat všude. A čím více algoritmů a datových struktur se naučíte, tím více vám budou sloužit jako tryskové palivo pro vaši kariéru softwarového inženýra.

Abyste mohli začít, pojďme se nejprve ponořit do vyhledávání a třídění, dvou tříd algoritmů, bez kterých se neobejdete. Pak si uděláme rychlý přehled zbytku prostředí, které zahrnuje stromy, grafy, dynamické programování a spoustu dalších.

Hrubě řečeno, existují dvě kategorie vyhledávacích algoritmů, které budete potřebovat znát hned: lineární a binární. Superdůležité jsou také algoritmy Depth First Search (DFS) a Breadth First Search (BFS), ale ty si necháme na část o procházení grafů níže.

Lineární vyhledávání

Lineární a binární algoritmy jsou takto pojmenovány proto, aby popsaly, jak dlouho (časová složitost) bude vyhledávání trvat v závislosti na velikosti prohledávaného vstupu.

Příklad u lineárních vyhledávacích algoritmů, pokud máte k prohledání 100 položek, pak by v nejhorším případě bylo nutné prohlédnout každou položku na vstupu, než narazíte na požadovanou hodnotu. Nazývá se lineární, protože čas potřebný k prohledání je přesně úměrný množství položek v hledání (100 položek/vstup = 100 kontrol/komplexnost)

Zkrátka lineární = jednoduchý (na algoritmu není nic chytrého). Příklad: Představte si, že se snažíte najít svého kamaráda Lina mezi řadou lidí stojících v žádném konkrétním pořadí. Již víte, jak Lin vypadá, takže se jednoduše musíte postupně podívat na jednotlivé osoby, dokud Lina nepoznáte nebo nerozpoznáte. A je to. Přitom postupujete podle algoritmu lineárního vyhledávání

Binární vyhledávání

Binární vyhledávání získalo svůj název proto, že slovo binární znamená „ze dvou věcí nebo týkající se dvou věcí“ a algoritmus pracuje tak, že rozdělí vstup na dvě části, dokud nenajde hledanou položku. Jedna polovina obsahuje hledanou položku a druhá ne. Proces pokračuje, dokud se místo, kde je vstup rozdělen, nestane hledanou položkou. Binární vyhledávání je v podstatě jen vysoce disciplinovaný přístup k procesu eliminace. Je rychlejší než lineární vyhledávání, ale pracuje pouze s uspořádanými posloupnostmi.

Příklad by to měl objasnit. Předpokládejme, že se snažíte najít svého přítele Bina (který měří 175 cm) v jednořadé řadě lidí, kteří byli seřazeni podle výšky zleva doprava, od nejmenšího po nejvyššího. Je to opravdu dlouhá řada a vy nemáte čas procházet ji celou jeden po druhém a porovnávat výšku každého s výškou Bina. Co můžete dělat?“

Zadejte binární vyhledávání. Vyberete osobu v samém středu řádku a změříte její výšku. Měří 175 cm. Hned tedy víte, že tato osoba spolu s ostatními napravo od ní není Bin. Nyní, když jste svůj problém zkrátili na polovinu, zaměříte svou pozornost na zbytek řady a opět vyberete prostřední osobu. Měří metr osmdesát. Můžete tedy vyloučit tuto osobu a všechny po její levici, čímž problém opět rozdělíte na polovinu. A tak dále. Po pouhých pěti nebo šesti takových rozděleních rychle najdete Bina za zlomek času, který vám trvalo najít Lina. Přitom jste postupovali podle algoritmu binárního vyhledávání.

Třídění

Řazení, jinak známé jako třídění, seznamů položek je jednou z nejčastějších programátorských úloh, které budete jako vývojáři provádět. Zde se podíváme na dva nejužitečnější algoritmy třídění:

MergeSort

Předpokládejme, že namísto uspořádané řady lidí z výše uvedeného příkladu potřebujete vytvořit uspořádanou řadu lidí z neuspořádané skupiny. Nemáte mnoho času, a tak vymyslíte strategii, jak vše urychlit.

Nejprve necháte skupinu lidí, která je namačkaná na sebe, rozdělit na dvě části. Pak necháte každou z těchto dvou skupin rozdělit opět na dvě a tak dále, dokud se nezabýváte výhradně jednotlivci. Poté začnete jednotlivce rozdělovat do dvojic a vyšší z dvojice se postaví napravo od toho druhého. Zanedlouho jsou všichni uspořádáni do těchto uspořádaných dvojic zleva doprava.

Následuje sloučení uspořádaných dvojic do uspořádaných skupin po čtyřech; poté sloučení uspořádaných skupin po čtyřech do uspořádaných skupin po osmi; a tak dále. Nakonec zjistíte, že máte kompletní, výškově uspořádanou řadu lidí, přesně takovou, s jakou jste se setkali výše. Aniž byste to věděli, postupovali jste podle algoritmu MergeSort, abyste dosáhli svého úspěchu.

QuickSort

QuickSort je příliš složitý na to, aby si ho lidé mohli snadno představit, takže se pojďme trochu přiblížit ke kódu. Pro začátek si představme, že máte neuspořádaný seznam nebo pole osmi čísel, která chcete seřadit.

4 2 13 6 15 12 7 9

Mohli byste použít MergeSort, ale slyšeli jste, že QuickSort je obecně rychlejší, a tak se rozhodnete ho vyzkoušet. Vaším prvním krokem je výběr čísla v seznamu, které se nazývá pivot. Výběr správného čísla pivotu bude mít zásadní vliv na to, jak rychle bude QuickSort fungovat, a pro výběr dobrých pivotů existují připravené vzorce, kterými se můžete řídit. Prozatím to ale zjednodušíme a jako číslo pivotu zvolíme poslední číslo v poli: 9.

4 2 13 6 15 12 7 9

Pro usnadnění dalšího kroku vytvoříme na začátku pole oddělovač a znázorníme ho znakem libry.

# 4 2 13 6 15 12 7 9

Pokračujeme-li v našem poli zleva doprava, je naším cílem umístit jakékoli číslo menší než pivot (9) nalevo od oddělovače a jakékoli číslo větší (nebo rovno) pivotu napravo od oddělovače. Začneme prvním číslem v našem poli: 4. Abychom jej přesunuli vlevo od oddělovače, stačí oddělovač posunout o jeden prvek nahoru:

4 # 2 13 6 15 12 7 9

To samé uděláme s dalším číslem: 2.

4 2 # 13 6 15 12 7 9

Pak se ale dostaneme k číslu 13, které je větší než otočné číslo 9 a je již na pravé straně oddělovače. Necháme ji tedy být. Dále dojdeme k číslu 6, které musí jít nalevo od oddělovače. Nejprve ji tedy prohodíme s 13, abychom ji dostali na místo:

4 2 # 6 13 15 12 7 9

Poté ji přesuneme za oddělovač:

4 2 6 # 13 15 12 7 9

Následuje 15, která je již napravo od oddělovače, takže ji necháme být. Pak máme 12. To samé. Ale 7, naše poslední číslo před dosažením čepu, potřebuje stejný druh pomoci při přesunu jako 6. Vyměníme tedy 7 za 13, abychom ji dostali na místo:

4 2 6 # 7 15 12 13 9

Poté opět přesuneme oddělovač kolem ní:

4 2 6 7 # 15 12 13 9

Nakonec se dostaneme k našemu otočnému číslu: 9. V tomto případě se jedná o číslo, které je na místě. Podle stejné logiky jako výše prohodíme 15 s 9, abychom dostali otočné číslo tam, kde má být:

4 2 6 7 # 9 12 13 15

Protože všechna čísla nalevo od 9 jsou nyní menší než 9 a všechna čísla napravo od 9 jsou větší než 9, máme první cyklus QuickSort za sebou. Dále budeme s každou sadou čtyř čísel na obou stranách oddělovače zacházet jako s novým polem, na které aplikujeme QuickSort. Ušetříme vás podrobností, ale v dalším kole získáme čtyři dvojice čísel, na které můžeme snadno aplikovat závěrečný cyklus QuickSort. Konečným výsledkem bude následující uspořádaný seznam, jehož vytvoření nám zabralo méně času než při použití jednoduššího MergeSort:

2 4 6 7 9 12 13 15

Třídicí algoritmy – tahák

Jedná se o nejběžnější třídicí algoritmy s několika doporučeními, kdy je použít. Osvojte si je! Používají se všude!

Třídění na hromadu: Když nepotřebujete stabilní třídění a záleží vám více na výkonu v nejhorším než v průměrném případě. Má zaručenou rychlost O(N log N) a používá pomocný prostor O(1), což znamená, že při velmi velkých vstupech vám neočekávaně nedojde místo na hromadě nebo na zásobníku.

Introsort: To je rychlé třídění, které se po určité hloubce rekurze přepne na třídění na hromadě, aby se obešel nejhorší případ rychlého třídění O(N²). Je téměř vždy lepší než obyčejné staré rychlé třídění, protože získáte průměrný případ rychlého třídění se zaručeným výkonem O(N log N). Pravděpodobně jediným důvodem, proč místo něj použít řazení na hromadě, je v systémech se silně omezenou pamětí, kde je O(log N) místa na zásobníku prakticky významné.

Vložení řazení: Pokud je zaručeno, že N je malé, a to i jako základní případ rychlého třídění nebo slučovacího třídění. I když je to O(N²), má velmi malou konstantu a je to stabilní třídění.

Bublinkové třídění, výběrové třídění: Když děláte něco rychlého a špinavého a z nějakého důvodu nemůžete prostě použít třídicí algoritmus standardní knihovny. Jedinou jejich výhodou oproti třídění vkládáním je, že jsou o něco jednodušší na implementaci.

Rychlé třídění: Když nepotřebujete stabilní třídění a na výkonu v průměrném případě záleží více než na výkonu v nejhorším případě. Rychlé třídění je v průměru O(N log N), v nejhorším případě O(N²). Dobrá implementace používá O(log N) pomocného úložiště v podobě zásobníkového prostoru pro rekurzi.

Merge sort: Pokud potřebujete stabilní třídění O(N log N), je to asi jediná možnost. Jeho jedinou nevýhodou je, že využívá pomocný prostor O(N) a má o něco větší konstantu než rychlé třídění. Existují některá slučovací třídění na místě, ale AFAIK všechna buď nejsou stabilní, nebo jsou horší než O(N log N). Dokonce i O(N log N) in place sorty mají o tolik větší konstantu než obyčejný starý merge sort, že jsou spíše teoretickou kuriozitou než užitečným algoritmem.