Introduktion til sortering af algoritmer i JavaScript

I lighed med de fleste andre programmeringssprog kan du løbe ind i scenarier, hvor du skal sortere nogle numre i JavaScript i stigende eller faldende rækkefølge. For at få det til, kan vi bruge mange algoritmer såsom Bubble sort, Selection Sort, Merge sort, Quicksort osv. Disse algoritmer adskiller sig ikke kun i, hvordan de fungerer, men også hver har sine forskellige krav med hensyn til hukommelse og tid tog, lad os grave dybere ned i nogle af de vigtige sorteringsalgoritmer og se, hvordan du kan bruge dem i din JavaScript-kode.

Top 6 sorteringsalgoritmer i JavaScript

Her er nogle sorteringsalgoritmer i javascript forklaret nedenfor med eksempler:

1. Bubble Sort Algoritme

Anset for at være et af de mest almindelige værktøjer i denne handel, fungerer Bubble-sortering ved at oprette en løkke, der sammenligner hvert element i matrixen med et andet emne. Hvis den sammenlignede vare er mindre end den, der er til rådighed, bytter vi deres pladser. Dette fortsætter, indtil vi har et pass, hvor intet element i matrixen er større end det, der er ved siden af.

Bubble Sort har O (n 2 ) tidskompleksitet og O (n) space complexity.

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

Produktion:

2. Valg af sorteringsalgoritme

Nu hvor vi er færdige med at diskutere Bubble Sort Algoritme, lad os se på lige som en populær algoritme til sortering kaldet Selection Sort.

I modsætning til Bubble Sort, fokuserer vi på at finde den mindste værdi i matrixen for at få sorteringen udført. Her er en trin for trin oversigt over, hvordan valg af sortering fungerer:

  • Vi antager det første emne i matrixen som det mindste.
  • Vi sammenligner dette punkt med det næste punkt i matrixen.
  • Hvis det næste element er mindre end det, der er ved hånden, indstiller vi det næste punkt som den nyeste værdi.
  • Vi gentager disse trin, indtil vi når slutningen af ​​matrixen.
  • Når vi finder værdi i den matrix, der er mindre end den, vi startede med, bytter vi deres positioner.
  • Vi fortsætter med at sammenligne og går videre til det næste punkt. Indtil hele matrixen er sorteret.

Ligesom Bubble Sort-algoritmen har udvælgelsessorteringen O (n 2 ) tidskompleksitet og O (n) pladskompleksitet.

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

Produktion:

3. Flet sorteringsalgoritme

Ligesom Bubble Sort and Selection Sort, Merge sort er en af ​​de populære sorteringsalgoritmer inden for datalogi, du kan implementere den på de fleste programmeringssprog, og den har god ydeevne, uden at den er for trang til ressourcer.

Flet sortering bruger Opdel og erobre metoden til at sortere en matrix eller en liste over elementer. Udtrykket opdeler og erobrer betyder, at vi opdeler et stort problem i flere mindre problemer, og så løser vi disse små problemer. Når de mindre problemer er løst, kombinerer vi de resultater, der resulterer i løsningen på det store problem.

At forstå algoritmen er faktisk enkel:

  • Vi deler det givne array i n arrays hver af disse arrays indeholder kun 1 element.
  • Flet arrayerne for at producere en ny matrix.
  • Gentag trin 2, indtil der kun er en array tilbage, hvilket vil være den sorterede array.

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

Produktion:

4. Hurtig sorteringsalgoritme

Quicksort er en af ​​de mest effektive måder til sortering af elementer i computersystemer. Similor for at flette sortering, Quicksort fungerer på split og erobre algoritmen. I dette finder vi et pivot-element i arrayet for at sammenligne alle andre elementarrays mod, og derefter flytter vi elementerne på en måde, hvor alle elementer før vores valgte pivot-emner er mindre, og alle elementer efter pivot-emnet er større i størrelse. Når vi har gjort det, er nøglen at fortsætte med at gøre det gentagne gange, og vi får vores sorterede matrix.

Følgende er de trin, der kan følges for at implementere quicksort-algoritmen:

  • Vi vælger et element i matrixen og kalder det "Pivot Point"
  • Vi starter en pointer kaldet den venstre pointer, hvorfra er det første element i arrayet.
  • Tilsvarende starter vi en markør, der kaldes den rigtige markør ved det sidste punkt i arrayet.
  • Hvis værdien af ​​elementet ved den venstre markør er mindre sammenlignet med det valgte drejepunkt, flytter vi den venstre markør til venstre (tilføj +1 til det) og fortsætter med at gentage det, indtil værdien ved den venstre markør viser sig at være større end den værdien af ​​drejepunktet eller lig med det.
  • Hvis værdien af ​​elementet ved højre markør på listen er højere end værdien af ​​pivotelementet, indstiller vi højre markør til venstre. Gentag dette, indtil værdien ved højre markør er lavere end (eller lig med) pivotens værdi.
  • Når værdien af ​​den venstre markør er mindre end eller lig med den højre pointer, skal du skifte værdier.
  • Flyt den højre markør til venstre for en, venstre markøren til højre ved en.
  • Gentag, indtil venstre og højre peger mødes.

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

