Inleiding tot sorteeralgoritmen in JavaScript
Net als de meeste andere programmeertalen, kun je scenario's tegenkomen waarin je sommige getallen in JavaScript in oplopende of aflopende volgorde moet sorteren. Om dit voor elkaar te krijgen, kunnen we veel algoritmen gebruiken zoals Bubble sort, Selection Sort, Merge Sort, Quicksort, etc. Deze algoritmen verschillen niet alleen in hoe ze werken, maar ook hebben ze allemaal verschillende eisen qua geheugen en tijd, laten we ga dieper in op enkele belangrijke sorteeralgoritmen en kijk hoe u ze in uw JavaScript-code kunt gebruiken.
Top 6 Sorteeralgoritmen in JavaScript
Hier zijn enkele sorteeralgoritmen in javascript die hieronder worden uitgelegd met voorbeelden:
1. Bubble Sort-algoritme
Bubble wordt beschouwd als een van de meest voorkomende tools van deze branche en werkt door een lus te maken die elk item in de array vergelijkt met een ander item. Als het vergeleken item kleiner is dan het aanwezige exemplaar, wisselen we hun plaatsen. Dit blijft doorgaan totdat we een pass hebben waarbij geen item in de array groter is dan het item dat ernaast staat.
Bubble Sort heeft O (n 2 ) tijdcomplexiteit en O (n) ruimtecomplexiteit.
Code:
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)));
Output:
2. Selectie sorteren algoritme
Nu we klaar zijn met het bespreken van het Bubble Sort-algoritme, laten we eens kijken naar een populair sorteeralgoritme genaamd Selection Sort.
In tegenstelling tot Bubble Sort richten we ons op het vinden van de kleinste waarde in de array om het sorteren te voltooien. Hier is een stap voor stap overzicht van hoe Selection Sort werkt:
- We nemen aan dat het eerste item in de array het kleinste is.
- We vergelijken dit item met het volgende item in de array.
- Als het volgende item kleiner is dan het volgende, stellen we het volgende item in als de kleinste waarde.
- We blijven deze stappen herhalen totdat we het einde van de array bereiken.
- Wanneer we waarde vinden in de array die kleiner is dan degene waarmee we zijn begonnen, wisselen we hun posities.
- We blijven vergelijken en doorgaan naar het volgende item. Totdat de hele array is gesorteerd.
Net als het Bubble Sort-algoritme heeft de selectie-sortering O (n 2 ) tijdcomplexiteit en O (n) ruimtecomplexiteit.
Code:
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; )));
Output:
3. Sorteeralgoritme samenvoegen
Vergelijkbaar met Bubble Sort en Selection Sort, is Merge sort een van de populaire sorteeralgoritmen in de informatica, je kunt het in de meeste programmeertalen implementeren en het heeft goede prestaties zonder dat het te veel middelen vereist.
Sorteer samenvoegen gebruikt de methode Verdeel en Verover om een matrix of een lijst met elementen te sorteren. De term verdeelt en overwint betekent dat we een groot probleem in verschillende kleinere problemen verdelen en vervolgens deze kleine problemen oplossen. Zodra de kleinere problemen zijn opgelost, combineren we de resultaten die resulteren in de oplossing voor het grote probleem.
Het begrijpen van het algoritme is eigenlijk eenvoudig:
- We verdelen de gegeven array in n arrays elk van deze arrays bevat slechts 1 element.
- Voeg de arrays samen om een nieuwe array te produceren.
- Herhaal stap 2 totdat er nog maar 1 array over is, dit is de gesorteerde array.
Code:
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)));
Output:
4. Snel sorteren algoritme
Quicksort is een van de meest efficiënte manieren om elementen in computersystemen te sorteren. Simsor om sortering samen te voegen, Quicksort werkt op het verdeel en heers algoritme. Hierin vinden we een pivotitem in de array om alle andere elementenarrays tegen te vergelijken en vervolgens verplaatsen we de items op een manier waarbij alle items vóór onze geselecteerde pivotitems kleiner zijn en alle items na het pivotitem groter zijn. Zodra we dat hebben gedaan, is de sleutel om het herhaaldelijk te blijven doen en hebben we onze gesorteerde array.
Hieronder volgen de stappen die kunnen worden gevolgd om het quicksort-algoritme te implementeren:
- We selecteren een element van de array en noemen dit "Pivot Point"
- We starten een aanwijzer die de linkeraanwijzer wordt genoemd en die zich bij het eerste element in de array bevindt.
- Op dezelfde manier starten we een aanwijzer die de juiste aanwijzer wordt genoemd bij het laatste item in de array.
- Als de waarde van het element bij de linkerwijzer minder is in vergelijking met het geselecteerde draaipunt, verplaatsen we de linkerwijzer naar links (voeg +1 toe) en blijven we herhalen totdat de waarde bij de linkerwijzer groter wordt gevonden dan de waarde van draaipunt of gelijk daaraan.
- Als de waarde van het element aan de rechterwijzer in de lijst hoger is dan de waarde van het pivot-element, schakelen we de rechterwijzer naar links. Herhaal dit totdat de waarde aan de rechterkant van de aanwijzer lager is dan (of gelijk is aan) de waarde van het draaipunt.
- Wanneer de waarde van de linkerwijzer kleiner is dan of gelijk is aan de waarde van de rechterwijzer, verwisselt u de waarden.
- Verplaats de rechterwijzer één voor één naar links, de linkerwijzer één voor één naar rechts.
- Herhaal dit totdat de linker en rechter wijzers elkaar raken.
Code:
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);
Output:
5. Algoritme voor invoegsortering
Als het gaat om het gemak van implementatie, staat het invoegen van een soort bekend als een van de eenvoudigere algoritmen. In Insertion Sort worden elementen van de array met elkaar vergeleken en vervolgens in een bepaalde volgorde gerangschikt. Dit lijkt erg op het ordenen van kaarten in een kaartspel. De naaminvoegsoort is afkomstig van het proces waarbij een element wordt geplukt en op de juiste plaats wordt ingevoegd en vervolgens voor alle elementen wordt herhaald.
Dit is hoe het algoritme werkt:
- Het eerste element van de array wordt als al gesorteerd beschouwd.
- Kies het volgende element van de array.
- Vergelijk het geselecteerde element met alle elementen in de array.
- Verschuif elk element in de array dat groter is dan de waarde van het geselecteerde element.
- Plaats het element
- Herhaal stap 2 tot 5 totdat de array is gesorteerd.
Code:
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)));
Output:
6. Heap-sorteeralgoritme
Heap-sorteren is een manier om elementen te sorteren met behulp van de 'Heap'-gegevensstructuur. De methode lijkt veel op de selectiesorteertechniek die we eerder hebben besproken. Nu vraag je je misschien af wat Heaps is en hoe ze zijn gedefinieerd, voordat we naar het algoritme gaan, laten we eerst heaps begrijpen.
Kortom, een hoop is een binaire boom met enkele toegevoegde regels. Eén regel stelt dat de boom in heap een complete binaire boom moet zijn, wat simpelweg betekent dat het nodig is om alle knooppunten op het huidige niveau te vullen voordat een andere wordt toegevoegd. De volgende regel voor de heap is dat er een gedefinieerde kind- en ouderrelatie moet zijn met de elementwaarden van de heap.
In een min-heap moet de waarde van een ouder kleiner zijn dan zijn kinderen. Zoals je kunt raden, moet de maximale waarde van een ouder groter zijn dan die van het kind.
Nu de definities uit de weg zijn, laten we eens kijken hoe heapsort werkt:
- We bouwen eerst een maximale heap die ervoor zorgt dat het element met de hoogste waarde bovenaan staat.
- We schakelen het bovenste element met het laatste element van de heap en verwijderen het bovenste element uit de heap en slaan het op in een gesorteerde array.
- We blijven stap één en twee herhalen totdat er nog maar één element in de hoop is.
Een ding om in gedachten te houden is dat Heaps niet native worden ondersteund in JavaScript, daarom moeten we onze toevlucht nemen tot het implementeren van Heaps met behulp van arrays. De ruimtecomplexiteit van heap-sortering is O (1), wat uitstekend is en hoewel het een beetje gecompliceerder is in vergelijking met merge-sortering of invoegsortering als het gaat om begrip en implementatie, denk ik dat het voor prestatievoordelen uiteindelijk beter is om te gebruiken in grote projecten.
Code:
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);
Output:
Conclusie
Sorteren is een belangrijk onderdeel van het maken van applicaties en websites met JavaScript. Nu u bekend bent met enkele van de belangrijkste algoritmen om de klus te klaren, zou u meer vertrouwen moeten hebben in JS Development.
Een belangrijk feit om in gedachten te houden bij verschillende sorteringen, is dat je jezelf niet echt teveel hoeft te benadrukken over welk algoritme je in de meeste gevallen moet gebruiken. Nu de computerhardware zo krachtig is, zullen moderne telefoon- en desktopprocessors geen zweet meer breken bij het sorteren van zelfs honderden elementen in enkele milliseconden. Het zijn alleen gevallen waarin je vastzit aan trage hardware of situaties waarin je elke afzonderlijke sectie code optimaliseert waar het wijzigen van sorteeralgoritmen nuttig kan zijn.
Aanbevolen artikelen
Dit is een gids voor het sorteren van algoritmen in JavaScript. Hier bespreken we de top 6 sorteeralgoritmen in JavaScript, samen met voorbeelden en code-implementatie. U kunt ook de volgende artikelen bekijken voor meer informatie -
- JavaScript-compilers
- Omgekeerd in JavaScript
- Inleiding tot JavaScript
- Vierkanten op Java
- Snel sorteren algoritmen in Java
- Arrays in gegevensstructuur
- C ++ Algoritme | Voorbeelden van C ++ algoritme