Битонический сортировщик

Битонический сортировщик

Сеть битонной сортировки с восемью входами.
Сорт	Алгоритм сортировки
Структура данных	Множество
Худшая производительность	$O(\log ^{2}(n))$ параллельное время
Лучшая производительность	$O(\log ^{2}(n))$ параллельное время
Средняя производительность	$O(\log ^{2}(n))$ параллельное время
Наихудшая пространственная сложность	$O(n\log ^{2}(n))$ непараллельное время
Оптимальный	Нет

Bitonic mergesort — это параллельный алгоритм сортировки. Он также используется в качестве метода построения сортировочной сети . Алгоритм был разработан Кеном Бэтчером . Полученные сортировочные сети состоят из $O(n\log ^{2}(n))$ компараторов и имеют задержку $O(\log ^{2}(n))$, где $n$ количество элементов, подлежащих сортировке. Это делает его популярным выбором для сортировки большого количества элементов в архитектуре, которая сама содержит большое количество параллельных исполнительных блоков, работающих синхронно , например, в типичном графическом процессоре .

Сортированная последовательность — это монотонно неубывающая (или невозрастающая) последовательность. Битоническая которой последовательность – это последовательность, в $x_{0}\leq \cdots \leq x_{k}\geq \cdots \geq x_{n-1}$ для некоторых $k,0\leq k<n$, или круговой сдвиг такой последовательности.

Сложность

Позволять $p=\lfloor \log _{2}n\rfloor$ и $q=\lceil \log _{2}n\rceil$.

Из алгоритма построения видно, что количество раундов параллельных сравнений определяется выражением $q(q+1)/2$.

Отсюда следует, что число компараторов $c$ ограничен $2^{p-1}\cdot p(p+1)/2\leq c\leq \lfloor {n/2}\rfloor \cdot q(q+1)/2$ (что устанавливает точное значение для $c$ когда $n$ является степенью 2).

Хотя абсолютное число сравнений обычно выше, чем при сортировке «нечет-чет» Бэтчера , многие последовательные операции в битонной сортировке сохраняют локальность ссылки , что делает реализации более удобными для кэширования и, как правило, более эффективными на практике.

Как работает алгоритм

Ниже представлена ​​битоническая сортировочная сеть с 16 входами:

16 чисел входят в качестве входов на левом конце, скользят по каждому из 16 горизонтальных проводов и выходят на выходы на правом конце. Сеть предназначена для сортировки элементов, наибольшее число которых находится внизу.

Стрелки — компараторы. Всякий раз, когда два числа достигают двух концов стрелки, они сравниваются, чтобы убедиться, что стрелка указывает в сторону большего числа. Если они вышли из строя, их меняют местами. Цветные рамки предназначены только для иллюстрации и не влияют на алгоритм.

Каждое красное поле имеет одинаковую структуру: каждый ввод в верхней половине сравнивается с соответствующим вводом в нижней половине, при этом все стрелки направлены вниз (темно-красный) или все вверх (светло-красный). Если входные данные образуют битоническую последовательность (одна неубывающая последовательность, за которой следует одна невозрастающая или наоборот), то выходные данные будут формировать две битонические последовательности. Верхняя половина выходных данных будет битонической, а нижняя половина — битонной, причем каждый элемент верхней половины меньше или равен каждому элементу нижней половины (для темно-красного) или наоборот (для светло-красного). Эта теорема не очевидна, но ее можно проверить, внимательно рассмотрев все случаи сравнения различных входных данных, используя принцип нуля-единицы , где битоническая последовательность представляет собой последовательность нулей и единиц, содержащую не более двух «10». " или "01" подпоследовательности.

