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