začátečník třídění algoritmy v JavaScriptu: bublina, výběr a vložení Třídit

mít své datové sady uspořádány všechny chtě nechtě bude jen přidat více času a zdrojů pro správu a prohledávat. Zda jsou vaše data tříděna nebo ne, bude mít přímý vliv na to, jaké metody vyhledávání můžete použít, a může znamenat rozdíl mezi vyhledáváním s milionem operací nebo s 10, jako u binárního vyhledávání.

pro jednoduchost se zaměříme pouze na třídění řady čísel od nejmenších po největší, ale tyto algoritmy jsou snadno modifikovatelné pro jiné cíle třídění. Mějte na paměti, že se jedná o obecnější pojmy a vzorce a méně o“ postup “ pro třídění dat, protože vaše konkrétní implementace se může hodně lišit, ale nakonec se může koncepčně podobat těmto vzorcům.

zde je praktické pole 50 náhodných čísel.

const unsortedArr = ;

předpoklady

budu se dívat na všechno optikou Big O notace, takže pochopení toho, jak složitost roste v průběhu času, bude velmi užitečné.

Bubble Sort

Toto je „Hello World“ třídících metod, nic bláznivého, ale to dělá práci.

pro každou položku v poli chceme zkontrolovat, zda je další položka větší, pokud je pak zaměnit své indexy v poli. Abychom se vyhnuli opětovnému porovnání tříděných čísel, začneme od zadní části pole, zatímco další for loop dostane předchozí číslo. Tímto způsobem všechny největší hodnoty vybudovat, nebo „bubliny nahoru“, na konci.

animace řazení bublin

grafika / animace díky VisuAlgo.net

naše verze funguje obráceně než animace, ale je to dost blízko.

const bubble = arr => { const swap = (list, a, b) => , list] = , list]; for (let i = arr.length; i > 0; i--) { for (let j = 0; j < i - 1; j++) { if (arr > arr) swap(arr, j, j + 1); }; }; return arr;};console.log(bubble(unsortedArr));

Selection Sort

Selection sort funguje jako opak Bubble sort, zatímco bubble třídění tlačí všechny největší hodnoty až do konce teď budeme tlačit minimální hodnoty na začátek.

pokaždé, když smyčky přes pole vybere nejmenší hodnotu, pokud najde nižší hodnotu, která se pak stane novou nejnižší hodnotou. Když je smyčka hotová, vezme to minimum a před opětovným spuštěním smyčky ji položí na přední část pole. Tímto způsobem je nejnižší hodnota každé iterace naskládána na přední stranu, dokud není celé pole seřazeno.

výběr řazení animace

grafika / animace díky VisuAlgo.net

const selection = arr => { const swap = (list, a, b) => , list] = , list]; arr.forEach((item, i) => { let min = i; for (let j = i + 1; j < arr.length; j++) { if (arr < arr) min = j; }; swap(arr, i, min); }); return arr;};console.log(selection(unsortedArr));

Insertion Sort

můj osobní oblíbený a nejvýkonnější ze tří, insertion sort, je více podobný tomu, jak byste něco řadili ručně.

na pole se díváme jako na dvě části, tříděné a netříděné, pokaždé, když najdeme novou hodnotu, vrátíme se zpět, abychom našli jeho místo v tříděné polovině. S každým přidáním roste naše tříděná skupina, dokud se nejedná o celé pole.

animace řazení vložení

grafika / animace díky VisuAlgo.net

const insertion = arr => { arr.forEach((item, i) => { let num = arr; let j; for (j = i - 1; j >= 0 && arr > num; j--) { arr = arr; }; arr = num; }); return arr;};console.log(insertion(unsortedArr));

srovnání

jedním z problémů s použitím notace Big O pro porovnávání algoritmů je to, že je založeno na horším scénáři, který může být stejný napříč algoritmy, což dává falešnou iluzi, že jsou si rovni. Zatímco bubliny, výběr a vkládání jsou všechny O (n^2), to nám neříká mnoho o průměrném nebo nejlepším scénáři nebo o tom, jak se liší se strukturou dat.

třídění vložení vyhrává pokaždé. Výhodou je také to, že před spuštěním nemusíte mít celé pole, což vám umožní třídit věci v reálném čase, jak přicházejí data.

Mějte to na paměti, protože byste se neměli rozhodnout, který algoritmus je „nejlepší“, než zvážíte, jak jsou vaše data již organizována.

závěr

tyto tři jsou daleko od nejlepších řešení pro efektivní třídění velkého množství dat, ale jsou některé z nejintuitivnějších ponořit prsty do toho, co může být ohromující oceán. 🌊