01.10.2024 старт набору нової групи на курс Enterprise Patterns! Реєструйтеся зараз зі знижкою 30%!
Дізнатися більше
01.03.2024
9 хвилин читання

Про методи сортування масивів у JavaScript

У світі програмування масиви є однією з найпоширеніших структур даних. Вони дають змогу зберігати безліч елементів одного типу, що робить їх незамінними інструментами під час роботи з даними. Однак для ефективної роботи з масивами часто необхідно впорядковувати їхній вміст. І тут на допомогу приходить сортування масиву JS.

JavaScript надає метод sort(), який доступний для всіх масивів через прототип Array.prototype. Цей метод дозволяє сортувати елементи масиву на місці, тобто змінюючи вихідний масив, і повертає – відсортований. Цікаво, що за замовчуванням цей метод сортує елементи масиву в лексикографічному порядку, що відповідає порядку кодових точок Unicode. Для рядків це означає сортування за алфавітом, для чисел – за зростанням.

Розуміння того, як працює стандартний порядок сортування, важливе для передбачуваності поведінки методу sort(). За замовчуванням елементи масиву порівнюються як рядки. Це означає, що під час сортування масиву чисел спочатку вони перетворюються на рядки, а потім порівнюються.

Поняття структури даних, що використовуються в JS, такі, як об’єкти, масиви та ін., в обов’язковому порядку розглядаються на курсі JavaScript Start від компанії FoxmindED.

Основи методу sort

Метод sort() є основним інструментом для сортування елементів масиву в JavaScript. Синтаксис цього методу досить простий: arr.sort([compareFunction]), де:

  • arr – це масив, який потрібно відсортувати;
  • compareFunction (необов’язковий параметр) – це функція порівняння, що визначає порядок сортування. Якщо цей параметр не вказано, елементи масиву сортуються як рядки в лексикографічному порядку Unicode.
🎓 Що ви дізнаєтеся на нашому курсі для новачків у програмуванні JavaScript Start:
Програма курсу
Середовище виконання
Змінні
Структури даних
Логічні операції, цикли, функції
Обробка помилок
Класи та екземпляри класів
ООП у JavaScript
Особливості мови
Деталі курсу

Якщо не надати функцію порівняння, метод sort() використовуватиме стандартний порядок сортування. Для рядків це буде сортування за алфавітом, для чисел – за зростанням.

Наприклад:

  • Сортування масиву чисел:
  • Сортування масиву рядків:

Часто потрібне складніше сортування, засноване на користувацьких критеріях. Для цього ми можемо використовувати функцію порівняння:

У цьому прикладі функція порівняння приймає два аргументи a і b, і повертає різницю між ними. Це дає змогу сортувати числа за спаданням.

Користувацька функція порівняння

При використанні методу sort(), також можна визначити власний порядок сортування за допомогою необов’язкового параметра compareFunction. Ця функція приймає два аргументи (зазвичай позначаються як a і b). Вони являють собою два елементи масиву, які порівнюються. Залежно від результату порівняння:

  • функція має повернути від’ємне число, якщо a має йти перед b;
  • позитивне число — якщо b має йти перед a;
  • і нуль, якщо вони рівні й порядок не важливий.

У цьому прикладі функція порівняння просто повертає різницю між a і b. Якщо a менше b, це буде від’ємне число, що означає, що a має бути перед b, і навпаки. Це призводить до сортування чисел за зростанням.

У цьому прикладі функція порівняння повертає різницю між b і a, що призводить до сортування чисел за спаданням.

Вкладена деструктуризація та сортування

Існує також можливість використовувати метод sort() спільно з вкладеною деструктуризацією для сортування масивів об’єктів за певними ключами. Цей підхід дає змогу спростити сортування і зробити код більш читабельним.

Як це працює? Деструктуризація в JavaScript дає змогу витягувати значення з об’єктів і масивів і присвоювати їх змінним. Вкладена деструктуризація дає змогу витягувати значення з вкладених об’єктів.

Спільне використання методу sort() і вкладеної деструктуризації дозволяє нам сортувати масив об’єктів за значенням однієї з їхніх властивостей. Ми можемо звернутися до потрібної властивості у функції порівняння, використовуючи вкладену деструктуризацію, і сортувати масив об’єктів на основі цієї властивості:

У цьому прикладі ми сортуємо масив users за зростанням віку. Функція порівняння приймає два об’єкти a і b, і повертає різницю їхніх вікових груп. Це призводить до сортування за зростанням.

У цьому ж прикладі ми сортуємо масив users за спаданням віку. Функція порівняння повертає різницю вікових груп об’єктів b і a, що призводить до сортування за спаданням.

Бульбашкове сортування

Бульбашкове сортування — це один із найпростіших алгоритмів сортування, що проходить масивом кілька разів, порівнюючи пари сусідніх елементів і міняючи їх місцями, якщо вони розташовані в неправильному порядку. Кожен прохід масивом поміщає найбільший елемент у кінець (або найменший елемент на початок, якщо сортуємо за спаданням).

