Обчислювальна складність алгоритмів, які ми розглядаємо, поступово зростає. Разом із цим ускладнюється їх реалізація та розуміння. Отже, починається щось цікаве! Сортування Шелла ("shell sort") знаходиться між простими та складними сортуваннями. Для цього існує кілька причин, про які ми сьогодні поговоримо.
За своєю сутністю сортування Шелла є модифікацією сортування включенням, про яке ми розповідали у попередній статті. Коротко нагадаємо. При сортуванні включенням прохід масивом здійснюється зліва направо. Беремо елемент і шукаємо, куди його можна вставити в лівій частині масиву так, щоб зліва знаходилося менше число, а справа — більше. І робимо так з кожним наступним елементом. Складність алгоритму включенням у гіршому випадку дорівнює O(n2).
Що, як ми проходитимемо не весь масив, а виконаємо сортування включеннями у підмасивах, які являють собою елементи вихідного масиву, що взяли з певним інтервалом?
— напевне, подумав Дональд Шелл і у 1959 році опублікував цю ідею.
Спробуємо її продемонструвати. Припустимо, ми маємо масив елементів:
(а1, а2, а3, а4, а5, а6, а7, а8, а9, а10, а11)
Застосуємо алгоритм сортування включенням до підмасиву, який складається з кожного 5-го елементу, виглядатиме він так:
(а1, а6, а11)
Зберігаємо результат сортування в основному масиві. І тепер, з таким самим інтервалом між елементами, зсуваємося на елемент вправо і сортуємо підмасив (а2, а7), а відтак робимо те ж саме для (а3, а8). І продовжуємо, поки не дійдемо до кінця масиву.
Далі, візьмемо підмасив із кожного 3-го елементу:
(а1, а4, а7, а10)
Знову зберігаємо результат сортування в основному масиві. Потім, вже звичним рухом, зсуваємось на один елемент вправо, отримуємо підмасив:
(а2, а5, а8, а11)
Сортуємо так і далі.
В кінці виконуємо звичайне сортування включенням для всього масиву, який вже частково відсортовано. От і вся ідея.
А тепер найцікавіше: складність алгоритму буде залежати від того, які інтервали обрати між елементами для виділення підмасивів. Варіантів багато, наведемо найбільш популярні:
Послідовність Шелла
Перший інтервал дорівнює довжині масиву. На кожному наступному кроці інтервал зменшується вдвічі. Обчислювальна складність у найгіршому випадку — O(n2).
Послідовність Хіббарда
Беруться конкретні відстані між елементами, які обчислюються за формулою 2k-1. У найгіршому випадку отримуємо O(n1.5).
Послідовність Седжвіка
Формула складна і в один рядок не влізе. Обчислювальна складність у найгіршому випадку — O(n4/3).
Послідовність Пратта
Всі добутки ступенів двійки та трійки. Обчислювальна складність у гіршому випадку — O(n log2n).
Послідовність Циура
Вважається найкращим запропонованим рядом. Визначена експериментально і відомостей про обчислювальну складність немає. Припускаємо, що вона повинна бути близькою до O(n log n).
Ось чому ми не можемо віднести цей алгоритм ані до простих, ані до складних: його обчислювальна складність сильно залежить від розміру масиву та обраної послідовності. А обрати або розрахувати послідовність самотужки — не найпростіша справа!
Дізнатися більше про інші види сортування ви можете з інших матеріалів блогу:
