Алгоритми сортування - це набір інструкцій, які беруть масив або список як вхідні дані та упорядковують елементи в певний порядок.
Сорти найчастіше мають цифровий або алфавітний формат (так званий лексикографічний), і можуть бути у порядку зростання (AZ, 0-9) або спадання (ZA, 9-0).
Чому алгоритми сортування важливі
Оскільки сортування часто може зменшити складність проблеми, це важливий алгоритм в інформатиці. Ці алгоритми мають пряме застосування в алгоритмах пошуку, алгоритмах баз даних, методах поділу та завоювання, алгоритмах структури даних та багатьох інших.
Деякі загальні алгоритми сортування
Деякі найпоширеніші алгоритми сортування:
- Сортування вибору
- Сортування бульбашок
- Сортування вставки
- Сортувати злиття
- Швидке сортування
- Сортування купи
- Сортування підрахунку
- Сортування Radix
- Сортування відра
Класифікація алгоритму сортування
Алгоритми сортування можна класифікувати за такими параметрами:
- На основі кількості обмінів або інверсії Це кількість разів, коли алгоритм міняє місцями елементи для сортування вхідних даних.
Selection Sort
вимагає мінімальної кількості свопів. - На основі кількості порівнянь Це кількість разів, коли алгоритм порівнює елементи для сортування вхідних даних. Використовуючи нотацію Big-O, перелічені вище приклади алгоритмів сортування вимагають принаймні
O(nlogn)
порівнянь у найкращому випадку таO(n^2)
порівнянь у гіршому випадку для більшості результатів. - На основі рекурсії або
Quick Sort
нерекурсії Деякі алгоритми сортування, наприклад , використовують рекурсивні методи для сортування вхідних даних. Інші алгоритми сортування, такі якSelection Sort
абоInsertion Sort
, використовують нерекурсивні методи. Нарешті, деякі алгоритми сортування, такі якMerge Sort
, використовують як рекурсивні, так і нерекурсивні методи для сортування вхідних даних. - Засновано на алгоритмах сортування за стабільністю,
stable
якщо алгоритм підтримує відносний порядок елементів з однаковими ключами. Іншими словами, два еквівалентні елементи залишаються в тому ж порядку у відсортованому виведенні, як вони були у вхідних даних. Insertion sort
,,Merge Sort
іBubble Sort
стабільніHeap Sort
іQuick Sort
не є стабільними- На основі вимоги до додаткового простору алгоритми сортування називаються такими,
in place
якщо вони потребують постійногоO(1)
додаткового місця для сортування. Insertion sort
іQuick-sort
є своїмin place
родом , як ми переміщаємо елементи щодо осі повороту і на самому ділі не використовувати окремий масив , який не має місця в сортуваннях злиття , де розмір входу повинен бути виділений заздалегідь , щоб зберегти вихід під час сортування.Merge Sort
є прикладомout place
сортування, оскільки для його роботи потрібен додатковий простір у пам’яті.
Найкраща часова складність для будь-якого сортування на основі порівняння
Будь-який алгоритм сортування, заснований на порівнянні, повинен робити принаймні порівняння nLog2n для сортування вхідного масиву, а сортування Heapsort та merge є асимптотично оптимальними сортаціями порівняння. Це можна легко довести, намалювавши схему дерева рішень.