Comb Sort
Comb Sort — вариант bubble sort с уменьшающимся gap, который ускоряет перенос удалённых элементов.
Основная идея
Сначала сравниваем элементы на большом расстоянии, затем постепенно уменьшаем gap до 1.
Пошаговый пример
Исходный массив:
[8, 4, 1, 56, 3, 44, 23, 15]- Gap начинается с n и сжимается коэффициентом ~1.3
- На больших gap быстро устраняются "черепахи"
- При gap = 1 алгоритм работает как bubble sort
Псевдокод
gap = n
swapped = true
while gap > 1 or swapped:
gap = max(1, floor(gap / 1.3))
swapped = false
for i from 0 to n - gap - 1:
j = i + gap
if arr[i] > arr[j]:
swap(arr[i], arr[j])
swapped = true
Оптимизация: За счёт gap часто работает быстрее классического bubble sort.
Сложность
Время
В среднем быстрее O(n²), но в худшем близко к O(n²).
Память
O(1), in-place.
Когда используется
- Замена bubble sort
- Обучение gap-подходу
- Лёгкая реализация без рекурсии
Ключевые свойства
- Обычно не стабильный
- In-place
- Простой и практичный