Чётно-нечётная сортировка :: 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