Сортування списків даних є надзвичайно важливою частиною обробки в програмах.
Це корисно для відображення даних і виконання пошуку. Тому не дивно, що будь-який хороший програміст повинен знати, як сортувати масиви. У цій статті пояснюється кілька найпоширеніших алгоритмів сортування масивів у JavaScript.
Що таке сортування і чому воно корисне?
Джерело: Unsplash
Сортування – це систематична організація значень за певним порядком. Цей порядок може бути за спаданням або за зростанням. Сортування масивів у JavaScript є корисним, оскільки воно дозволяє відображати дані більш змістовно.
Наприклад, користувач може забажати бачити файли, відсортовані за найновішими файлами, або продукти, відсортовані за ціною. Це також корисно для виконання бінарного пошуку даних, який працює лише з відсортованими даними.
Хоча існують функції та бібліотеки, які допоможуть вам легко сортувати дані, вам все одно потрібно знати, як сортування працює під капотом для кодування інтерв’ю або коли вам потрібно написати код низького рівня.
Алгоритми сортування масивів JavaScript
Бульбашкове сортування
Bubble Sort, мабуть, найпростіший алгоритм для розуміння та реалізації. Він працює шляхом циклічного проходження масиву. З кожним проходом ми рухаємося по масиву від початку до кінця, порівнюючи два сусідніх елемента. Якщо елементи розташовані в неправильному порядку, ми міняємо їх місцями.
Ми виконуємо n проходів, де n — кількість елементів у масиві. З кожним проходом масив сортується, починаючи з правого боку. Псевдокод для алгоритму сортування чисел у порядку зростання виглядає наступним чином:
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.
Перекладаючи його на JavaScript, код виглядатиме так:
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;
}
Щоб краще зрозуміти, що відбувається, я б рекомендував додати console.logs всередину двох циклів, щоб побачити, як масив змінюється з кожним проходом.
У наведеному нижче коді я змінив функцію сортування, щоб додати console.logs у два цикли. Я також створив невеликий несортований масив, який відсортував за допомогою функції сортування.
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);
Результатом виконання наведеного вище коду буде:
Бульбашкове сортування має складність часу Big O O(n ^ 2). Це пов’язано з тим, що він виконує n проходів, які зациклюються по масиву для кожного проходу. Тому він погано масштабується. Однак він має просторову складність O(1), оскільки він змінює елементи масиву на місці.
Сортування вставкою
Сортування за допомогою вставки — це популярний алгоритм сортування масивів JavaScript. Припустімо, що ми використовуємо сортування вставкою для сортування значень у порядку зростання. Алгоритм працює, вибираючи число, яке ми називатимемо num. Потім він пересуває num ліворуч, доки кожне інше число ліворуч від num не стане меншим за num. Усі числа будуть відсортовані, якщо це зробити від другого елемента до кінця. Ось опис у псевдокоді.
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
А тепер псевдокод, реалізований у JavaScript, виглядає наступним чином.
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;
}
Як і у випадку з Bubble Sort, додавання console.logs допомагає візуалізувати те, що відбувається. Наведений нижче фрагмент коду показує, як працює сортування вставкою.
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);
І запуск наведеного вище фрагмента дає такий результат:
Сортування злиттям
У той час як сортування вставленням і бульбашковим сортуванням масштабується за квадратичний час, сортування злиттям масштабується за квазілінійний час. Він має часову складність O(n * log(n)).
Сортування злиттям використовує стратегію розділяй і володарюй. Масив кілька разів ділиться на менші масиви по 1 елементу кожен. Після поділу вони потім зливаються назад.
Поділ є рекурсивним, тому масив можна згодом повторно зібрати.
Під час об’єднання масиву підмасиви об’єднуються по порядку. Об’єднання виконується так само, як і відсортований масив. Псевдокод для цього написано нижче:
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
Реалізація його в JavaScript дасть наступне:
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));
}
Якщо ви запустите код із прикладом масиву, він має працювати.
Швидке сортування
Як і сортування злиттям, швидке сортування спирається на стратегію розділяй і володарюй. Алгоритм вибирає опорний елемент. Далі він переміщує всі елементи, більші за опору, праворуч і менші за опору ліворуч. Як тільки це буде зроблено, шарнір буде в правильному положенні.
Щоб перемістити елементи навколо опорної точки, алгоритм починається з переміщення опорної точки в кінець масиву.
Після переміщення ми використовуємо вказівник, щоб виконати цикл зліва від масиву, шукаючи перше число, більше за опорну. Одночасно ми використовуємо ще один цикл вказівника справа від масиву, шукаючи перше число, яке менше опорного. Коли обидва числа визначено, ми міняємо їх місцями. Ця процедура повторюється до тих пір, поки вказівник ліворуч не стане більшим за вказівник праворуч.
Коли ми зупиняємося, ми міняємо місцями більше з двох останніх чисел, поміняних місцями з опорою. У цей момент шарнір буде в правильному положенні; числа, менші за опорну, будуть ліворуч, а більші – праворуч.
Ця процедура повторюється рекурсивно для підмасивів ліворуч і праворуч від опори, поки в підмасивах не залишиться лише один елемент.
Ось псевдокод для швидкого сортування:
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
І перетворення його на 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;
}
Сортування прикладу масиву за допомогою швидкого сортування в Node.js має дати наступне:
У найкращому випадку Quicksort працює з квазілінійною часовою складністю. Використання місця у швидкому сортуванні також масштабується логарифмічно. Тому він є відносно ефективним порівняно з іншими алгоритмами сортування масивів JavaScript.
Поради для ваших співбесід з кодування
❇️ Практика є ключовим. Це допоможе вам вивчити різні алгоритми, але, що більш важливо, це допоможе вам розвинути навички розв’язання проблем і обчислювального мислення. Ви також можете займатися на таких платформах, як Leetcode і AlgoExpert.
❇️ Спробуйте спочатку вирішити проблему. Замість того, щоб відразу переходити до рішення, спробуйте вирішити його, оскільки це допоможе вам розвинути навички вирішення проблем.
❇️ Якщо проблема триває надто довго, переходьте до вирішення; ви все ще можете навчитися розв’язувати задачу з рішення. Більшість платформ для навчання пропонують рішення. ChatGPT або Google Bard також корисні для пояснення концепцій.
❇️ Крім того, не пишіть код відразу; дошіть свої рішення та обдумайте їх, перш ніж писати код. Псевдокод також є корисним способом швидкого запису ідей.
Висновок
У цій статті ми розглянули найпопулярніші алгоритми сортування. Однак спочатку дізнатися все це може здатися непосильним. Тому я зазвичай рекомендую змішувати різні джерела, а не просто покладатися на одне. Щасливого кодування!
Далі перевірте розуміння сортованої функції в Python.