Johdatus algoritmien lajitteluun JavaScriptillä

Kuten useimmat muutkin ohjelmointikielet, voit törmätä tilanteisiin, joissa joudut lajittelemaan joitakin numeroita JavaScript: ssä nousevaan tai laskevaan järjestykseen. Saadaksesi sen aikaan, voimme käyttää monia algoritmeja, kuten Bubble Sort, Selection Sort, Merge Sort, Quicksort jne. Nämä algoritmit eivät eroa pelkästään niiden toiminnasta, vaan myös jokaisella on erilaiset vaatimukset muistin ja keston suhteen. kaivaa syvemmälle joitain tärkeitä lajittelualgoritmeja ja katso kuinka voit käyttää niitä JavaScript-koodissasi.

Kuusi suosituinta lajittelualgoritmia JavaScriptissä

Tässä on joitain JavaScriptin lajittelualgoritmeja, selitetään alla esimerkein:

1. Kuplalajittelualgoritmi

Bubble-lajittelua pidetään yhtenä tämän kaupan yleisimmistä työkaluista luomalla silmukka, joka vertaa taulukon kaikkia kohteita toiseen. Jos vertailtu esine on pienempi kuin käsillä oleva, vaihdamme paikkoja. Tämä jatkuu, kunnes meillä on pääsy, jossa mikään taulukon kohde ei ole suurempi kuin vieressä oleva esine.

Bubble Sortilla on O (n 2 ) ajan monimutkaisuus ja O (n) tilan monimutkaisuus.

Koodi:

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)));

lähtö:

2. Valinnan lajittelualgoritmi

Nyt kun olemme keskustelleet Bubble Sort Algorithmista, katsotaanpa aivan yhtä suosittua lajittelualgoritmia nimeltään Selection Sort.

Toisin kuin Bubble Sort, keskitymme etsimään taulukon pienin arvo saadaksesi lajittelu loppuun. Tässä on vaiheittainen erittely siitä, miten valintalajittelu toimii:

  • Oletetaan, että taulukon ensimmäinen kohde on pienin.
  • Vertaamme tätä tuotetta seuraavaan ryhmään.
  • Jos seuraava kohde on pienempi kuin käsiteltävänä oleva, asetamme seuraavan kohteen uudeksi pienimmäksi arvoksi.
  • Toistamme nämä vaiheet, kunnes saavutamme taulukon lopun.
  • Kun löydämme taulukosta arvon, joka on pienempi kuin aloitimme, vaihdamme heidän sijaintinsa.
  • Jatkamme vertailuja ja siirrymme seuraavaan kohtaan. Kunnes koko taulukko on lajiteltu.

Aivan kuten Bubble Sort -algoritmi, myös Selection-lajittelulla on O (n 2 ) ajan monimutkaisuus ja O (n) tilan monimutkaisuus.

Koodi:

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; )));

lähtö:

3. Yhdistä lajittelualgoritmi

Samanlainen kuin Bubble Sort and Selection Sort, yhdistämislajittelu on yksi tietotekniikan suosituimmista lajittelualgoritmeista, voit ottaa sen käyttöön useimmissa ohjelmointikielissä, ja se on hyvä suorituskyky ilman, että se on tarpeeksi resursseja.

Yhdistämisjärjestys lajittelee taulukon tai minkä tahansa elementtiluettelon Divide and Conquer -menetelmän avulla. Termi jakaa ja valloittaa tarkoittaa, että jaamme yhden suuren ongelman useaksi pienemmäksi ongelmaksi ja sitten ratkaisemme nämä pienet ongelmat. Kun pienet ongelmat on ratkaistu, yhdistämme tulokset, jotka johtavat ratkaisuun suureen ongelmaan.

Algoritmin ymmärtäminen on itse asiassa yksinkertaista:

  • Jaamme annetun taulukon n taulukkoon, kukin näistä taulukoista sisältää vain yhden elementin.
  • Yhdistä taulukot tuottaaksesi uuden taulukon.
  • Toista vaihe 2, kunnes jäljellä on vain 1 taulukko, joka on lajiteltu taulukko.

Koodi:

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)));

lähtö:

4. Pikalajittelualgoritmi

Quicksort on yksi tehokkaimmista tavoista lajitella elementtejä tietokonejärjestelmissä. Similor yhdistää lajittelu, Quicksort toimii jakaa ja valloittaa algoritmi. Löydämme tässä taulukosta kääntökohteen vertailemaan kaikkia muita elementtiryhmiä ja sitten siirrämme kohteita tavalla, jossa kaikki kohteet ennen valittuja kääntökohteita ovat pienempiä ja kaikki kohteet kääntökohteen jälkeen ovat kooltaan suurempia. Kun olemme tehneet sen, avain on jatkaa sen tekemistä toistuvasti ja meillä on lajiteltu joukko.

Seuraavat vaiheet, joita voidaan noudattaa suorittamalla pikavalintaalgoritmi:

  • Valitaan taulukon elementti ja kutsutaan sitä “Pivot Point”
  • Aloitamme vasemman osoittimen nimeltä osoittimen, josta on taulukon ensimmäinen elementti.
  • Samoin aloitamme oikean osoittimen nimityksen osoittimen taulukon viimeisestä kohdasta.
  • Jos elementin arvo vasemmassa osoittimessa on vähemmän kuin valitussa kääntöpisteessä, siirrämme vasenta osoitinta vasemmalle (lisää siihen +1) ja toistamme sitä kunnes vasen osoittimen arvo todetaan olevan suurempi kuin kääntöpisteen arvo tai yhtä suuri kuin se.
  • Jos elementin arvo luettelon oikeassa osoittimessa on korkeampi kuin kääntyvän elementin arvo, modeloimme oikea osoitin vasemmalle. Toista tämä, kunnes oikeanpuoleisen osoittimen arvo on pienempi (tai yhtä suuri kuin) kääntöarvon arvo.
  • Kun vasemman osoittimen arvo on pienempi tai yhtä suuri kuin oikean osoittimen arvo, vaihda arvot.
  • Siirrä oikea osoitin vasemmalle yhdellä, vasen osoitin oikealla yksi kerrallaan.
  • Toista, kunnes vasen ja oikea osoitin kohtaavat.

