Introduktion till sortering av algoritmer i JavaScript
I likhet med de flesta andra programmeringsspråk kan du stöta på scenarier där du måste sortera vissa nummer i JavaScript i stigande eller fallande ordning. För att få det gjort kan vi använda många algoritmer som Bubble sortering, Selection Sort, Merge sort, Quicksort, etc. Dessa algoritmer skiljer sig inte bara i hur de fungerar men också var och en har sina olika krav vad gäller minne och tid tog, låt oss gräva djupare i några av de viktiga sorteringsalgoritmerna och se hur du kan använda dem i din JavaScript-kod.
Topp 6 sorteringsalgoritmer i JavaScript
Här är några sorteringsalgoritmer i javascript som förklaras nedan med exempel:
1. Bubble Sort Algoritm
Betraktas som ett av de vanligaste verktygen i denna handel, Bubble sort fungerar genom att skapa en slinga som jämför varje objekt i matrisen med en annan artikel. Om den jämförda artikeln är mindre än den till hands byter vi deras platser. Detta fortsätter tills vi har ett pass där inget objekt i matrisen är större än objektet bredvid.
Bubble Sort har O (n 2 ) tidskomplexitet och O (n) rymdkomplexitet.
Koda:
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. Val av sorteringsalgoritm
Nu när vi är klar med att diskutera Bubble Sort Algoritm, låt oss ta en titt på precis som en populär algoritm för sortering som kallas Selection Sort.
Till skillnad från Bubble Sort fokuserar vi på att hitta det minsta värdet i matrisen för att få sorteringen gjort. Här är en steg för steg uppdelning av hur Selection Sort fungerar:
- Vi antar att den första artikeln i matrisen är den minsta.
- Vi jämför denna artikel med nästa artikel i matrisen.
- Om nästa objekt är mindre än det som finns, ställer vi in nästa objekt som det minsta värdet.
- Vi fortsätter att upprepa dessa steg tills vi når slutet av matrisen.
- När vi hittar värde i matrisen som är mindre än den vi började med byter vi deras positioner.
- Vi fortsätter att göra jämförelser och flyttar till nästa artikel. Tills hela matrisen är sorterad.
Precis som Bubble Sort-algoritmen har valet sortering O (n 2 ) tidskomplexitet och O (n) rymdkomplexitet.
Koda:
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. Slå samman sorteringsalgoritm
Liknar Bubble Sort and Selection Sort, Merge sort är en av de populära sorteringsalgoritmerna inom datavetenskap, du kan implementera den på de flesta programmeringsspråk, och den har bra prestanda utan att det är för behövande för resurser.
Merge Sort använder metoden Dela och erövra för att sortera en matris eller en lista över element. Termen delar upp och erövrar betyder att vi delar upp ett stort problem i flera mindre problem och sedan löser vi dessa små problem. När de mindre problemen har löst kombinerar vi resultaten som resulterar i lösningen på det stora problemet.
Att förstå algoritmen är faktiskt enkelt:
- Vi delar upp det givna arrayet i n arrays var och en av dessa matriser innehåller bara ett element.
- Slå samman matriserna för att producera en ny matris.
- Upprepa steg 2 tills det bara finns en grupp som är den sorterade matrisen.
Koda:
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. Snabbsorteringsalgoritm
Quicksort är ett av de mest effektiva sätten att sortera element i datorsystem. Similor för att slå samman sortering, Quicksort fungerar på dividerings- och erövringsalgoritmen. I det här hittar vi ett pivot-objekt i arrayen för att jämföra alla andra element-arrayer mot och sedan flyttar vi objekten på ett sätt där alla objekt före våra valda pivot-objekt är mindre och alla objekt efter pivot-objektet är större i storlek. När vi har gjort det är nyckeln att fortsätta göra det upprepade gånger och vi kommer att ha vår sorterade matris.
Följande är stegen som kan följas för att implementera kvicksortsalgoritm:
- Vi väljer ett element i matrisen och kallar det "Pivot Point"
- Vi startar en pekare som kallas vänsterpekaren från vilken är det första elementet i matrisen.
- På liknande sätt startar vi en pekare som kallas rätt pekare vid det sista objektet i matrisen.
- Om värdet på elementet vid vänsterpekaren är mindre jämfört med den valda vridpunkten, flyttar vi vänsterpekaren åt vänster (lägg till +1 till den) och fortsätter att upprepa det tills värdet vid vänsterpekaren har visat sig vara större än värdet på vridpunkten eller lika med den.
- Om värdet på elementet vid höger pekare i listan är högre än värdet på pivotelementet, lägger vi in högerpekaren till vänster. Upprepa detta tills värdet på högerpekaren är lägre än (eller lika med) pivotens värde.
- När värdet på den vänstra pekaren är mindre än eller lika med värdet på den högra pekaren, byt värdena.
- Flytta högerpekaren till vänster för en, vänsterpekaren till höger för en.
- Upprepa tills vänster- och högerpekarna möts.
Koda:
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. Insertion Sort Algoritm
När det gäller enkel implementering är införingssorter allmänt känd som en av de enklare algoritmerna. I Insertion Sort jämförs elementen i matrisen med varandra och arrangeras sedan i en viss ordning. Detta liknar mycket att ordna kort i ett däck. Namnet införing sortering kommer från processen att plocka ett element och infoga det på rätt plats och sedan upprepa det för alla element.
Så här fungerar algoritmen:
- Det första elementet i matrisen anses redan sorterat.
- Välj nästa element i matrisen.
- Jämför det valda elementet med alla element i matrisen.
- Växla varje element i arrayen som är större än värdet på det valda elementet.
- Sätt i elementet
- Upprepa steg 2 till 5 tills matrisen är sorterad.
Koda:
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 Algoritm
Heap sortering är ett sätt att sortera element genom att använda "Heap" datastrukturen. Metoden är ganska lik den urvalssorteringsteknik som vi diskuterade tidigare. Nu undrar du kanske över Heaps och hur definieras de innan vi kommer till algoritmen, låt oss först förstå högen.
I ett nötskal är en hög en binär träd med några tillagda regler. En regel säger att trädet i högen måste vara ett komplett binärt träd vilket helt enkelt betyder att det är nödvändigt att fylla alla noder på den aktuella nivån innan du lägger till en annan. Nästa regel för högen är att det måste finnas ett definierat förhållande mellan barn och förälder med högvärldens elementvärden.
I en minheap måste värdet på en förälder vara mindre än sina barn. Som du antar måste en förälders värde vara högre än barnet.
Nu när definitionerna är ur vägen, låt oss ta en titt på hur heapsort fungerar:
- Vi bygger först en max hög som ser till att elementet med det högsta värdet är uppe.
- Vi byter toppelementet med det sista elementet i högen och tar bort toppelementet från högen och lagrar det på en sorterad matris.
- Vi upprepar stegen ett och två tills det bara finns ett element kvar i högen.
En sak att tänka på är att Heaps inte stöds naturligt i JavaScript, därför måste vi använda oss av att implementera Heaps med hjälp av matriser. Rymdkomplexiteten hos heap sort är O (1) vilket är utmärkt och även om det är lite mer komplicerat jämfört med sammanslagningssortering eller insättningssortering när det gäller förståelse och implementering, tror jag att prestandafördelarna är i slutändan bättre att använda i stora projekt.
Koda:
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:
Slutsats
Sortering är en viktig del av att skapa applikationer och webbplatser med JavaScript. Nu när du är bekant med några av de viktigaste algoritmerna för att få jobbet gjort, bör du känna dig mer säker på JS Development.
Ett viktigt faktum att tänka på när det gäller olika sortering är att du egentligen inte behöver stressa dig själv för mycket med vilken algoritm du ska använda i de flesta fall. Nu när datormaskinvaran är så kraftfull kommer moderna telefon- och stationära processorer inte att bryta någon svett när det gäller att sortera till och med hundratals element på några millisekunder. Det är bara fall där du sitter fast med långsam hårdvara eller situationer där du optimerar varje enskilt kodavsnitt där att ändra sorteringsalgoritmer kan vara fördelaktigt.
Rekommenderade artiklar
Detta är en guide till sortering av algoritmer i JavaScript. Här diskuterar vi de 6 främsta sorteringsalgoritmerna i javascript tillsammans med exempel och kodimplementering. Du kan också titta på följande artiklar för att lära dig mer -
- JavaScript-kompilatorer
- Omvänd i JavaScript
- Introduktion till JavaScript
- Kvadrater i Java
- Snabbsorteringsalgoritmer i Java
- Matriser i datastruktur
- C ++ algoritm | Exempel på C ++ -algoritm