Bitonic сортировщик - Bitonic sorter

Bitonic сортировщик

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

Bitonic mergesort - это параллельный алгоритм сортировки. Он также используется в качестве метода построения сортировочной сети . Алгоритм был разработан Кеном Батчером . Результирующие сети сортировки состоят из компараторов и имеют задержку , где - количество сортируемых элементов. ${\ Displaystyle О (п \ журнал ^ {2} (п))}$${\ Displaystyle О (\ журнал ^ {2} (п))}$${\ displaystyle n}$

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

Сложность

Пусть и . ${\ displaystyle p = \ lfloor \ log _ {2} n \ rfloor}$${\ Displaystyle д = \ lceil \ журнал _ {2} п \ rceil}$

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

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

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

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

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

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

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

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

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

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

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

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

Пример кода

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

    // 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
• Учебник с анимированными картинками и рабочим кодом