Sortowanie list danych jest niezwykle istotną częścią przetwarzania w aplikacjach.
Jest przydatny do wyświetlania danych i przeprowadzania wyszukiwania. Nic więc dziwnego, że każdy dobry inżynier oprogramowania powinien wiedzieć, jak sortować tablice. W tym artykule wyjaśniono niektóre z najpopularniejszych algorytmów sortowania tablic w JavaScript.
Spis treści:
Co to jest sortowanie i dlaczego jest przydatne?
Źródło: Usuń rozpryski
Sortowanie to systematyczne organizowanie wartości według pewnego porządku. Kolejność ta może być malejąca lub rosnąca. Sortowanie tablic w JavaScript jest przydatne, ponieważ umożliwia bardziej znaczące wyświetlanie danych.
Na przykład użytkownik może chcieć, aby pliki były posortowane najpierw według najnowszych plików, a produkty posortowane według ceny. Przydaje się również do wyszukiwania binarnego danych, które działa tylko w przypadku danych posortowanych.
Chociaż istnieją funkcje i biblioteki ułatwiające sortowanie danych, nadal musisz wiedzieć, jak sortowanie działa pod maską podczas rozmów kwalifikacyjnych lub gdy musisz napisać kod niskiego poziomu.
Algorytmy sortowania tablicy JavaScript
Sortowanie bąbelkowe
Sortowanie bąbelkowe jest prawdopodobnie najłatwiejszym algorytmem do zrozumienia i wdrożenia. Działa poprzez pętlę przez tablicę w przebiegu. Z każdym przejściem poruszamy się po tablicy od początku do końca, porównując dwa sąsiednie elementy. Jeśli elementy są w złej kolejności, zamieniamy je.
Wykonujemy n przebiegów, gdzie n jest liczbą elementów tablicy. Przy każdym przejściu tablica jest sortowana zaczynając od prawej strony. Pseudokod algorytmu sortującego liczby w kolejności rosnącej jest następujący:
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.
Tłumacząc to na JavaScript, kod wyglądałby tak:
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;
}
Aby lepiej zrozumieć, co się dzieje, polecam dodać plik console.logs do obu pętli, aby zobaczyć, jak tablica zmienia się przy każdym przebiegu.
W poniższym kodzie zmodyfikowałem funkcję sortowania, dodając plik console.logs do obu pętli. Utworzyłem także małą nieposortowaną tablicę, którą posortowałem za pomocą funkcji sortowania.
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);
Efektem uruchomienia powyższego kodu będzie:
Sortowanie bąbelkowe ma złożoność czasową Big O wynoszącą O(n ^ 2). Dzieje się tak, ponieważ wykonuje n przebiegów, które dla każdego przejścia wykonują pętlę przez tablicę. Dlatego nie skaluje się dobrze. Ma jednak złożoność przestrzenną O(1), ponieważ modyfikuje elementy tablicy na miejscu.
Sortowanie przez wstawianie
Sortowanie przez wstawianie to popularny algorytm sortowania tablic w JavaScript. Załóżmy, że używamy sortowania przez wstawianie do sortowania wartości w kolejności rosnącej. Algorytm działa poprzez wybranie liczby, którą nazwiemy num. Następnie przesuwa num w lewo, aż każda inna liczba na lewo od num będzie mniejsza niż num. Wszystkie liczby zostaną posortowane, jeśli zostanie to zrobione od drugiego elementu do końca. Oto opis w pseudokodzie.
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
A teraz pseudokod zaimplementowany w JavaScript wygląda następująco.
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;
}
Podobnie jak w przypadku sortowania bąbelkowego, dodanie pliku console.logs pomaga w wizualizacji tego, co się dzieje. Poniższy fragment kodu przedstawia działanie sortowania przez wstawianie.
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);
Uruchomienie powyższego fragmentu daje następujący wynik:
Sortowanie przez scalanie
Podczas gdy sortowanie przez wstawianie i sortowanie bąbelkowe skalują się w czasie kwadratowym, sortowanie przez scalanie skaluje się w czasie quasi-liniowym. Ma złożoność czasową O(n * log(n)).
Sortowanie przez scalanie wykorzystuje strategię dziel i zwyciężaj. Tablica jest wielokrotnie dzielona na mniejsze tablice po 1 element każda. Po podziale są one następnie ponownie łączone.
Podział jest rekurencyjny, dzięki czemu tablicę można później złożyć ponownie.
Podczas ponownego scalania tablicy podtablice są łączone w odpowiedniej kolejności. Scalanie odbywa się w taki sam sposób, jak scalanie posortowanej tablicy. Pseudokod umożliwiający wykonanie tej czynności zapisano poniżej:
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
Implementacja go w JavaScript dałaby następujące rezultaty:
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));
}
Jeśli uruchomisz kod z przykładową tablicą, powinno działać.
Szybkie sortowanie
Podobnie jak sortowanie przez scalanie, sortowanie szybkie opiera się na strategii dziel i zwyciężaj. Algorytm wybiera element obrotowy. Następnie przesuwa wszystkie elementy większe od osi obrotu w prawo i mniejsze od osi obrotu w lewo. Po wykonaniu tej czynności, przegub znajdzie się we właściwej pozycji.
Aby przenieść elementy wokół osi, algorytm rozpoczyna się od przesunięcia osi na koniec tablicy.
Po przesunięciu za pomocą wskaźnika wykonujemy pętlę od lewej strony tablicy, szukając pierwszej liczby większej niż środek obrotu. Jednocześnie korzystamy z kolejnej pętli wskaźnikowej z prawej strony tablicy, szukając pierwszej liczby mniejszej od osi obrotu. Po zidentyfikowaniu obu liczb zamieniamy je. Procedurę tę powtarza się, aż wskaźnik po lewej stronie będzie większy niż wskaźnik po prawej stronie.
Kiedy się zatrzymamy, zamieniamy większą z dwóch ostatnio zamienionych liczb z osią. W tym momencie oś będzie we właściwej pozycji; liczby mniejsze od osi obrotu będą po lewej stronie, a większe po prawej stronie.
Ta procedura jest powtarzana rekurencyjnie dla podtablic po lewej i prawej stronie osi obrotu, aż w podtablicach pozostanie tylko jeden element.
Oto pseudokod szybkiego sortowania:
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 konwertowanie go na 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;
}
Sortowanie przykładowej tablicy za pomocą szybkiego sortowania w Node.js powinno dać następujący wynik:
W najlepszym przypadku Quicksort działa w quasi-liniowej złożoności czasowej. Użycie miejsca w trybie szybkiego sortowania również skaluje się logarytmicznie. Dlatego jest stosunkowo wydajny w porównaniu do innych algorytmów sortowania tablic JavaScript.
Wskazówki dotyczące rozmów kwalifikacyjnych na temat kodowania
❇️ Kluczem jest praktyka. Pomaga uczyć się różnych algorytmów, ale co ważniejsze, pomaga rozwijać umiejętności rozwiązywania problemów i myślenia obliczeniowego. Możesz także ćwiczyć na platformach takich jak Leetcode I AlgoExpert.
❇️ Najpierw spróbuj rozwiązać problem. Zamiast od razu przeskakiwać do rozwiązania, spróbuj je rozwiązać, ponieważ pomaga to rozwinąć umiejętności rozwiązywania problemów.
❇️ Jeśli problem trwa zbyt długo, przejdź do rozwiązania; nadal możesz nauczyć się rozwiązywać problem na podstawie rozwiązania. Większość platform do nauki oferuje rozwiązania. ChatGPT lub Google Bard są również przydatne do wyjaśniania pojęć.
❇️ Nie pisz też kodu od razu; zapisz swoje rozwiązania i przemyśl je przed napisaniem kodu. Pseudokod jest również przydatnym sposobem szybkiego zapisywania pomysłów.
Wniosek
W tym artykule omówiliśmy najpopularniejsze algorytmy sortowania. Jednak nauka tego wszystkiego może początkowo wydawać się przytłaczająca. Dlatego zazwyczaj zalecam mieszanie różnych źródeł zamiast polegania tylko na jednym. Miłego kodowania!
Następnie sprawdź zrozumienie funkcji sortowanej w Pythonie.