Сортировка чёт-нечет (Odd-Even Sort)

Сортировка чёт-нечет (odd-even sort) - является модификацией сортировки пузырьком(https://dzen.ru/a/Zxq90S9-vCI24kjn). Этот достаточно простой алгоритм сортировки был создан для работы на параллельных процессорах. Его основная идея заключается в сравнении элементов массива с четными и нечетными индексами с последующими элементами независимо друг от друга. Преимущество данного метода заключается в том, что на нескольких процессорах он выполняется быстрее, поскольку сортировка четных и нечетных индексов происходит параллельно.

▎Основные шаги алгоритма:

1. Разделение на четные и нечетные индексы:

• На каждой итерации алгоритм проходит по массиву и сравнивает элементы с четными индексами с элементами, находящимися рядом с ними (нечетными индексами).

2. Сравнение и обмен:

• Если элемент с четным индексом больше элемента с нечетным индексом, они обмениваются местами.

• После этого алгоритм переходит к следующей паре (индексы +2).

3. Чередование проходов:

• Алгоритм выполняет два прохода: один для четных индексов, другой для нечетных.

• Сначала происходит сортировка по четным индексам, затем по нечетным. Эти проходы повторяются до тех пор, пока массив не будет отсортирован.

▎Временная сложность:

Алгоритм имеет временную сложность O(n²) в худшем и среднем случаях. Это связано с тем, что алгоритм выполняет множество проходов по массиву, сравнивая и меняя местами соседние элементы, в лучшем случае, когда массив уже отсортирован, временная сложность составляет O(n).

Хотя алгоритм и имеет квадратичную сложность, он может быть полезен в параллельных вычислениях, поскольку операции с четными и нечетными индексами могут выполняться одновременно на разных процессорах. В параллельной реализации временная сложность может быть уменьшена до O(n) с использованием O(log n) шагов.

▎Устойчивость:

Данный алгоритм сортировки является устойчивым, это означает, что при сортировке элементов с одинаковыми ключами их относительный порядок сохраняется. То есть, если два элемента имеют одинаковое значение и один из них идет перед другим в исходном массиве, то после сортировки первый элемент останется перед вторым.

Однопоточная реализация на языке программирования C++:

Однопоточная реализация на языке программирования Python: