Коктейльная сортировка :: 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 on Wikipedia
Реализация на различных ЯП

Добавить комментарий