Sortering av datalister er en så viktig del av behandlingen i søknader.
Det er nyttig for å vise data og utføre søk. Det er derfor ingen overraskelse at enhver god programvareingeniør bør vite hvordan man sorterer matriser. Denne artikkelen forklarer noen av de vanligste algoritmene for sortering av arrays i JavaScript.
Innholdsfortegnelse
Hva er sortering, og hvorfor er det nyttig?
Kilde: Unsplash
Sortering er systematisk organisering av verdier etter en eller annen rekkefølge. Denne rekkefølgen kan være synkende eller stigende. Sortering av matriser i JavaScript er nyttig siden det gjør at data kan vises mer meningsfullt.
For eksempel kan en person ønske å se filer sortert med de nyeste filene først eller produkter sortert etter pris. Det er også nyttig for å utføre binært søk på data, som kun fungerer med sorterte data.
Selv om det er funksjoner og biblioteker som hjelper deg med å sortere data enkelt, må du fortsatt vite hvordan sortering fungerer under panseret for å kode intervjuer eller når du må skrive lavnivåkode.
JavaScript Array Sort Algoritmer
Boblesortering
Bubble Sort er uten tvil den enkleste algoritmen å forstå og implementere. Det fungerer ved å gå gjennom arrayet i et pass. For hvert pass beveger vi oss gjennom matrisen, fra start til slutt, og sammenligner to tilstøtende elementer. Hvis elementene er i feil rekkefølge, bytter vi dem.
Vi utfører n passeringer der n er antall elementer i matrisen. For hvert pass sorteres matrisen fra høyre. Pseudokoden for algoritmen for å sortere tall i stigende rekkefølge er som følger:
1. Let n be the number of elements in the array 2. Loop n times, keeping count of the loops using i (doing the following in each loop) a. loop the array from the second element to the (n - i)th element b. if the previous element is greater than the current element, swap them.
Når du oversetter det til JavaScript, vil koden se slik ut:
function sort(arr) {
const n = arr.length;
for (let i = 0; i < n; i++) {
for (let j = 1; j < n - i; j++) {
if (arr[j - 1] > arr[j]) {
const temp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}
For bedre å forstå hva som skjer, vil jeg anbefale å legge til en console.logs inne i de to løkkene for å se hvordan matrisen endres for hvert pass.
I koden nedenfor har jeg endret sorteringsfunksjonen for å legge til console.logs inne i de to løkkene. Jeg har også laget en liten usortert matrise som jeg sorterte ved hjelp av sorteringsfunksjonen.
function sort(arr) {
const n = arr.length;
for (let i = 0; i < n; i++) {
console.log(`Pass: ${i}`);
for (let j = 1; j < n - i; j++) {
if (arr[j - 1] > arr[j]) {
const temp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = temp;
}
console.log(arr);
}
}
return arr;
}
const array = [9, 2, 7, 4, 1];
sort(array);
console.log(array);
Resultatet av å kjøre koden ovenfor vil være:
Boblesortering har en Big O-tidskompleksitet på O(n ^ 2). Dette er fordi den utfører n passeringer, som går gjennom arrayet for hver pass. Derfor skalerer den ikke godt. Imidlertid har den en romkompleksitet på O(1) siden den modifiserer array-elementene på plass.
Innsettingssortering
Insertion sort er en populær JavaScript-array-sorteringsalgoritme. Anta at vi bruker innsettingssortering for å sortere verdier i stigende rekkefølge. Algoritmen fungerer ved å velge et tall, som vi vil kalle num. Den flytter deretter num til venstre til annethvert tall til venstre for num er mindre enn num. Alle tall vil bli sortert hvis dette gjøres fra det andre elementet til slutten. Her er en beskrivelse i pseudokode.
1. Let n be the number of elements in the array
2. Loop i from 1 to n - 1 (start from the second element)
a. Set currentElement to array[i]
b. Set j to i - 1
c. While j >= 0 and array[j] > current_element
i. Move array[j] to array[j+1]
ii. Decrement j by 1
d. Set array[j+1] to current_element
Og nå er pseudokoden implementert i JavaScript som følger.
function insertionSort(array) {
const n = array.length;
for (let i = 1; i < n; i++) {
const currentElement = array[i];
let j = i - 1;
while (j >= 0 && array[j] > currentElement) {
array[j + 1] = array[j];
j -= 1;
}
array[j + 1] = currentElement;
}
return array;
}
Som med Bubble Sort, hjelper det å legge til console.logs deg med å visualisere hva som skjer. Kodebiten nedenfor viser deg Insertion Sort på jobben.
function sort(array) {
const n = array.length;
for (let i = 1; i < n; i++) {
const currentElement = array[i];
let j = i - 1;
console.log("Placing element:", currentElement);
while (j >= 0 && array[j] > currentElement) {
array[j + 1] = array[j];
j -= 1;
}
array[j + 1] = currentElement;
console.log("Placed it at position:", j + 1);
console.log(array);
}
return array;
}
const array = [4, 1, 2, 5, 3];
sort(array);
Og å kjøre kodebiten ovenfor gir følgende resultat:
Slå sammen sortering
Mens innsettingssortering og boblesortering skalerer i kvadratisk tid, skalerer Merge Sort i kvasi-lineær tid. Den har en tidskompleksitet på O(n * log(n)).
Slå sammen sortering bruker skille og hersk-strategien. Matrisen er gjentatte ganger delt inn i mindre matriser med 1 element hver. Etter delingen slås de så sammen tilbake.
Delingen er rekursiv slik at matrisen kan settes sammen igjen etterpå.
Når du slår sammen matrisen tilbake, slås subarrayene sammen i rekkefølge. Sammenslåingen gjøres på samme måte som du ville slått sammen en sortert matrise. Pseudokoden for å gjøre det er skrevet nedenfor:
1. If the length of the array is 1 or less, return the array (base case)
2. Find the middle index:
a. Set mid to the floor of (length of the array / 2)
3. Divide the array into two subarrays:
a. Create leftArray and copy the first half of the array into it (from index 0 to mid)
b. Create rightArray and copy the second half of the array into it (from index mid+1 to the end)
4. Recursively call MergeSort on leftArray
5. Recursively call MergeSort on rightArray
6. Merge the two sorted subarrays:
a. Create an empty resultArray
b. While both leftArray and rightArray are not empty:
i. If the first element in leftArray is less than or equal to the first element in rightArray, append it to resultArray
ii. Otherwise, append the first element in rightArray to resultArray
c. Append any remaining elements in leftArray to resultArray (if any)
d. Append any remaining elements in rightArray to resultArray (if any)
7. Return resultArray
Implementering av det i JavaScript vil gi følgende:
function sort(array) {
// Base case in which we stop subdividing the array
if (array.length == 1) {
return array;
}
// Finding the middle point of the array
const m = Math.round(array.length / 2);
// Divide the array into two halves
const leftUnsorted = array.slice(0, m);
const rightUnsorted = array.slice(m);
// Recursively call merge sort
const leftSorted = sort(leftUnsorted);
const rightSorted = sort(rightUnsorted);
// Return a merged sorted array
return merge(leftSorted, rightSorted);
}
function merge(left, right) {
// Merge two sorted lists
let result = [];
let leftIndex = 0;
let rightIndex = 0;
while (leftIndex < left.length && rightIndex < right.length) {
if (left[leftIndex] < right[rightIndex]) {
result.push(left[leftIndex]);
leftIndex += 1;
} else {
result.push(right[rightIndex]);
rightIndex += 1;
}
}
return result.concat(left.slice(leftIndex), right.slice(rightIndex));
}
Hvis du kjører koden med en eksempelmatrise, bør den fungere.
Rask sortering
I likhet med Merge Sort, er Quick Sort avhengig av del-og-hersk-strategien. Algoritmen velger et pivotelement. Deretter flytter den alle elementer større enn pivoten til høyre og mindre enn pivoten til venstre. Når dette er gjort, vil pivoten være i riktig posisjon.
For å flytte elementer rundt pivoten, starter algoritmen med å flytte pivoten til slutten av matrisen.
Etter å ha flyttet den, bruker vi en peker til å løkke fra arrayets venstre side, og ser etter det første tallet som er større enn pivoten. Samtidig bruker vi en annen pekersløyfe fra arrayets høyre side, og ser etter det første tallet som er mindre enn pivoten. Når begge numrene er identifisert, bytter vi dem. Denne prosedyren gjentas til pekeren fra venstre er større enn pekeren til høyre.
Når vi stopper, bytter vi det største av de to tallene som sist ble byttet med pivoten. På dette tidspunktet vil pivoten være i riktig posisjon; Tall mindre enn pivoten vil være til venstre, mens de større vil være til høyre.
Denne prosedyren gjentas rekursivt for sub-arrayene til venstre og høyre for pivoten inntil sub-arrayene har bare ett element igjen.
Her er pseudokoden for rask sortering:
1. If lessThanPointer is less than greaterThanPointer:
a. Choose a pivot element from the array
b. Move elements such that elements less are to the left and elements greater are to the right:
c. Recursively call Quicksort on leftSubarray
d. Recursively call Quicksort on rightSubarray
Og konvertere det til JavaScript:
function sort(array, low, high) {
if (low < high) {
// Choose the pivot index and partition the array
const pivotIndex = move(array, low, high);
// Recursively sort the subarrays to the left and right of the pivot
sort(array, low, pivotIndex - 1);
sort(array, pivotIndex + 1, high);
}
}
function move(array, low, high) {
// Select the pivot element (in this case, the last element)
const pivotElement = array[high];
// Initialize the index for the smaller element
let i = low - 1;
for (let j = low; j < high; j++) {
// If the current element is less than or equal to the pivot, swap it with the element at index i+1
if (array[j] <= pivotElement) {
i += 1;
const temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
// Swap the pivot element into its correct position
const temp = array[i];
array[i] = array[j];
array[j] = temp;
// Return the index of the pivot element
return i + 1;
}
Sortering av en eksempelmatrise med hurtigsortering i Node.js bør gi følgende:
I beste fall kjører Quicksort i kvasi-lineær tidskompleksitet. Plassbruken i Quick Sort skaleres også logaritmisk. Derfor er det relativt effektivt sammenlignet med andre JavaScript-array-sorteringsalgoritmer.
Tips for dine kodeintervjuer
❇️ Øvelse er nøkkelen. Det hjelper deg å lære forskjellige algoritmer, men enda viktigere, det hjelper deg med å utvikle problemløsnings- og beregningsmessige tenkningsferdigheter. Du kan også øve på plattformer som Leetcode og AlgoExpert.
❇️ Prøv å løse problemet først. I stedet for å hoppe rett til løsningen, prøv å løse den, siden det hjelper deg med å utvikle dine problemløsningsevner.
❇️ Hvis et problem tar for lang tid, hopp til løsningen; du kan fortsatt lære å løse problemet fra løsningen. De fleste plattformer for læring tilbyr løsninger. ChatGPT eller Google Bard er også nyttige for å forklare konsepter.
❇️ Ikke skriv kode umiddelbart; tavle løsningene dine og tenk gjennom dem før du skriver kode. Pseudokode er også en nyttig måte å skrive ned ideer raskt.
Konklusjon
I denne artikkelen dekket vi de mest populære sorteringsalgoritmene. Å lære alt dette kan imidlertid virke overveldende i begynnelsen. Derfor anbefaler jeg vanligvis å blande ulike kilder i stedet for å bare stole på én. Lykke til med koding!
Deretter kan du sjekke forståelsen av sortert funksjon i Python.