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

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

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

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

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

Сложность

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример кода

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

    // учитывая массив arr длины n, этот код сортирует его на месте    // все индексы идут от 0 до n-1    за (k = 2; k <= п; k *= 2) // k удваивается на каждой итерации        за (j = k/2; j > 0; j /= 2) // j уменьшается вдвое на каждой итерации с отсечением дробных частей            за (я = 0; я < п; я++)                л = побитовый XOR (я, j); // в C-подобных языках это "i ^ j"                если (л > я)                    если (  (побитовое И (я, k) == 0) И (обр[я] > обр[л])                       ИЛИ ЖЕ (побитовое И (я, k) != 0) И (обр[я] < обр[л]) )                          замена то элементы обр[я] и обр[л]

Смотрите также

• Сортировка по четным и нечетным дозаторам

Рекомендации

1. Битоническая сортировочная сеть для n не степень двойки
2. Исходный исходный код на C был по адресу https://www2.cs.duke.edu/courses/fall08/cps196.1/Pthreads/bitonic.c (самая последняя функция в файле). Для Википедии он был заменен на общий синтаксис псевдокода, а не на C.

внешняя ссылка

• Обсуждение этого алгоритма
• Код ссылки в NIST
• Учебник с анимированными картинками и рабочим кодом