Коктейльная сортировка :: Cocktail sort

Коктейльная сортировка

Модификация пузырьковой сортировки.

Алгоритм

Производится многократный прогон по массиву, соседние элементы сравниваются и, в случае необходимости, меняются местами. При достижении конца массива направление меняется на противоположное. Таким образом по очереди выталкиваются крупные и мелкие элементы массива в конец и начало структуры соответственно.Коктейльная сортировка ещё называется двухсторонней сортировкой простыми обменами. Есть аналогичная модификация и для сортировки выбором.

Характеристики алгоритма

НазваниеКоктейльная сортировка (Cocktail sort)
Другие названияШейкерная сортировка (Shaker sort);
Сортировка перемешиванием (Shuffle sort);
Челночная сортировка (Shuttle sort);
Пульсирующая сортировка (Ripple sort);
Двухсторонняя пузырьковая сортировка (Bidirectional bubble sort)
КлассСортировки обменами
УстойчивостьУстойчивая
СравненияДа
Сложность по времениХудшаяO(n2)
СредняяO(n2)
ЛучшаяO(n)
Сложность по памятиОбщаяO(n)
ДополнительнаяO(1)

Ссылки

Сортировки обменами

Пузырьковая сортировка и все-все-все

Коктейльная сортировка

Cocktail sort

Реализация на различных ЯП