Sortarea listelor de date este o parte atât de crucială a procesării în aplicații.
Este util pentru afișarea datelor și efectuarea de căutări. Prin urmare, nu este surprinzător faptul că orice inginer de software bun ar trebui să știe cum să sorteze matrice. Acest articol explică unii dintre cei mai comuni algoritmi pentru sortarea matricelor în JavaScript.
Cuprins
Ce este sortarea și de ce este utilă?
Sursă: Unsplash
Sortarea este organizarea sistematică a valorilor după o anumită ordine. Această ordine poate fi descendentă sau ascendentă. Sortarea matricelor în JavaScript este utilă, deoarece permite ca datele să fie afișate mai semnificativ.
De exemplu, o persoană poate dori să vadă mai întâi fișierele sortate cu cele mai recente fișiere sau produsele sortate după preț. De asemenea, este util pentru efectuarea unei căutări binare pe date, care funcționează numai cu date sortate.
Deși există funcții și biblioteci care vă ajută să sortați cu ușurință datele, trebuie totuși să știți cum funcționează sortarea sub capotă pentru codificarea interviurilor sau când trebuie să scrieți cod de nivel scăzut.
Algoritmi de sortare a matricelor JavaScript
Sortare cu bule
Bubble Sort este, fără îndoială, cel mai ușor algoritm de înțeles și implementat. Funcționează prin bucla prin matrice într-o trecere. Cu fiecare trecere, ne deplasăm prin matrice, de la început până la sfârșit, comparând două elemente adiacente. Dacă elementele sunt în ordinea greșită, le schimbăm.
Efectuăm n treceri unde n este numărul de elemente din tablou. La fiecare trecere, matricea este sortată începând din dreapta. Pseudocodul pentru algoritmul de sortare a numerelor în ordine crescătoare este următorul:
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.
Traducându-l în JavaScript, codul ar arăta astfel:
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;
}
Pentru a înțelege mai bine ce se întâmplă, aș recomanda adăugarea unui console.logs în cele două bucle pentru a vedea cum se modifică matricea cu fiecare trecere.
În codul de mai jos, am modificat funcția de sortare pentru a adăuga console.logs în cele două bucle. De asemenea, am creat o matrice mică nesortată pe care am sortat-o folosind funcția de sortare.
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);
Rezultatul rulării codului de mai sus ar fi:
Sortarea cu bule are o complexitate de timp Big O de O(n ^ 2). Acest lucru se datorează faptului că efectuează n treceri, care circulă prin matrice pentru fiecare trecere. Prin urmare, nu se scalează bine. Cu toate acestea, are o complexitate spațială de O(1), deoarece modifică elementele matricei la locul lor.
Sortare prin inserare
Sortarea prin inserție este un algoritm popular de sortare a matricei JavaScript. Să presupunem că folosim sortarea prin inserare pentru a sorta valorile în ordine crescătoare. Algoritmul funcționează prin alegerea unui număr, pe care îl vom numi num. Apoi mută num la stânga până când fiecare alt număr la stânga lui num este mai mic decât num. Toate numerele vor fi sortate dacă acest lucru se face de la al doilea element până la sfârșit. Iată o descriere în pseudocod.
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
Și acum, pseudocodul implementat în JavaScript este după cum urmează.
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;
}
Ca și în cazul Sortare cu bule, adăugarea console.logs vă ajută să vizualizați ce se întâmplă. Fragmentul de cod de mai jos vă arată Sortarea prin inserare la locul de muncă.
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);
Și rularea fragmentului de mai sus dă următorul rezultat:
Merge Sort
În timp ce Sortarea prin inserție și Sortarea cu bule se scalează în timp patratic, Sortarea prin îmbinare se scalează în timp cvasi-liniar. Are o complexitate de timp de O(n * log(n)).
Sortarea prin îmbinare utilizează strategia împărțiți și cuceriți. Matricea este împărțită în mod repetat în matrice mai mici de câte 1 element fiecare. După împărțire, acestea sunt apoi fuzionate înapoi.
Împărțirea este recursivă, astfel încât matricea poate fi reasamblată ulterior.
La îmbinarea matricei înapoi, subbaryurile sunt îmbinate în ordine. Îmbinarea se face în același mod în care ați îmbina o matrice sortată. Pseudocodul pentru a face acest lucru este scris mai jos:
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
Implementarea acestuia în JavaScript ar produce următoarele:
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));
}
Dacă rulați codul cu un exemplu de matrice, ar trebui să funcționeze.
Sortare rapida
La fel ca Merge Sort, Quick Sort se bazează pe strategia împărțiți și cuceriți. Algoritmul selectează un element pivot. Apoi, mută toate elementele mai mari decât pivotul spre dreapta și mai mici decât pivotul spre stânga. Odată făcut acest lucru, pivotul va fi în poziția corectă.
Pentru a muta elemente în jurul pivotului, algoritmul începe prin mutarea pivotului la capătul matricei.
După ce o mutam, folosim un indicator pentru a bucla din stânga matricei, căutând primul număr mai mare decât pivotul. Simultan, folosim o altă buclă de pointer din dreapta matricei, căutând primul număr mai mic decât pivotul. Odată ce ambele numere au fost identificate, le schimbăm. Această procedură se repetă până când indicatorul din stânga este mai mare decât indicatorul din dreapta.
Când ne oprim, schimbăm cel mai mare dintre ultimele două numere schimbate cu pivotul. În acest moment, pivotul va fi în poziția corectă; numerele mai mici decât pivotul vor fi la stânga, în timp ce cele mai mari vor fi la dreapta.
Această procedură se repetă recursiv pentru sub-matricele din stânga și din dreapta pivotului până când sub-matricele au rămas un singur element.
Iată pseudocodul pentru sortarea rapidă:
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
Și conversia acestuia în 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;
}
Sortarea unui exemplu de matrice cu Sortare rapidă în Node.js ar trebui să producă următoarele:
În cel mai bun caz, Quicksort rulează în complexitate temporală cvasi-liniară. Utilizarea spațiului în Sortare rapidă crește și logaritmic. Prin urmare, este relativ eficient în comparație cu alți algoritmi de sortare a matricei JavaScript.
Sfaturi pentru interviurile dvs. de codificare
❇️ Practica este cheia. Vă ajută să învățați diferiți algoritmi, dar, mai important, vă ajută să dezvoltați abilitățile de rezolvare a problemelor și de gândire computațională. Puteți exersa și pe platforme precum Leetcode și AlgoExpert.
❇️ Încercați mai întâi să rezolvați problema. În loc să sari direct la soluție, încearcă să o rezolvi, deoarece te ajută să-ți dezvolți abilitățile de rezolvare a problemelor.
❇️ Dacă o problemă durează prea mult, sari la soluție; mai poți învăța să rezolvi problema din soluție. Majoritatea platformelor de învățare oferă soluții. ChatGPT sau Google Bard sunt, de asemenea, utile pentru explicarea conceptelor.
❇️ De asemenea, nu scrie cod imediat; tablă soluțiile și gândiți-vă la ele înainte de a scrie cod. Pseudocodul este, de asemenea, o modalitate utilă de a scrie rapid ideile.
Concluzie
În acest articol, am acoperit cei mai populari algoritmi de sortare. Cu toate acestea, învățarea tuturor acestor lucruri poate părea copleșitoare la început. Prin urmare, recomand de obicei să amestecați diverse surse în loc să mă bazez doar pe una. Codare fericită!
Apoi, verificați înțelegerea funcției sortate în Python.