ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 09.11.2023
Просмотров: 41
Скачиваний: 3
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Чётно-нечётная сортировка
Презентацию подготовил
Москва 2022 г.
Кто придумал
- Алгоритм был впервые представлен Н. Хаберманом (N. Haberman) в 1972 году.
Как работает
- Алгоритм
- Производится многократный прогон по массиву, соседние элементы сравниваются и, в случае необходимости, меняются местами. В отличие от пузырьковой сортировки шаг по массиву равен двум, а не единице.
- Сначала элементы с нечётными индексами сравниваются/обмениваются с элементами с чётными индексами (1-й со 2-м, 3-й с 4-м, 5-й с 6-м и т.д.). Затем элементы с чётными индексами сравниваются/обмениваются с соседними элементами с нечётными индексами (2-й с 3-м, 4-й с 5-м, 6-й с 7-м и т.д.). Затем снова нечётные сравниваются с чётными, потом снова чётные с нечётными и т.д. Процесс завершается если в результате двух прогонов не происходило обменов - значит массив упорядочен.
Четно – нечетная сортировка На C++
Какая эффективность
Характеристики
| Название | Чётно-нечётная сортировк (Odd-even sort) |
| Другие названия | Кирпичная сортировка (Brick sort); Чётно-нечётная сортировка с транспозицией (Odd–even transposition sort) |
| Класс | Сортировки обменами |
| Устойчивость | Устойчивая |
| Сравнения | Да |
| Сложность по времени | Худшая | O(n2) |
| Средняя | O(n2) | |
| Лучшая | O(n) | |
| Сложность по памяти | Общая | O(n) |
| Дополнительная | O(1) |