Bitonic mergesort — это параллельный алгоритм сортировки. Он также используется в качестве метода построения сортировочной сети . Алгоритм был разработан Кеном Бэтчером . Получающиеся сети сортировки состоят из компараторов и имеют задержку , где — количество элементов, подлежащих сортировке. [1] Это делает его популярным выбором для сортировки большого количества элементов в архитектуре, которая сама содержит большое количество параллельных исполнительных блоков, работающих синхронно, например, типичный графический процессор .
Сортированная последовательность — это монотонно неубывающая (или невозрастающая) последовательность. Битоническая последовательность — это последовательность с для некоторого или круговой сдвиг такой последовательности.
Пусть и .
Из алгоритма построения видно, что количество раундов параллельных сравнений определяется выражением .
Отсюда следует, что число компараторов ограничено (что устанавливает точное значение для степени 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 = побитовое XOR ( i , j ); // в C-подобных языках это "i ^ j" if ( l > i ) if ( ( побитовое AND ( i , k ) == 0 ) AND ( arr [ i ] > arr [ l ]) OR ( побитовое AND ( i , k ) != 0 ) AND ( arr [ i ] < arr [ l ])) ) поменять местами элементы arr [ i ] и arr [ l ]