Úvod do triediacich algoritmov v JavaScripte

Podobne ako väčšina ostatných programovacích jazykov, môžete naraziť na scenáre, v ktorých musíte zoradiť niektoré čísla v JavaScripte vzostupne alebo zostupne. Aby sme to dosiahli, môžeme použiť veľa algoritmov, ako napríklad triedenie bubliniek, výber triedenia, zlúčenie triedenia, rýchly prehľad atď. Tieto algoritmy sa líšia nielen tým, ako fungujú, ale každý z nich má tiež odlišné požiadavky na pamäť a čas, prehĺbte si niektoré dôležité algoritmy triedenia a zistite, ako ich môžete použiť vo svojom kóde JavaScript.

Top 6 triediacich algoritmov v JavaScripte

Tu je niekoľko triediacich algoritmov v javascripte vysvetlených nižšie s príkladmi:

1. Algoritmus triedenia bubliniek

Považované za jeden z najbežnejších nástrojov tohto obchodu, druh bubliny funguje tak, že vytvára slučku, ktorá porovnáva každú položku v poli s inou položkou. Ak je porovnávaná položka menšia ako položka na strane, vymeníme ich miesta. To pokračuje ďalej, až kým nezískame priechod, kde žiadna položka v poli nie je väčšia ako položka, ktorá je vedľa nej.

Triedenie bubliniek má časovú zložitosť O (n 2 ) a zložitosť priestoru O (n).

kód:

function swap(arr, firstIndex, secondIndex)(
var temp = arr(firstIndex);
arr(firstIndex) = arr(secondIndex);
arr(secondIndex) = temp;
)
function bubbleSortAlgo(arraaytest)(
var len = arraaytest.length,
i, j, stop;
for (i=0; i < len; i++)(
for (j=0, stop=len-i; j < stop; j++)(
if (arraaytest(j) > arraaytest(j+1))(
swap(arraaytest, j, j+1);
)
)
)return arraaytest;
)
console.log(bubbleSortAlgo((3, 6, 2, 5, -75, 4, 1)));

Výkon:

2. Výber Algoritmus zoradenia

Teraz, keď sme skončili s diskusiou o algoritme triedenia bubliniek, pozrime sa na to, rovnako ako populárny algoritmus na triedenie nazývaný výberové triedenie.

Na rozdiel od Bubble Sort sa zameriavame na nájdenie najmenšej hodnoty v poli, aby bolo triedenie dokončené. Toto je podrobné členenie toho, ako funguje výberové triedenie:

  • Prvú položku v poli predpokladáme ako najmenšiu.
  • Porovnávame túto položku s nasledujúcou položkou v poli.
  • Ak je ďalšia položka menšia ako položka, ktorú máme k dispozícii, nastavíme nasledujúcu položku ako novú najmenšiu hodnotu.
  • Tieto kroky opakujeme, až kým nedosiahneme koniec poľa.
  • Keď nájdeme hodnotu v poli, ktorá je menšia ako hodnota, ktorú sme začali, vymeníme ich pozície.
  • Stále robíme porovnania a prejdeme k ďalšej položke. Kým nebude zoradené celé pole.

Rovnako ako algoritmus triedenia bubliniek, aj triedenie výberu má časovú zložitosť O (n 2 ) a zložitosť priestoru O (n).

kód:

function SelectionSortAlgo(array, compare_Function) (
function comp(a, b) (
return a - b;
)
var min = 0;
var index = 0;
var temp = 0;
compare_Function = compare_Function || compare;
for (var i = 0; i < array.length; i += 1) (
index = i;
min = array(i);
for (var j = i + 1; j < array.length; j += 1) (
if (compare_Function(min, array(j)) > 0) (
min = array(j);
index = j;
)
)
temp = array(i);
array(i) = min;
array(index) = temp;
)
return array;
)
console.log(SelectionSortAlgo((9, 15, 2, 44, -1, 36, 1), function(a, b) ( return a - b; )));

Výkon:

3. Zlúčiť algoritmus triedenia

Podobne ako pri triedení a výbere bubliniek, aj triedenie podľa zlúčenia je jedným z populárnych algoritmov triedenia v informatike, môžete ho implementovať vo väčšine programovacích jazykov a má dobrý výkon bez toho, aby bolo na zdroje príliš potrebné.

Zlúčiť zoradenie používa na rozdelenie poľa alebo ľubovoľného zoznamu prvkov metódu Rozdeľ a dobývať. Termín rozdeľuje a dobýva znamená, že jeden veľký problém rozdelíme na niekoľko menších problémov a potom tieto malé problémy vyriešime. Akonáhle sú menšie problémy vyriešené, kombinujeme výsledky, ktoré vedú k riešeniu veľkého problému.