Produktion:

5. Indsættelsessorteringsalgoritme

Når det kommer til let implementering, er indsættelsessort kendt som en af ​​de enklere algoritmer. I indsættelsessorter sammenlignes elementer i matrixen med hinanden og arrangeres derefter i en bestemt rækkefølge. Dette ligner meget at arrangere kort i et dæk. Navnetindsættelsessort kommer fra processen med at vælge et element og indsætte det på det rigtige sted og derefter gentage det for alle elementer.

Sådan fungerer algoritmen:

  • Det første element i arrayet betragtes som allerede sorteret.
  • Vælg det næste element i matrixen.
  • Sammenlign det valgte element med alle elementer i matrixen.
  • Skift hvert element i arrayet, der er større end værdien af ​​det valgte element.
  • Indsæt elementet
  • Gentag trin 2 til 5, indtil arrayet er sorteret.

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

Produktion:

6. Heap Sort Algoritme

Heap sortering er en måde at sortere elementer ved hjælp af "Heap" datastrukturen. Metoden ligner temmelig meget den udvælgelsessorteringsteknik, vi diskuterede tidligere. Nu undrer du dig måske over Heaps, og hvordan defineres de, før vi kommer til algoritmen, lad os først forstå heaps.

I en nøddeskal er en bunke et binært træ med nogle tilføjede regler. Én regel siger, at træet skal i hop, være et komplet binært træ, hvilket ganske enkelt betyder, at det er nødvendigt at udfylde alle noder på det aktuelle niveau, før du tilføjer et andet. Den næste regel for dyngen er, at der skal være et defineret forhold mellem børn og forældre med elementens værdier for dyngen.

I en minheap skal værdien af ​​en forælder være mindre end dens børn. Som du kan gætte, skal værdien af ​​en forælder være større end dets barn i en maksimal bunke.

Nu hvor definitionerne er ude af vejen, lad os se på, hvordan heapsort fungerer:

  • Vi bygger først en maksimal bunke, der sikrer, at elementet med den højeste værdi er øverst.
  • Vi skifter det øverste element med det sidste element i dyngen og fjerner det øverste element fra dyngen og opbevarer det i en sorteret matrix.
  • Vi gentager trin et og to, indtil der kun er et element tilbage i dyngen.

Én ting at huske er, at Heaps ikke støttes oprindeligt i JavaScript, derfor er vi nødt til at benytte os af at implementere Heaps ved hjælp af arrays. Rumkompleksiteten i heap sort er O (1), hvilket er fremragende, og selvom det er en smule mere kompliceret sammenlignet med sammenfletningssortering eller indsættelsessortering, når det kommer til forståelse og implementering, synes jeg, for ydelsesfordele, er det i sidste ende bedre at bruge i store projekter.

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

Produktion:

Konklusion

Sortering er en vigtig del af oprettelsen af ​​applikationer og websteder med JavaScript. Nu hvor du er fortrolig med nogle af de vigtigste algoritmer for at få jobbet gjort, skal du føle dig mere sikker på JS Development.

En vigtig kendsgerning at huske på om forskellige sortering er, at du ikke behøver at stresse dig selv for meget med hensyn til hvilken algoritme du skal bruge i de fleste tilfælde. Nu hvor computerhardwaren er så kraftig, vil moderne telefon- og desktopprocessorer ikke ødelægge sved ved at sortere endda hundreder af elementer i et par millisekunder. Det er kun tilfælde, hvor du sidder fast med langsom hardware eller situationer, hvor du optimerer hvert enkelt kodesnit, hvor det kan være fordelagtigt at ændre sorteringsalgoritmer.

Anbefalede artikler

Dette er en guide til sortering af algoritmer i JavaScript. Her diskuterer vi de top 6 sorteringsalgoritmer i javascript sammen med eksempler og kodeimplementering. Du kan også se på de følgende artikler for at lære mere -

  1. JavaScript-kompilatorer
  2. Omvendt i JavaScript
  3. Introduktion til JavaScript
  4. Firkanter i Java
  5. Hurtig sorteringsalgoritmer i Java
  6. Arrays i datastruktur
  7. C ++ algoritme | Eksempler på C ++ algoritme

Kategori:

Softwareudvikling