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