Чётно-нечётная сортировка :: Odd-even sort

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

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

Алгоритм

Производится многократный прогон по массиву, соседние элементы сравниваются и, в случае необходимости, меняются местами. В отличие от пузырьковой сортировки шаг по массиву равен двум, а не единице.

Сначала элементы с нечётными индексами сравниваются/обмениваются с элементами с чётными индексами (1-й со 2-м, 3-й с 4-м, 5-й с 6-м и т.д.). Затем элементы с чётными индексами сравниваются/обмениваются с соседними элементами с нечётными индексами (2-й с 3-м, 4-й с 5-м, 6-й с 7-м и т.д.). Затем снова нечётные сравниваются с чётными, потом снова чётные с нечётными и т.д. Процесс завершается если в результате двух прогонов не происходило обменов — значит массив упорядочен.

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

Название Чётно-нечётная сортировк (Odd-even sort)
Другие названия Кирпичная сортировка (Brick sort);
Чётно-нечётная сортировка с транспозицией
(Odd–even transposition sort)
Класс Сортировки обменами
Устойчивость Устойчивая
Сравнения Да
Сложность по времени Худшая O(n2)
Средняя O(n2)
Лучшая O(n)
Сложность по памяти Общая O(n)
Дополнительная O(1)

Ссылки

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

Odd-even sort on Wikipedia

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