Introduksjon til sortering av algoritmer i JavaScript
I likhet med de fleste andre programmeringsspråk, kan du støte på scenarier der du må sortere noen tall i JavaScript i stigende eller synkende rekkefølge. For å få det til, kan vi bruke mange algoritmer som Bubble sort, Selection Sort, Merge sort, Quicksort, etc. Disse algoritmene er ikke bare forskjellige i hvordan de fungerer, men også hver har sine forskjellige krav når det gjelder minne og tid tok, la oss grave dypere i noen av de viktige sorteringsalgoritmene og se hvordan du kan bruke dem i JavaScript-koden.
Topp 6 sorteringsalgoritmer i JavaScript
Her er noen sorteringsalgoritmer i javascript forklart nedenfor med eksempler:
1. Bubble Sort Algorithm
Regnet som et av de vanligste verktøyene i denne bransjen, fungerer Bubble-sort ved å lage en løkke som sammenligner hvert element i matrisen med et annet element. Hvis den sammenlignede varen er mindre enn den på hånden, bytter vi plassene deres. Dette fortsetter til vi har et pass der ingen gjenstander i matrisen er større enn varen som ligger ved siden av.
Bubble Sort har O (n 2 ) tidskompleksitet og O (n) romkompleksitet.
Kode:
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)));
Produksjon:
2. Sorteringsalgoritme
Nå som vi er ferdige med å diskutere Bubble Sort Algorithm, la oss se på akkurat som en populær algoritme for sortering kalt Selection Sort.
I motsetning til Bubble Sort, fokuserer vi på å finne den minste verdien i matrisen for å få sorteringen gjort. Her er en trinnvis oversikt over hvordan Selection Sort fungerer:
- Vi antar at den første varen i matrisen er den minste.
- Vi sammenligner dette elementet med neste element i matrisen.
- Hvis neste element er mindre enn det som er for hånden, setter vi neste element som den nyeste verdien.
- Vi fortsetter å gjenta disse trinnene til vi kommer til slutten av matrisen.
- Når vi finner verdi i matrisen som er mindre enn den vi startet med, bytter vi posisjonene deres.
- Vi fortsetter å gjøre sammenligningene og går videre til neste element. Inntil hele matrisen er sortert.
Akkurat som Bubble Sort-algoritmen har utvalgssorteringen O (n 2 ) tidskompleksitet og O (n) romkompleksitet.
Kode:
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; )));
Produksjon:
3. Slå sammen sorteringsalgoritme
I likhet med Bubble Sort and Selection Sort, Merge sort er en av de populære sorteringsalgoritmene innen informatikk, du kan implementere den på de fleste programmeringsspråk, og den har god ytelse uten at den er for trengende for ressurser.
Merge Sort bruker Divide and conquer-metoden for å sortere en matrise eller en liste over elementer. Begrepet deler og erobrer betyr at vi deler ett stort problem i flere mindre problemer og så løser vi disse små problemene. Når de mindre problemene er løst, kombinerer vi resultatene som resulterer i løsningen på det store problemet.
Det er enkelt å forstå algoritmen:
- Vi deler det gitte arrayet i n arrays hver av disse matriser inneholder bare 1 element.
- Slå sammen gruppene for å produsere et nytt utvalg.
- Gjenta trinn 2 til det bare er en matrise igjen, som vil være den sorterte matrisen.
Kode:
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)));
Produksjon:
4. Rask sorteringsalgoritme
Quicksort er en av de mest effektive måtene å sortere elementer i datasystemer på. Similor for å slå sammen sortering, Quicksort fungerer på skillet og erobre algoritmen. I dette finner vi et pivot-element i matrisen for å sammenligne alle andre element-arrays mot, og så flytter vi elementene på en måte der alle elementene før de valgte pivot-elementene er mindre og alle elementene etter pivot-elementet er større i størrelse. Når vi har gjort det, er nøkkelen å fortsette å gjøre det gjentatte ganger, og vi får sortert utvalg.
Følgende er trinnene som kan følges for å implementere hurtigsorteringsalgoritme:
- Vi velger et element i matrisen og kaller det "Pivot Point"
- Vi starter en peker som kalles venstre peker, og som er ved det første elementet i matrisen.
- På samme måte starter vi en peker som kalles høyre peker på det siste elementet i matrisen.
- Hvis verdien til elementet ved venstre peker er mindre sammenlignet med det valgte pivotpunktet, flytter vi venstre pekeren til venstre (legg +1 til det) og fortsetter å gjenta det til verdien ved venstre pekeren er funnet å være større enn verdien av pivot point eller lik den.
- Hvis verdien til elementet til høyre peker i listen er høyere enn verdien til pivotelementet, modifiserer vi høyre pekeren til venstre. Gjenta dette til verdien til høyre pekeren er lavere enn (eller lik) pivotens verdi.
- Når verdien til venstrepekeren er mindre enn eller lik verdien til høyrepekeren, bytter du verdiene.
- Flytt høyre pekeren til venstre for en, venstre pekeren til høyre for en.
- Gjenta til venstre og høyre pekere møtes.
Kode:
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);
Produksjon:
5. Sett inn sorteringsalgoritme
Når det gjelder enkel implementering, er innsetting sortert kjent som en av de enklere algoritmene. I Insertion Sort blir elementer i matrisen sammenlignet med hverandre og deretter ordnet i en bestemt rekkefølge. Dette ligner veldig på å ordne kort i en kortstokk. Navnetinnsetting kommer fra prosessen med å plukke et element og sette det inn på riktig sted og deretter gjenta det for alle elementene.
Slik fungerer algoritmen:
- Det første elementet i matrisen anses som allerede sortert.
- Velg neste element i matrisen.
- Sammenlign det valgte elementet med alle elementene i matrisen.
- Skift hvert element i matrisen som er større enn verdien til det valgte elementet.
- Sett inn elementet
- Gjenta trinn 2 til 5 til matrisen er sortert.
Kode:
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)));
Produksjon:
6. Heap Sort algoritme
Heap sortering er en måte å sortere elementer ved å bruke "Heap" datastrukturen. Metoden er ganske lik utvalgssorteringsteknikken vi diskuterte tidligere. Nå lurer du kanskje på Heaps og hvordan er de definert, før vi kommer til algoritmen, la oss først forstå heaps.
I et nøtteskall er en haug et binært tre med noen lagt regler. Én regel sier at treet i hop, må være et komplett binært tre som ganske enkelt betyr at det er nødvendig å fylle alle noder på det nåværende nivået før du legger til et nytt. Den neste regelen for dyngen er at det må være et definert forhold mellom barn og foreldre med elementens verdier på dyngen.
På en minheap må verdien av en forelder være mindre enn barna. Som du kan gjette i en maksimal haug, må verdien av en forelder være større enn barnet sitt.
Nå som definisjonene er ute av veien, la oss se på hvordan heapsort fungerer:
- Vi bygger først en maksimal haug som sørger for at elementet med høyeste verdi er øverst.
- Vi bytter toppelementet med det siste elementet i dyngen og fjerner toppelementet fra dyngen og lagrer det på en sortert matrise.
- Vi fortsetter å gjenta trinn ett og to til det bare er ett element som er igjen i dyngen.
En ting å huske er at Heaps ikke støttes i JavaScript, derfor må vi ta i bruk implementering av Heaps ved bruk av matriser. Plasskompleksiteten til heap sort er O (1), som er utmerket, og selv om det er litt mer komplisert sammenlignet med sammenslåingssortering eller innsettingssortering når det kommer til forståelse og implementering, tror jeg for ytelsesfordeler er det til slutt bedre å bruke i store prosjekter.
Kode:
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);
Produksjon:
Konklusjon
Sortering er en viktig del av å lage applikasjoner og nettsteder med JavaScript. Nå som du er kjent med noen av de viktigste algoritmene for å få jobben gjort, bør du føle deg mer trygg på JS Development.
Et viktig faktum å huske på om ulike sortering er at du ikke egentlig trenger å stresse deg selv for mye med hensyn til hvilken algoritme du skal bruke i de fleste tilfeller. Nå som datamaskinvaren er så kraftig, vil ikke moderne telefon- og stasjonære prosessorer ødelegge svette ved å sortere til og med hundrevis av elementer på noen få millisekunder. Det er bare tilfeller hvor du sitter fast med treg maskinvare eller situasjoner der du optimaliserer hver eneste del av koden der det kan være en fordel å endre sorteringsalgoritmer.
Anbefalte artikler
Dette er en guide til sortering av algoritmer i JavaScript. Her diskuterer vi de 6 beste sorteringsalgoritmene i javascript sammen med eksempler og implementering av kode. Du kan også se på følgende artikler for å lære mer -
- JavaScript-kompilatorer
- Omvendt i JavaScript
- Introduksjon til JavaScript
- Firkanter i Java
- Rask sorteringsalgoritmer i Java
- Arrays i datastruktur
- C ++ algoritme | Eksempler på C ++ algoritme