> Якщо масив впорядкований у зворотному порядку, то число операцій порівняння дорівнює 1/2 (n2 + n) - 1, даючи в середньому значення 1/4 (n2 + n-2).
Число операцій обміну буде наступним:
для кращого випадку: 2 (n-1);
в середньому: 1/4 (n2 +9 n-10);
для гіршого випадку: 1/2 (n2 +3 n-4).
Таким чином, число операцій обміну для гіршого випадку буде настільки ж великим, як і для сортировок бульбашковим методом і сортувань вибором. Число операцій обміну для середнього випадку буде лише на трохи менше. Однак сортування вставкою має дві переваги. По-перше, вона володіє природною поведінкою, тобто вона виконується швидше для упорядкованого масиву і найдовше виконується, коли масив упорядкований у зворотному напрямку. Це робить сортування вставкою корисної для впорядкування майже відсортованих масивів. По-друге, елементи з однаковими ключами не переставляти: якщо список елементів сортується з використанням двох ключів, то після завершення сортування вставкою він як і раніше буде впорядкований по двох ключах. p align="justify"> Незважаючи на те, що число порівнянь може бути досить невеликим для певних наборів даних, постійні зрушення масиву вимагають виконання великого числа операцій пересилань.
Однак, сортування вставкою має природну поведінку, вимагаючи найменше число операцій обміну для майже впорядкованого списку і найбільше число операцій обміну, коли масив упорядкований у зворотному напрямку.
2.7 Сортування Шелла
Всі представлені досі алгоритми сортування володіють дуже серйозним недоліком, а саме, час їх виконання пропорційно квадрату числа елементів.
Для великих обсягів даних ці сортування будуть повільними, а починаючи з деякої величини, вони будуть надто повільними, щоб їх можна було використовувати на практиці. Кожен програміст чув або розповідав "страшні" історії про "сортування, яка виконувалася три дні". На жаль, ці історії часто не були вигадкою. p align="justify"> Якщо сортування виконується занадто довго, то причиною цього може бути використовуваний алгоритм. Розглянемо дві дуже хороші сортування. Перша носить назву сортування Шелла, а друга називається швидким сортуванням, алгоритм якої визнаний найкращим. Ці сортування виконуються дуже швидко. p align="justify"> Сортування Шелла отримала свою назву по імені її творця Д.Л. Шелла. Однак, цю назву можна вважати вдалим, оскільки виконуються при сортуванні дії нагадують вкладання морських черепашок один на одного. p align="justify"> Загальний метод, який використовує сортування вставкою, застосовує принцип зменшення відстані між порівнюваними елементами. Нижче показана схема виконання сортування Шелла для масиву "fdacb e". Спочатку сортуються всі елементи, які зміщені один від одного на три позиції. Потім сортуються всі елементи...
