Сортування включенням

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Сортування включенням
Приклад сортування масиву випадкових чисел.
Клас Алгоритм сортування
Структура даних масив
Найгірша швидкодія О(n2)
Найкраща швидкодія О(n)
Середня швидкодія О(n2)
Просторова складність у найгіршому випадку О(n), O(1)
Оптимальний Переважно ні

Сортування включенням — простий алгоритм сортування на основі порівнянь. На великих масивах є значно менш ефективним за такі алгоритми, як швидке сортування, пірамідальне сортування та сортування злиттям. Однак, має цілу низку переваг:

  • простота у реалізації
  • ефективний (зазвичай) на маленьких масивах
  • ефективний при сортуванні масивів, дані в яких вже непогано відсортовані: продуктивність рівна O(n + d), де d — кількість інверсій
  • на практиці ефективніший за більшість інших квадратичних алгоритмів (O(n2)), як то сортування вибором та сортування бульбашкою: його швидкодія рівна n2/4, і в найкращому випадку є лінійною
  • є стабільним алгоритмом

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

Приклад сортування включенням. Елементи в чорних рамках — посортована частина списку. Метод порівнює наступний елемент непосортованої частини (червона рамка) з послідовними елементами посортованої та вставляє у потрібне місце.

Опис[ред.ред. код]

На кожному кроці алгоритму ми вибираємо один з елементів вхідних даних і вставляємо його на потрібну позицію у вже відсортованому списку до тих пір, доки набір вхідних даних не буде вичерпано. Метод вибору чергового елементу з початкового масиву довільний; може використовуватися практично будь-який алгоритм вибору. Зазвичай (і з метою отримання стійкого алгоритму сортування), елементи вставляються за порядком їх появи у вхідному масиві.

Примітки[ред.ред. код]

Література[ред.ред. код]

  • Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein. Introduction to Algorithms (2nd ed.) The MIT Press. ISBN 0-07-013151-1

Див. також[ред.ред. код]

Посилання[ред.ред. код]