Shell Sort
Shell Sort — улучшение insertion sort, где сравнение идёт с элементами через определённый шаг (gap).
Основная идея
Сначала сортируем элементы с большим gap, постепенно уменьшая gap до 1.
Пошаговый пример
Исходный массив:
[12, 34, 54, 2, 3]- Gap = 2: частично упорядочиваем массив
- Gap = 1: выполняем финальный insertion sort
- Получаем [2,3,12,34,54]
Псевдокод
gap = n / 2
while gap > 0:
for i from gap to n - 1:
temp = arr[i]
j = i
while j >= gap and arr[j - gap] > temp:
arr[j] = arr[j - gap]
j -= gap
arr[j] = temp
gap /= 2
Оптимизация: Подбор последовательности gap сильно влияет на скорость.
Сложность
Время
Зависит от gap, обычно между O(n^1.3) и O(n²).
Память
O(1), in-place.
Когда используется
- Средние массивы
- Когда нужен простой и быстрый in-place алгоритм
- Встраиваемые системы
Ключевые свойства
- Обычно не стабильный
- In-place
- Быстрее insertion sort на случайных данных