Koodi:

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);

lähtö:

5. Lisäyslajittelualgoritmi

Suorittamisen helpottamiseksi lisäyslajittelu tunnetaan laajalti yhtenä yksinkertaisemmasta algoritmista. Lisäyslajittelussa taulukon elementtejä verrataan toisiinsa ja järjestetään sitten tiettyyn järjestykseen. Tämä on hyvin samanlainen kuin korttien järjestäminen kannelle. Nimen lisäyslaji tulee elementin poimintaprosessista, sen asettamisesta oikeaan paikkaan ja toistamisen jälkeen kaikille elementeille.

Näin algoritmi toimii:

  • Matriisin ensimmäistä elementtiä pidetään jo lajiteltuna.
  • Valitse taulukon seuraava elementti.
  • Vertaa valittua elementtiä kaikkiin taulukon elementteihin.
  • Siirrä kaikki taulukon elementit, jotka ovat suuremmat kuin valitun elementin arvo.
  • Aseta elementti paikalleen
  • Toista vaiheet 2–5, kunnes taulukko on lajiteltu.

Koodi:

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)));

lähtö:

6. Kasalajittelualgoritmi

Kasojen lajittelu on tapa lajitella elementtejä käyttämällä ”kasa” -rakennetta. Menetelmä on melko samanlainen kuin aiemmin keskusteltu valintalajittelu. Nyt saatat miettiä kasoista ja kuinka ne on määritelty, ymmärretään ensin kasat ennen algoritmiin siirtymistä.

Lyhyesti sanottuna kasa on binääripuu, johon on lisätty joitain sääntöjä. Yhden säännön mukaan kasassa puun on oltava täydellinen binaaripuu, mikä tarkoittaa yksinkertaisesti, että on tarpeen täyttää kaikki solmut nykyisellä tasolla ennen uuden lisäämistä. Seuraava kasan sääntö on, että kasan alkuainearvoihin on oltava määritelty lapsi ja vanhemmat.

Pienessä kasassa vanhemman arvon on oltava pienempi kuin hänen lapsensa. Kuten voit arvata, maksimikasassa vanhemman arvon on oltava suurempi kuin hänen lapsensa.

Nyt kun määritelmät ovat poissa käytöstä, katsotaanpa, miten kassalaji toimii:

  • Rakennamme ensin maksimikasan, joka varmistaa, että korkeimman arvon elementti on yläosassa.
  • Kytkemme yläosa kasan viimeisellä elementillä ja poistamme yläosan kasasta ja varastoimme se lajiteltuun ryhmään.
  • Toistamme vaihetta yksi ja kaksi, kunnes kasassa on vain yksi elementti.

Yksi asia, joka on pidettävä mielessä, on se, että Java-kansioita ei tueta luonnollisesti kansissa, siksi meidän on turvauduttava Heaps-sovellusten toteuttamiseen taulukkojen avulla. Kasalajittelutilan tilan monimutkaisuus on O (1), joka on erinomainen, ja vaikka se onkin hieman monimutkaisempi kuin yhdistämis- tai lisäyslaji, kun on kyse ymmärryksestä ja toteutuksesta, mielestäni suorituskyvyn etujen vuoksi on viime kädessä parempi käyttää sitä suuria projekteja.

Koodi:

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);

lähtö:

johtopäätös

Lajittelu on tärkeä osa sovellusten ja verkkosivustojen luomista JavaScriptillä. Nyt kun olet perehtynyt joihinkin tärkeimpiin algoritmeihin työn saamiseksi, sinun pitäisi tuntea olosi luottavaisemmaksi JS Kehitykseen.

Yksi tärkeä seikka, joka pitää mielessä erilaisesta lajittelusta, on se, että sinun ei oikeastaan ​​tarvitse stressata itseäsi liikaa sen suhteen, mitä algoritmia käytetään useimmissa tapauksissa. Nyt kun tietokonelaitteisto on niin tehokas, nykyaikaiset puhelin- ja työpöytäprosessorit eivät riko hikeä lajittelemalla jopa satoja elementtejä muutamassa millisekunnissa. Lajittelualgoritmien muuttaminen voi olla hyödyllistä vain tapauksissa, joissa sinulla on hidasta laitteistoa tai tilanteissa, joissa optimoit jokaisen koodiosion.

Suositellut artikkelit

Tämä on opas algoritmien lajitteluun JavaScript-muodossa. Tässä keskustellaan 6 suosituimmasta JavaScriptin lajittelualgoritmista sekä esimerkkeistä ja koodin toteutuksesta. Voit myös katsoa seuraavia artikkeleita saadaksesi lisätietoja -

  1. JavaScript-kääntäjät
  2. Käännä JavaScript
  3. Johdanto JavaScriptiin
  4. Ruudut Java
  5. Pikalajittelualgoritmit Java-sovelluksessa
  6. Tietorakenteen taulukot
  7. C ++ -algoritmi | Esimerkkejä C ++ -algoritmista

Luokka:

Ohjelmistokehitys