Сортування включенням
З Вікіпедії, безкоштовно encyclopedia
Сортування включенням або сортування вставлянням[1] — простий алгоритм сортування на основі порівнянь. На великих масивах є значно менш ефективним за такі алгоритми, як швидке сортування, пірамідальне сортування та сортування злиттям. Однак, має цілу низку переваг:
- простота у реалізації
- ефективний (зазвичай) на маленьких масивах
- ефективний при сортуванні масивів, дані в яких вже непогано відсортовані: продуктивність рівна O(n + d), де d — кількість інверсій
- на практиці ефективніший за більшість інших квадратичних алгоритмів (O(n2)), як то сортування вибором та сортування бульбашкою: його швидкодія рівна n2/4, і в найкращому випадку є лінійною
- є стабільним алгоритмом
Коротка інформація Клас, Структура даних ...
![]() | |
Клас | Алгоритм сортування |
---|---|
Структура даних | масив |
Найгірша швидкодія | О(n2) |
Найкраща швидкодія | О(n) |
Середня швидкодія | О(n2) |
Просторова складність у найгіршому випадку | О(n), O(1) |
Оптимальний | Переважно ні |
Закрити
Наприклад, більшість людей при сортуванні колоди гральних карт, використовують метод, схожий на алгоритм сортування включенням.
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/0/0f/Insertion-sort-example-300px.gif)