Bitonic mergesort — параллельный алгоритм сортировки. Он также используется в качестве метода построения сортировочной сети . Алгоритм был разработан Кеном Батчером . Полученные сортировочные сети состоят из компараторов и имеют задержку , где — количество сортируемых элементов. [1] Это делает его популярным выбором для сортировки большого количества элементов на архитектуре, которая сама по себе содержит большое количество параллельных исполнительных устройств, работающих в режиме lockstep , например, типичный графический процессор .
Сортированная последовательность — это монотонно неубывающая (или невозрастающая) последовательность. Битонная последовательность — это последовательность с для некоторого , или циклический сдвиг такой последовательности.
Пусть и .
Из алгоритма построения видно, что количество раундов параллельных сравнений определяется выражением .
Отсюда следует, что число компараторов ограничено (что устанавливает точное значение для случая, когда является степенью числа 2).
Хотя абсолютное число сравнений обычно выше, чем у сортировки Батчера «чет-нечет» , многие последовательные операции в битонной сортировке сохраняют локальность ссылок , что делает реализации более дружественными к кэшу и, как правило, более эффективными на практике.
Ниже представлена битонная сортировочная сеть с 16 входами:
16 чисел входят как входы на левом конце, скользят по каждому из 16 горизонтальных проводов и выходят на выходах на правом конце. Сеть спроектирована так, чтобы сортировать элементы, с наибольшим числом внизу.
Стрелки — это компараторы. Всякий раз, когда два числа достигают двух концов стрелки, они сравниваются, чтобы убедиться, что стрелка указывает на большее число. Если они не в порядке, они меняются местами. Цветные поля приведены только для иллюстрации и не оказывают никакого влияния на алгоритм.
Каждый красный ящик имеет одинаковую структуру: каждый вход в верхней половине сравнивается с соответствующим входом в нижней половине, причем все стрелки направлены вниз (темно-красный) или все вверх (светло-красный). Если входы образуют битоническую последовательность (одну неубывающую последовательность, за которой следует одна невозрастающая или наоборот), то выход сформирует две битонические последовательности. Верхняя половина выхода будет битонической, а нижняя половина будет битонической, причем каждый элемент верхней половины будет меньше или равен каждому элементу нижней половины (для темно-красного) или наоборот (для светло-красного). Эта теорема не очевидна, но ее можно проверить, тщательно рассмотрев все случаи того, как могут сравниваться различные входы, используя принцип нуля-единицы , где битоническая последовательность представляет собой последовательность нулей и единиц, которая содержит не более двух подпоследовательностей «10» или «01».
Красные ящики объединяются, образуя синие и зеленые ящики. Каждый такой ящик имеет одинаковую структуру: красный ящик применяется ко всей входной последовательности, затем к каждой половине результата, затем к каждой половине каждого из этих результатов и так далее. Все стрелки указывают вниз (синие) или все указывают вверх (зеленые). Эта структура известна как сеть бабочки . Если вход в этот ящик оказывается битоническим, то выход будет полностью отсортирован в порядке возрастания (синие) или убывания (зеленые). Если число попадает в синий или зеленый ящик, то первый красный ящик отсортирует его в правильную половину списка. Затем он пройдет через меньший красный ящик, который отсортирует его в правильную четверть списка в этой половине. Это продолжается до тех пор, пока он не будет отсортирован в точно правильной позиции. Следовательно, выход зеленого или синего ящика будет полностью отсортирован.
Зеленые и синие ящики объединяются, чтобы сформировать всю сортировочную сеть. Для любой произвольной последовательности входов она отсортирует их правильно, с наибольшим внизу. Выход каждого зеленого или синего ящика будет отсортированной последовательностью, поэтому выход каждой пары смежных списков будет битоническим, потому что верхний — синий, а нижний — зеленый. Каждый столбец синих и зеленых ящиков берет N отсортированных последовательностей и объединяет их в пары, чтобы сформировать N/2 битонических последовательностей, которые затем сортируются ящиками в этом столбце, чтобы сформировать N/2 отсортированных последовательностей. Этот процесс начинается с того, что каждый вход считается отсортированным списком из одного элемента, и продолжается по всем столбцам, пока последний не объединит их в один отсортированный список. Поскольку последний этап был синим, этот окончательный список будет иметь наибольший элемент внизу.
Каждый зеленый ящик на схеме выше выполняет ту же операцию, что и синий ящик, но с сортировкой в противоположном направлении. Таким образом, каждый зеленый ящик можно заменить синим ящиком, за которым следует кроссовер, где все провода перемещаются в противоположное положение. Это позволило бы всем стрелкам указывать в одном направлении, но не позволило бы горизонтальным линиям быть прямыми. Однако аналогичный кроссовер можно было бы разместить справа от нижней половины выходов любого красного блока, и сортировка все равно работала бы правильно, потому что обратная битоническая последовательность все еще является битонической. Если затем красный ящик имеет кроссовер до и после него, его можно перестроить внутри так, чтобы два кроссовера отменились, и провода снова стали прямыми. Таким образом, следующая схема эквивалентна приведенной выше, где каждый зеленый ящик стал синим плюс кроссовер, а каждый оранжевый ящик является красным ящиком, который поглотил два таких кроссовера:
Наконечники стрелок не нарисованы, поскольку каждый компаратор сортирует в одном направлении. Синие и красные блоки выполняют те же операции, что и раньше. Оранжевые блоки эквивалентны красным блокам, в которых порядок последовательности обратен для нижней половины его входов и нижней половины его выходов. Это наиболее распространенное представление битонной сортировочной сети. В отличие от предыдущей интерпретации, поскольку элементы остаются логически упорядоченными, это представление легко расширить до случая, не являющегося степенью двойки (где каждое сравнение и обмен игнорирует любой случай, когда больший индекс выходит за пределы диапазона).
Ниже представлена реализация битональной сортировки слиянием без рекурсии, когда длина массива равна степени двойки: [2]
// задан массив arr длины n, этот код сортирует его на месте // все индексы начинаются от 0 до n-1 for ( k = 2 ; k <= n ; k *= 2 ) // k удваивается на каждой итерации for ( j = k / 2 ; j > 0 ; j /= 2 ) // j уменьшается вдвое на каждой итерации с отсечением дробных частей for ( i = 0 ; i < n ; i ++ ) l = bitwiseXOR ( i , j ); // в языках, подобных C, это "i ^ j" if ( l > i ) if ( ( bitwiseAND ( i , k ) == 0 ) AND ( arr [ i ] > arr [ l ]) OR ( bitwiseAND ( i , k ) != 0 ) AND ( arr [ i ] < arr [ l ]) ) поменять местами элементы arr [ i ] и arr [ l ]