Який вигляд має алгоритм такого сортування?

  • Починаємо порівнювати перший і другий елементи масиву. Якщо другий елемент менший за перший, міняємо їх місцями.
  • Переходимо до наступної пари елементів (другого і третього), порівнюємо їх і, якщо потрібно, міняємо місцями.
  • Продовжуємо цей процес до кінця масиву.
  • Після першого проходу найбільший елемент опиниться в кінці масиву.
  • Повторюємо процес для всіх елементів масиву, крім останнього.
  • Після кожного проходу найбільший елемент “спливає” на своє місце, як бульбашка води в келиху, тому алгоритм названо “бульбашковим”.

У цьому прикладі ми маємо два вкладених цикли: зовнішній, який проходить усім масивом, і внутрішній, який порівнює і міняє місцями сусідні елементи. Після кожного проходу масивом найбільший елемент “спливає” в кінець масиву, що призводить до його впорядкування.

Швидке сортування

Швидке сортування, також відоме як сортування Хоара, є одним із найефективніших алгоритмів сортування для масивів. Воно використовує метод “розділяй і володарюй”, розбиваючи масив на підмасиви і рекурсивно сортуючи кожен із них. Як це відбувається?

  • Обирається опорний елемент із масиву. Він може бути будь-яким, але зазвичай вибирають середній елемент.
  • Масив розбивається на дві частини: одна містить елементи, які менші за опорний, а інша — ті, які більші за опорний.
  • Процес рекурсивно повторюється для кожної з двох частин.
  • На останньому етапі підмасиви об’єднуються в один масив.

Цей алгоритм має середню часову складність і є одним із найефективніших методів сортування для великих масивів.

Оптимізація сортування масивів

При виборі та застосуванні алгоритму сортування для конкретного завдання важливо враховувати різні фактори, такі як розмір і тип даних масиву, а також необхідну продуктивність. Нижче наведено поради та рекомендації, які допоможуть оптимізувати цей процес:

1. Вибір алгоритму сортування

  • Для маленьких масивів (зазвичай менше ніж 10-20 елементів): тут бульбашкове сортування може бути ефективнішим через його низьку складність.
  • Для великих масивів: у цьому випадку швидке сортування часто буде кращим, оскільки має складність O(n log n), що робить його дуже ефективним.
  • Для специфічних даних: деякі алгоритми сортування працюють краще на певних типах даних. Наприклад, сортування підрахунком ефективне для цілих чисел у певному діапазоні, а сортування злиттям добре справляється з великими обсягами даних.
Выбор алгоритма сортировки

2. Урахування особливостей мови програмування та середовища виконання

  • Використання вбудованих методів: у мовах програмування, як-от JavaScript, вбудовані методи сортування можуть бути оптимізовані для конкретного середовища виконання і використовувати оптимізовані алгоритми сортування, що може бути вигідно за продуктивністю.
  • Використання багатопоточності: це може прискорити процес сортування.

3. Мінімізація операцій копіювання

  • Використання in-place сортувань: тут відбувається мінімізація кількості операцій копіювання, що може заощадити пам’ять і підвищити продуктивність.
  • Оптимізація роботи з пам’яттю: під час реалізації власних алгоритмів сортування варто враховувати ефективне використання пам’яті та мінімізацію операцій копіювання.
Підпишіться на наш Ютуб-канал! Корисні відео для програмістів чекають на вас! YouTube
Оберіть свій курс програмування! Шлях до кар’єри програміста починається тут! Подивитись

4. Профілювання та тестування

  • Профілювання продуктивності: це допоможе оцінити реальну ефективність і порівняти різні варіанти.
  • Тестування на різних вхідних даних: необхідно враховувати різноманітність вхідних даних і тестувати їх на різних наборах даних, щоб переконатися в їхній ефективності в різних умовах.

Висновок

Сортування масивів у JavaScript – це важливий аспект програмування, який дає змогу керувати даними більш ефективно та зручно. Розуміння різних методів сортування та їхнє оптимальне застосування допоможе у створенні продуктивніших та ефективніших додатків.

Експериментуйте з різними методами сортування та обирайте ті, що найбільше підходять для ваших конкретних завдань, з огляду на особливості даних і вимоги до продуктивності.

FAQ
Як відсортувати масив чисел у порядку зростання в JavaScript?

Використовуйте метод .sort((a, b) => a - b) для сортування масиву чисел у порядку зростання.

Чи можна відсортувати масив рядків за алфавітом у JavaScript?

Так, метод .sort() без додаткових параметрів відсортує рядки за алфавітом.

Як сортувати масив об'єктів за значенням ключа в JavaScript?

Використовуйте .sort((a, b) => a.key - b.key) для чисел або .sort((a, b) => a.key.localeCompare(b.key)) для рядків.

Чи можливо виконати зворотне сортування масиву?

Так, просто змініть знак у функції порівняння методу .sort().

Як перевірити, чи відсортований масив?

Пройдіться масивом і перевірте, що кожен наступний елемент не менший за попередній.

Чи є спосіб сортувати масив без зміни вихідного масиву?

Так, спочатку створіть копію масиву за допомогою .slice() або [...array], потім відсортуйте копію.

У вас залишилися запитання про методи сортування масивів у JavaScript? Сміливо запитуйте в коментарях нижче!

Додати коментар

Ваш імейл не буде опубліковано. Обов'язкові поля відзначені *

Зберегти моє ім'я, імейл та адресу сайту у цьому браузері для майбутніх коментарів