Odd-Even Sort

Чётно-нечётная сортировка (brick sort) - вариант пузырьковой сортировки, который вместо одного последовательного прохода чередует два независимых набора сравнений: по нечётным и по чётным позициям, что делает пары сравнений внутри каждого набора независимыми друг от друга и пригодными для параллельного выполнения.

Пререквизит:Big O Нотация

Лучший: O(n)Средний: O(n²)Худший: O(n²)Память: O(1)

Проблема

Обычная пузырьковая сортировка по своей природе последовательна: каждое сравнение (i, i+1) должно выполниться после предыдущего (i-1, i), потому что результат обмена на предыдущем шаге влияет на следующий. Это делает bubble sort плохим кандидатом для параллельных вычислений или аппаратной реализации (например, в сортирующих сетях), где хочется выполнять много сравнений одновременно.

Решение

Все сравнения разбиваются на две группы, которые не пересекаются по индексам: «нечётная» фаза сравнивает пары (1,2), (3,4), (5,6)... а «чётная» фаза - пары (0,1), (2,3), (4,5).... Внутри одной фазы ни одна пара индексов не используется дважды, поэтому все сравнения этой фазы можно выполнять одновременно, независимо друг от друга. Алгоритм чередует нечётную и чётную фазы, пока за очередной полный проход (обе фазы) не произойдёт ни одного обмена - тогда массив отсортирован.

Как это работает

Проверим поведение на конкретном входе - том же массиве [8, 3, 9, 1, 6, 4, 7, 2, 5] (n = 9), что используется на вкладке «Визуализация». Симуляция кода с вкладки «Реализация» даёт: 5 полных проходов (нечётная + чётная фаза), 40 сравнений и 21 обмен до полной сортировки.

Для сравнения: на уже отсортированном [1..9] алгоритм делает 1 проход, 8 сравнений и 0 обменов - оба полупрохода (по 4 сравнения каждый при n = 9) сразу подтверждают порядок. На развороте [9..1] - 6 проходов, 48 сравнений и 36 обменов: это худший случай, но обратите внимание - обычная пузырьковая сортировка на том же входе потребовала бы 8 проходов (n - 1), а не 6.

Эта разница не случайна: разбиение на нечётную и чётную фазы позволяет элементу переместиться на две позиции за один полный проход вместо одной, как в обычном bubble sort - если элемент сдвинулся вправо в нечётной фазе, он может тут же сдвинуться ещё раз в следующей за ней чётной. Замер на нескольких размерах подтверждает это: для развёрнутого входа число проходов растёт примерно как n/2 - 3 при n = 4, 6 при n = 9, 11 при n = 20, 26 при n = 50, а не как n.

Но это не меняет сложность по числу сравнений: каждый проход по-прежнему стоит O(n) сравнений (обе фазы вместе покрывают почти весь массив), и с O(n/2) проходами общая последовательная сложность остаётся O(n²) - тот же класс, что у обычного bubble sort, просто с меньшей константой. Разделение на фазы не даёт асимптотического выигрыша, если выполнять его на одном ядре одно за другим.

Выигрыш появляется только при реальном параллельном исполнении. Внутри одной фазы ни один индекс не встречается дважды - сравнения (1,2), (3,4), (5,6)... не пересекаются по данным, поэтому с n/2 процессорами вся фаза выполняется за O(1) параллельного времени. Число проходов при этом ограничено сверху значением n (строгий теоретический результат для odd-even transposition sort, доказываемый через принцип 0-1 для сортирующих сетей), что даёт O(n) суммарного параллельного времени вместо O(n²) последовательного.

Метод изобрёл А. Наум Хабермann в 1972 году как одну из первых схем сортировки для параллельных вычислительных систем (сети transputer-подобных процессоров). Именно строгая доказуемость через принцип 0-1 (если сеть компараторов корректно сортирует все последовательности из нулей и единиц, она сортирует любые числа) сделала odd-even transposition sort стандартным учебным примером сортирующей сети, а не просто ещё одним вариантом bubble sort.

Итог: чётно-нечётная сортировка - не более быстрый bubble sort в обычном смысле, а его переформулировка под другую вычислительную модель. На одном ядре она выигрывает лишь константу (в 1.5-2 раза меньше проходов, как показано выше), но при наличии параллельного оборудования переходит из класса O(n²) в класс O(n) - смена, недоступная простому bubble sort ни при какой оптимизации на одном потоке.

Нюансы выбора

Против обычного bubble sort на одном ядре - тот же квадратичный класс сложности, но измеримо меньше проходов (6 вместо 8 на развороте из 9 элементов); разумная замена, если код и так был написан как bubble sort.

Против cocktail shaker sort - оба устраняют часть слабости bubble sort, но разными средствами: shaker sort меняет направление прохода, оставаясь строго последовательным, тогда как odd-even sort разбивает проход на независимые фазы, жертвуя простотой ради параллелизуемости.

На параллельном или SIMD/GPU оборудовании с n/2 доступными потоками - именно здесь алгоритм переходит в класс O(n); без такого оборудования этот выигрыш недостижим, и выбор сводится к константному ускорению на одном ядре.

Не выбирать для больших последовательных массивов без параллельного оборудования - при отсутствии параллелизма выигрыш ограничен вдвое-втрое меньшим числом проходов, а не сменой асимптотического класса; для реального ускорения на одном ядре подойдут quick sort, merge sort или даже comb sort.

Примеры в коде

Работа А. Наума Хабермана (1972) - первое описание чётно-нечётной сортировки как схемы для параллельных многопроцессорных систем, задолго до появления современных GPU и SIMD-инструкций.

Принцип 0-1 (zero-one principle) Кнута из третьего тома «Искусства программирования» - стандартный инструмент доказательства корректности сортирующих сетей, включая odd-even transposition network, без перебора всех возможных перестановок.

Аппаратные сортирующие сети в FPGA и ASIC используют регулярную, независимую по фазам структуру odd-even transposition sort как основу для схем компараторов с предсказуемой топологией межсоединений.

Учебные курсы по параллельным алгоритмам (например, в рамках PRAM-модели) неизменно берут odd-even transposition sort как первый пример перехода от последовательного алгоритма к параллельному через разбиение зависимостей на независимые группы.

Когда применять

Когда доступно параллельное или SIMD-оборудование и нужна простая, регулярная схема сравнений без сложной логики зависимостей - например, в сортирующих сетях.
Как учебный пример того, как переформулировать последовательный алгоритм (bubble sort) в параллельно-совместимую форму, разбив зависимые шаги на независимые группы.

Примеры из практики

Параллельные вычислительные архитектуры и transputer-сети (1980-е годы) использовали чётно-нечётную сортировку как один из первых практических примеров параллельного алгоритма сортировки.
Сортирующие сети (sorting networks) и их аппаратные реализации нередко используют чётно-нечётную схему сравнений как основу для регулярной, легко масштабируемой топологии компараторов.