Pochopenie algoritmu je v skutočnosti jednoduché:

  • Dané pole rozdelíme na n polí, pričom každé z týchto polí obsahuje iba 1 prvok.
  • Zlúčením polí vytvorte nové pole.
  • Opakujte krok 2, až kým nezostane iba 1 pole, ktoré bude triedeným poľom.

kód:

function merge_sort_algo(left, right)
(
var i = 0;
var j = 0;
var result = ();
while (i < left.length || j < right.length) (
if (i === left.length) (
// j is the only index left_part
result.push(right(j));
j++;
)
else if (j === right.length || left(i) <= right(j)) (
result.push(left(i));
i++;
) else (
result.push(right(j));
j++;
)
)
return result;
)
console.log(merge_sort_algo((1, 44, 6), (84, 7, 5)));

Výkon:

4. Algoritmus rýchleho zoradenia

Quicksort je jedným z najúčinnejších spôsobov triedenia prvkov v počítačových systémoch. Aplikácia Quicksort, ktorá je jednoduchšia na zlúčenie zoradenia, pracuje na algoritme rozdelenia a dobývania. V tomto nájdeme v poli pivotnú položku, ktorá porovnáva všetky ostatné polia prvkov proti a potom presunieme položky tak, aby všetky položky pred našimi vybranými pivotnými položkami boli menšie a všetky položky za pivotnou položkou boli väčšie. Keď to urobíme, kľúčom je, aby sme to robili opakovane, a my budeme mať naše zoradené pole.

Nasledujú kroky, ktoré je možné vykonať pri implementácii algoritmu rýchleho presunu:

  • Vyberieme prvok poľa a nazývame ho „Pivot Point“
  • Začneme ukazovateľ nazývaný ľavý ukazovateľ, od ktorého je prvý prvok v poli.
  • Podobne začneme ukazovateľ nazývaný správny ukazovateľ pri poslednej položke v poli.
  • Ak je hodnota prvku v ľavom ukazovateli nižšia v porovnaní s vybratým bodom otáčania, posúvame ľavý ukazovateľ doľava (pridajte do neho +1) a opakujte ho, až kým sa nezistí, že hodnota v ľavom ukazovateli je väčšia ako hodnota hodnota bodu otáčania alebo rovná.
  • Ak je hodnota prvku na pravom ukazovateli v zozname vyššia ako hodnota otočného prvku, aktivujeme pravý ukazovateľ doľava. Tento postup opakujte dovtedy, kým hodnota na pravom bočnom ukazovateli nebude nižšia ako (alebo rovná) hodnote otočného čapu.
  • Ak je hodnota ľavého ukazovateľa menšia alebo rovnaká ako hodnota pravého ukazovateľa, hodnoty vymeňte.
  • Presuňte pravý ukazovateľ o jednu po druhej, ľavý o jednu po druhej.
  • Opakujte, kým sa nezhodujú ľavé a pravé ukazovatele.

kód:

function quickSortAlgo(origArray) (
if (origArray.length <= 1) (
return origArray;
) else (
var left = ();
var right = ();
var newArray = ();
var pivot = origArray.pop();
var length = origArray.length;
for (var i = 0; i < length; i++) (
if (origArray(i) <= pivot) (
left.push(origArray(i));
) else (
right.push(origArray(i));
)
)
return newArray.concat(quickSortAlgo(left), pivot, quickSortAlgo(right));
)
)
var myArray = (13, 50, 2, 45, -1, 74, 11 );
var arreySorted = quickSortAlgo(myArray);
console.log(arreySorted);

Výkon:

5. Algoritmus zoradenia vloženia

Pokiaľ ide o jednoduchú implementáciu, druh vloženia je všeobecne známy ako jeden z jednoduchších algoritmov. Pri triedení vloženia sa prvky poľa porovnajú navzájom a potom sa usporiadajú v konkrétnom poradí. Je to veľmi podobné usporiadaniu kariet v balíčku. Druh vloženia názvu pochádza z procesu vyberania prvku a jeho vkladania na správne miesto a jeho opakovania pre všetky prvky.

Takto funguje algoritmus:

  • Prvý prvok poľa sa považuje za už usporiadaný.
  • Vyberte ďalší prvok poľa.
  • Porovnajte vybratý prvok so všetkými prvkami v poli.
  • Posuňte každý prvok v poli, ktorý je väčší ako hodnota vybratého prvku.
  • Vložte prvok
  • Opakujte kroky 2 až 5, až kým nebude pole zoradené.

kód:

