Сортировка чёт-нечет (odd-even sort) - является модификацией сортировки пузырьком(https://dzen.ru/a/Zxq90S9-vCI24kjn). Этот достаточно простой алгоритм сортировки был создан для работы на параллельных процессорах. Его основная идея заключается в сравнении элементов массива с четными и нечетными индексами с последующими элементами независимо друг от друга. Преимущество данного метода заключается в том, что на нескольких процессорах он выполняется быстрее, поскольку сортировка четных и нечетных индексов происходит параллельно.
▎Основные шаги алгоритма:
1. Разделение на четные и нечетные индексы:
• На каждой итерации алгоритм проходит по массиву и сравнивает элементы с четными индексами с элементами, находящимися рядом с ними (нечетными индексами).
2. Сравнение и обмен:
• Если элемент с четным индексом больше элемента с нечетным индексом, они обмениваются местами.
• После этого алгоритм переходит к следующей паре (индексы +2).
3. Чередование проходов:
• Алгоритм выполняет два прохода: один для четных индексов, другой для нечетных.
• Сначала происходит сортировка по четным индексам, затем по нечетным. Эти проходы повторяются до тех пор, пока массив не будет отсортирован.
▎Временная сложность:
Алгоритм имеет временную сложность O(n²) в худшем и среднем случаях. Это связано с тем, что алгоритм выполняет множество проходов по массиву, сравнивая и меняя местами соседние элементы, в лучшем случае, когда массив уже отсортирован, временная сложность составляет O(n).
Хотя алгоритм и имеет квадратичную сложность, он может быть полезен в параллельных вычислениях, поскольку операции с четными и нечетными индексами могут выполняться одновременно на разных процессорах. В параллельной реализации временная сложность может быть уменьшена до O(n) с использованием O(log n) шагов.
▎Устойчивость:
Данный алгоритм сортировки является устойчивым, это означает, что при сортировке элементов с одинаковыми ключами их относительный порядок сохраняется. То есть, если два элемента имеют одинаковое значение и один из них идет перед другим в исходном массиве, то после сортировки первый элемент останется перед вторым.
Однопоточная реализация на языке программирования C++:
Однопоточная реализация на языке программирования Python: