Пояснення алгоритмів сортування

Алгоритми сортування - це набір інструкцій, які беруть масив або список як вхідні дані та упорядковують елементи в певний порядок.

Сорти найчастіше мають цифровий або алфавітний формат (так званий лексикографічний), і можуть бути у порядку зростання (AZ, 0-9) або спадання (ZA, 9-0).

Чому алгоритми сортування важливі

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

Деякі загальні алгоритми сортування

Деякі найпоширеніші алгоритми сортування:

  • Сортування вибору
  • Сортування бульбашок
  • Сортування вставки
  • Сортувати злиття
  • Швидке сортування
  • Сортування купи
  • Сортування підрахунку
  • Сортування Radix
  • Сортування відра

Класифікація алгоритму сортування

Алгоритми сортування можна класифікувати за такими параметрами:

  1. На основі кількості обмінів або інверсії Це кількість разів, коли алгоритм міняє місцями елементи для сортування вхідних даних. Selection Sortвимагає мінімальної кількості свопів.
  2. На основі кількості порівнянь Це кількість разів, коли алгоритм порівнює елементи для сортування вхідних даних. Використовуючи нотацію Big-O, перелічені вище приклади алгоритмів сортування вимагають принаймні O(nlogn)порівнянь у найкращому випадку та O(n^2)порівнянь у гіршому випадку для більшості результатів.
  3. На основі рекурсії або Quick Sortнерекурсії Деякі алгоритми сортування, наприклад , використовують рекурсивні методи для сортування вхідних даних. Інші алгоритми сортування, такі як Selection Sortабо Insertion Sort, використовують нерекурсивні методи. Нарешті, деякі алгоритми сортування, такі як Merge Sort, використовують як рекурсивні, так і нерекурсивні методи для сортування вхідних даних.
  4. Засновано на алгоритмах сортування за стабільністю, stableякщо алгоритм підтримує відносний порядок елементів з однаковими ключами. Іншими словами, два еквівалентні елементи залишаються в тому ж порядку у відсортованому виведенні, як вони були у вхідних даних.
  5. Insertion sort,, Merge Sortі Bubble Sortстабільні
  6. Heap Sortі Quick Sortне є стабільними
  7. На основі вимоги до додаткового простору алгоритми сортування називаються такими, in placeякщо вони потребують постійного O(1)додаткового місця для сортування.
  8. Insertion sortі Quick-sortє своїм in placeродом , як ми переміщаємо елементи щодо осі повороту і на самому ділі не використовувати окремий масив , який не має місця в сортуваннях злиття , де розмір входу повинен бути виділений заздалегідь , щоб зберегти вихід під час сортування.
  9. Merge Sortє прикладом out placeсортування, оскільки для його роботи потрібен додатковий простір у пам’яті.

Найкраща часова складність для будь-якого сортування на основі порівняння

Будь-який алгоритм сортування, заснований на порівнянні, повинен робити принаймні порівняння nLog2n для сортування вхідного масиву, а сортування Heapsort та merge є асимптотично оптимальними сортаціями порівняння. Це можна легко довести, намалювавши схему дерева рішень.