function insertion_Sort_algo(arr)
(
for (var i = 1; i < arr.length; i++)
(
if (arr(i) < arr(0))
(
arr.unshift(arr.splice(i, 1)(0));
)
else if (arr(i) > arr(i-1))
(
continue;
)
else (
for (var j = 1; j < i; j++) (
if (arr(i) > arr(j-1) && arr(i) < arr(j))
(
arr.splice(j, 0, arr.splice(i, 1)(0));
)
)
)
)
return arr;
)
console.log(insertion_Sort_algo((44, 20, 26, 54, -9, 41, 16)));

Výkon:

6. Algoritmus triedenia haldy

Triedenie haldy je spôsob triedenia prvkov pomocou dátovej štruktúry „haldy“. Táto metóda je veľmi podobná technike výberu druhov, o ktorej sme diskutovali vyššie. Teraz sa možno pýtate na Heaps a ako sú definované, skôr ako sa dostaneme k algoritmu, najprv pochopíme haldy.

Stručne povedané, halda je binárny strom s niektorými pridanými pravidlami. Jedno pravidlo uvádza, že v halde musí byť strom úplným binárnym stromom, čo jednoducho znamená, že pred pridaním ďalšieho je potrebné vyplniť všetky uzly na aktuálnej úrovni. Ďalším pravidlom pre haldu je, že musí existovať definovaný podradený a nadradený vzťah s hodnotami prvkov haldy.

V mincovni musí byť hodnota rodiča menšia ako hodnota jej detí. Ako viete, v maximálnej halde musí byť hodnota rodiča vyššia ako jej dieťa.

Teraz, keď definície nie sú v poriadku, poďme sa pozrieť, ako haldy fungujú:

  • Najprv zostavíme maximálnu haldu, ktorá zaisťuje, že prvok s najvyššou hodnotou je na vrchu.
  • Prepneme horný prvok s posledným prvkom haldy, odstránime horný prvok z haldy a uložíme ho do triedeného poľa.
  • Opakujeme krok jeden a dva, až kým v halde nezostane iba jeden prvok.

Jedna vec, ktorú treba mať na pamäti, je, že Heaps nie je v JavaScripte natívne podporovaný, preto sa musíme uchýliť k implementácii Heaps pomocou polí. Priestorová zložitosť haldy je O (1), ktorá je vynikajúca, a hoci je to o niečo zložitejšie v porovnaní s zlúčením alebo vložením, pokiaľ ide o pochopenie a implementáciu, myslím si, že z hľadiska výkonnosti je lepšie použiť ju v veľké projekty.

kód:

var arrLength;
function heapRoot(input, i) (
var left = 2 * i + 1;
var right = 2 * i + 2;
var max = i;
if (left input(max)) (
max = left;
)
if (right input(max)) (
max = right;
)
if (max != i) (
swap(input, i, max);
heapRoot(input, max);
)
)
function swap(input, index_A, index_B) (
var temp = input(index_A);
input(index_A) = input(index_B);
input(index_B) = temp;
)
function heapSortAlgo(input) (
arrLength = input.length;
for (var i = Math.floor(arrLength / 2); i >= 0; i -= 1) (
heapRoot(input, i);
)
for (i = input.length - 1; i > 0; i--) (
swap(input, 0, i);
arrLength--;
heapRoot(input, 0);
)
)
var arr = (12, 10, 22, 55, -8, 64, 14);
heapSortAlgo(arr);
console.log(arr);

Výkon:

záver

Triedenie je dôležitou súčasťou vytvárania aplikácií a webových stránok pomocou JavaScriptu. Teraz, keď ste oboznámení s niektorými z najdôležitejších algoritmov na vykonanie úlohy, mali by ste sa v JS Development cítiť istejšie.

Jedným dôležitým faktom, ktorý treba mať na pamäti pri rôznych triedeniach, je to, že sa nemusíte príliš zdôrazňovať, aký algoritmus sa má vo väčšine prípadov použiť. Teraz, keď je počítačový hardvér tak výkonný, moderné telefónne a stolné procesory nezrušia pot pri triedení ani stoviek prvkov za niekoľko milisekúnd. Je to len prípad, keď ste zaseknutí pomalým hardvérom alebo situácie, keď optimalizujete každú jednotlivú časť kódu, pričom zmena algoritmov triedenia môže byť prospešná.

Odporúčané články

Toto je sprievodca triedením algoritmov v JavaScripte. Tu diskutujeme o najlepších 6 triediacich algoritmoch v javascripte spolu s príkladmi a implementáciou kódu. Ďalšie informácie nájdete aj v nasledujúcich článkoch -

  1. Kompilátory JavaScriptu
  2. Obrátiť sa na JavaScript
  3. Úvod do JavaScriptu
  4. Štvorce v Jave
  5. Algoritmy rýchleho triedenia v Jave
  6. Polia v štruktúre údajov
  7. Algoritmus C ++ Príklady algoritmu C ++

Kategórie:

Vývoj softvéru