Cocktail Sort
Cocktail Sort — двунаправленная версия bubble sort: проходит массив слева направо и справа налево.
Основная идея
За один цикл продвигает большие элементы вправо и маленькие влево.
Пошаговый пример
Исходный массив:
[5, 1, 4, 2, 8, 0, 2]- Forward pass сдвигает максимум вправо
- Backward pass сдвигает минимум влево
- Диапазон прохода сужается после каждого цикла
Псевдокод
left = 0; right = n - 1
swapped = true
while swapped:
swapped = false
for i from left to right - 1:
compare and swap
right -= 1
for i from right down to left + 1:
compare and swap
left += 1
Оптимизация: Лучше bubble sort, когда маленькие элементы находятся в конце массива.
Сложность
Время
O(n²) в среднем и худшем случае.
Память
O(1), in-place.
Когда используется
- Обучение двунаправленным проходам
- Маленькие массивы
- Простые сценарии
Ключевые свойства
- Стабильный
- In-place
- Улучшенный bubble sort