У світі програмування масиви є однією з найпоширеніших структур даних. Вони дають змогу зберігати безліч елементів одного типу, що робить їх незамінними інструментами під час роботи з даними. Однак для ефективної роботи з масивами часто необхідно впорядковувати їхній вміст. І тут на допомогу приходить сортування масиву JS.
JavaScript надає метод sort(), який доступний для всіх масивів через прототип Array.prototype. Цей метод дозволяє сортувати елементи масиву на місці, тобто змінюючи вихідний масив, і повертає – відсортований. Цікаво, що за замовчуванням цей метод сортує елементи масиву в лексикографічному порядку, що відповідає порядку кодових точок Unicode. Для рядків це означає сортування за алфавітом, для чисел – за зростанням.
Розуміння того, як працює стандартний порядок сортування, важливе для передбачуваності поведінки методу sort(). За замовчуванням елементи масиву порівнюються як рядки. Це означає, що під час сортування масиву чисел спочатку вони перетворюються на рядки, а потім порівнюються.
Поняття структури даних, що використовуються в JS, такі, як об’єкти, масиви та ін., в обов’язковому порядку розглядаються на курсі JavaScript Start від компанії FoxmindED.
Основи методу sort
Метод sort() є основним інструментом для сортування елементів масиву в JavaScript. Синтаксис цього методу досить простий: arr.sort([compareFunction]), де:
- arr – це масив, який потрібно відсортувати;
- compareFunction (необов’язковий параметр) – це функція порівняння, що визначає порядок сортування. Якщо цей параметр не вказано, елементи масиву сортуються як рядки в лексикографічному порядку Unicode.
Якщо не надати функцію порівняння, метод sort() використовуватиме стандартний порядок сортування. Для рядків це буде сортування за алфавітом, для чисел – за зростанням.
Наприклад:
- Сортування масиву чисел:
const numbers = [4, 2, 1, 3];
numbers.sort(); // Returns [1, 2, 3, 4]- Сортування масиву рядків:
const strings = ['banana', 'apple', 'cherry', 'date'];
strings.sort(); // Returns ['apple', 'banana', 'cherry', 'date']Часто потрібне складніше сортування, засноване на користувацьких критеріях. Для цього ми можемо використовувати функцію порівняння:
const numbers = [4, 2, 1, 3];
numbers.sort((a, b) => b - a); // Returns [4, 3, 2, 1]У цьому прикладі функція порівняння приймає два аргументи a і b, і повертає різницю між ними. Це дає змогу сортувати числа за спаданням.
Користувацька функція порівняння
При використанні методу sort(), також можна визначити власний порядок сортування за допомогою необов’язкового параметра compareFunction. Ця функція приймає два аргументи (зазвичай позначаються як a і b). Вони являють собою два елементи масиву, які порівнюються. Залежно від результату порівняння:
- функція має повернути від’ємне число, якщо a має йти перед b;
- позитивне число — якщо b має йти перед a;
- і нуль, якщо вони рівні й порядок не важливий.
const numbers = [4, 2, 1, 3];
numbers.sort((a, b) => a - b);
console.log(numbers); // Conclusion : [1, 2, 3, 4]У цьому прикладі функція порівняння просто повертає різницю між a і b. Якщо a менше b, це буде від’ємне число, що означає, що a має бути перед b, і навпаки. Це призводить до сортування чисел за зростанням.
const numbers = [4, 2, 1, 3];
numbers.sort((a, b) => b - a);
console.log(numbers); // Conclusion: [4, 3, 2, 1]У цьому прикладі функція порівняння повертає різницю між b і a, що призводить до сортування чисел за спаданням.
Вкладена деструктуризація та сортування
Існує також можливість використовувати метод sort() спільно з вкладеною деструктуризацією для сортування масивів об’єктів за певними ключами. Цей підхід дає змогу спростити сортування і зробити код більш читабельним.
Як це працює? Деструктуризація в JavaScript дає змогу витягувати значення з об’єктів і масивів і присвоювати їх змінним. Вкладена деструктуризація дає змогу витягувати значення з вкладених об’єктів.
Спільне використання методу sort() і вкладеної деструктуризації дозволяє нам сортувати масив об’єктів за значенням однієї з їхніх властивостей. Ми можемо звернутися до потрібної властивості у функції порівняння, використовуючи вкладену деструктуризацію, і сортувати масив об’єктів на основі цієї властивості:
const users = [
{ name: 'John', age: 25 },
{ name: 'Jane', age: 30 },
{ name: 'Doe', age: 20 }
];
users.sort((a, b) => a.age - b.age);
console.log(users);У цьому прикладі ми сортуємо масив users за зростанням віку. Функція порівняння приймає два об’єкти a і b, і повертає різницю їхніх вікових груп. Це призводить до сортування за зростанням.
const users = [
{ name: 'John', age: 25 },
{ name: 'Jane', age: 30 },
{ name: 'Doe', age: 20 }
];
users.sort((a, b) => b.age - a.age);
console.log(users);У цьому ж прикладі ми сортуємо масив users за спаданням віку. Функція порівняння повертає різницю вікових груп об’єктів b і a, що призводить до сортування за спаданням.
Бульбашкове сортування
Бульбашкове сортування — це один із найпростіших алгоритмів сортування, що проходить масивом кілька разів, порівнюючи пари сусідніх елементів і міняючи їх місцями, якщо вони розташовані в неправильному порядку. Кожен прохід масивом поміщає найбільший елемент у кінець (або найменший елемент на початок, якщо сортуємо за спаданням).
Який вигляд має алгоритм такого сортування?
- Починаємо порівнювати перший і другий елементи масиву. Якщо другий елемент менший за перший, міняємо їх місцями.
- Переходимо до наступної пари елементів (другого і третього), порівнюємо їх і, якщо потрібно, міняємо місцями.
- Продовжуємо цей процес до кінця масиву.
- Після першого проходу найбільший елемент опиниться в кінці масиву.
- Повторюємо процес для всіх елементів масиву, крім останнього.
- Після кожного проходу найбільший елемент “спливає” на своє місце, як бульбашка води в келиху, тому алгоритм названо “бульбашковим”.
function bubbleSort(arr) {
const len = arr.length;
for (let i = 0; i < len; i++) {
for (let j = 0; j < len - 1; j++) {
if (arr[j] > arr[j + 1]) {
// If the current element is larger than the next one, swap them
const temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return arr;
}
// Usage example:
const array = [5, 3, 8, 1, 2];
console.log(bubbleSort(array)); // Conclusion: [1, 2, 3, 5, 8]У цьому прикладі ми маємо два вкладених цикли: зовнішній, який проходить усім масивом, і внутрішній, який порівнює і міняє місцями сусідні елементи. Після кожного проходу масивом найбільший елемент “спливає” в кінець масиву, що призводить до його впорядкування.
Швидке сортування
Швидке сортування, також відоме як сортування Хоара, є одним із найефективніших алгоритмів сортування для масивів. Воно використовує метод “розділяй і володарюй”, розбиваючи масив на підмасиви і рекурсивно сортуючи кожен із них. Як це відбувається?
- Обирається опорний елемент із масиву. Він може бути будь-яким, але зазвичай вибирають середній елемент.
- Масив розбивається на дві частини: одна містить елементи, які менші за опорний, а інша — ті, які більші за опорний.
- Процес рекурсивно повторюється для кожної з двох частин.
- На останньому етапі підмасиви об’єднуються в один масив.
const pivot = arr[Math.floor(arr.length / 2)]; // select the support element
const left = [];
const right = [];
for (let i = 0; i < arr.length; i++) {
if (arr[i] < pivot) {
left.push(arr[i]); // add smaller elements to the left
} else if (arr[i] > pivot) {
right.push(arr[i]); // add large elements to the right
}
// elements equal to the reference can be added to any part, we can add them to the left or to the right
}
return [...quickSort(left), pivot, ...quickSort(right)]; // merge and return sorted subarrays
}
// Usage example:
const array = [5, 3, 8, 1, 2];
console.log(quickSort(array)); // Conclusion: [1, 2, 3, 5, 8]Цей алгоритм має середню часову складність і є одним із найефективніших методів сортування для великих масивів.
Оптимізація сортування масивів
При виборі та застосуванні алгоритму сортування для конкретного завдання важливо враховувати різні фактори, такі як розмір і тип даних масиву, а також необхідну продуктивність. Нижче наведено поради та рекомендації, які допоможуть оптимізувати цей процес:
1. Вибір алгоритму сортування
- Для маленьких масивів (зазвичай менше ніж 10-20 елементів): тут бульбашкове сортування може бути ефективнішим через його низьку складність.
- Для великих масивів: у цьому випадку швидке сортування часто буде кращим, оскільки має складність O(n log n), що робить його дуже ефективним.
- Для специфічних даних: деякі алгоритми сортування працюють краще на певних типах даних. Наприклад, сортування підрахунком ефективне для цілих чисел у певному діапазоні, а сортування злиттям добре справляється з великими обсягами даних.
2. Урахування особливостей мови програмування та середовища виконання
- Використання вбудованих методів: у мовах програмування, як-от JavaScript, вбудовані методи сортування можуть бути оптимізовані для конкретного середовища виконання і використовувати оптимізовані алгоритми сортування, що може бути вигідно за продуктивністю.
- Використання багатопоточності: це може прискорити процес сортування.
3. Мінімізація операцій копіювання
- Використання in-place сортувань: тут відбувається мінімізація кількості операцій копіювання, що може заощадити пам’ять і підвищити продуктивність.
- Оптимізація роботи з пам’яттю: під час реалізації власних алгоритмів сортування варто враховувати ефективне використання пам’яті та мінімізацію операцій копіювання.
4. Профілювання та тестування
- Профілювання продуктивності: це допоможе оцінити реальну ефективність і порівняти різні варіанти.
- Тестування на різних вхідних даних: необхідно враховувати різноманітність вхідних даних і тестувати їх на різних наборах даних, щоб переконатися в їхній ефективності в різних умовах.
Висновок
Сортування масивів у JavaScript – це важливий аспект програмування, який дає змогу керувати даними більш ефективно та зручно. Розуміння різних методів сортування та їхнє оптимальне застосування допоможе у створенні продуктивніших та ефективніших додатків.
Експериментуйте з різними методами сортування та обирайте ті, що найбільше підходять для ваших конкретних завдань, з огляду на особливості даних і вимоги до продуктивності.
У вас залишилися запитання про методи сортування масивів у JavaScript? Сміливо запитуйте в коментарях нижче!