Красные прямоугольники объединяются, образуя синие и зеленые прямоугольники. Каждый такой блок имеет одинаковую структуру: красный блок применяется ко всей входной последовательности, затем к каждой половине результата, затем к каждой половине каждого из этих результатов и так далее. Все стрелки направлены вниз (синие) или все стрелки вверх (зеленые). Эта структура известна как сеть-бабочка . Если входные данные в это поле являются битоническими, то выходные данные будут полностью отсортированы в порядке возрастания (синий) или убывания (зеленый). Если число попадает в синее или зеленое поле, то первое красное поле отсортирует его в правильную половину списка. Затем он пройдет через меньшую красную рамку, которая сортирует его по правильной четверти списка внутри этой половины. Это продолжается до тех пор, пока он не будет отсортирован в правильное положение. Таким образом, выходные данные зеленого или синего поля будут полностью отсортированы.

Зеленые и синие коробки объединяются, образуя всю сортировочную сеть. Для любой произвольной последовательности входных данных он отсортирует их правильно, начиная с самого большого значения внизу. Выходные данные каждого зеленого или синего поля будут представлять собой отсортированную последовательность, поэтому выходные данные каждой пары соседних списков будут битоническими, поскольку верхний — синий, а нижний — зеленый. Каждый столбец синих и зеленых прямоугольников содержит N отсортированных последовательностей и объединяет их попарно, образуя N/2 битонических последовательностей, которые затем сортируются по полям в этом столбце для формирования N/2 отсортированных последовательностей. Этот процесс начинается с того, что каждый вход считается отсортированным списком из одного элемента, и продолжается по всем столбцам, пока последний не объединит их в один отсортированный список. Поскольку последний этап был синим, в последнем списке самый большой элемент будет внизу.

Альтернативное представительство

Каждый зеленый прямоугольник на диаграмме выше выполняет ту же операцию, что и синий, но с сортировкой в ​​противоположном направлении. Таким образом, каждый зеленый квадрат можно заменить синим блоком, за которым следует пересечение, при котором все провода перемещаются в противоположное положение. Это позволит всем стрелкам указывать в одном направлении, но не позволит горизонтальным линиям быть прямыми. Однако аналогичное пересечение можно разместить справа от нижней половины выходных данных любого красного блока, и сортировка по-прежнему будет работать правильно, поскольку обратная битоническая последовательность по-прежнему является битонной. Если у красного прямоугольника есть пересечение до и после него, его можно переставить внутри так, чтобы два пересечения нейтрализовались, и провода снова стали прямыми. Таким образом, следующая диаграмма эквивалентна приведенной выше, где каждый зеленый прямоугольник стал синим плюс кроссовер, а каждый оранжевый прямоугольник — красным блоком, поглотившим два таких пересечения:

Стрелки не рисуются, поскольку все компараторы сортируют в одном направлении. Синий и красный блоки выполняют те же операции, что и раньше. Оранжевые блоки эквивалентны красным блокам, в которых порядок последовательности изменен на обратный для нижней половины входов и нижней половины выходов. Это наиболее распространенное представление битонной сортировочной сети. В отличие от предыдущей интерпретации, поскольку элементы остаются логически упорядоченными, это представление легко расширить до случая, не являющегося степенью двойки (где каждое сравнение и замена игнорирует любой случай, когда больший индекс выходит за пределы диапазона).

Пример кода

Ниже приведена безрекурсивная реализация битонной сортировки слиянием, когда длина массива равна степени двойки:

    // given an array arr of length n, this code sorts it in place    // all indices run from 0 to n-1    for (k = 2; k <= n; k *= 2) // k is doubled every iteration        for (j = k/2; j > 0; j /= 2) // j is halved at every iteration, with truncation of fractional parts            for (i = 0; i < n; i++)                l = bitwiseXOR (i, j); // in C-like languages this is "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]) )                          swap the elements arr[i] and arr[l]

См. также

• Батчерная сортировка слиянием нечет-чет
• Попарная сортировочная сеть

Внешние ссылки

• Обсуждение этого алгоритма
• Справочный код в NIST
• Туториал с анимированными картинками и рабочим кодом