Битонная сортировка

Битонная сортировка
Битонная сортировочная сеть для восьми входов
Автор	Кеннет Эдвард Бэтчер
Предназначение	Алгоритм сортировки
Худшее время	$O(\log ^{2}(n))$
Лучшее время	$O(\log ^{2}(n))$
Среднее время	$O(\log ^{2}(n))$

Битонная сортировка (англ. Bitonic sorter) — параллельный алгоритм сортировки данных, метод для создания сортировочной сети. Разработан американским информатиком Кеннетом Батчером в 1968 году. Один из первых параллельных алгоритмов сортировки. В основе алгоритма лежит понятие «битонной последовательности». Название было выбрано по аналогии с монотонной последовательностью.

В книге Батчера и Шереназа Баддара о сортировочных сетях упоминается, что название является неграмотным, так как комбинирует латинскую приставку и греческий корень. Более правильным названием было бы «дитонная» (ditonic).

Описание алгоритма

Алгоритм основан на сортировке битонных последовательностей. Такой последовательностью называется последовательность, которая сначала монотонно не убывает, а затем монотонно не возрастает, либо приводится к такому виду в результате циклического cдвига.

Любая последовательнось, входящая в битонную, любая последовательность состоящая из одного или двух элементов, а также любая монотонная последовательность также является битонной. Например, последовательности {3,5,10,4,1}, {1,5}, {10,14,5,-1,-4} являются битонными, а {4,6,1,9,2} не является. Каждое множество неотсортированных элементов можно считать множеством битонных последовательностей, состоящих из двух элементов.

Процесс битонного слияния преобразует битонную последовательность в полностью отсортированную последовательность. Алгоритм битонной сортировки состоит из применения битонных преобразований до тех пор, пока множество не будет полностью отсортировано.

Пример

Diagram of the bitonic sorting network with 16 inputs and arrows

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

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

Каждый столбец синих и зеленых прямоугольников принимает N отсортированных последовательностей (на самом первом шаге 16 отсортированных последовательностей, состоящих из 1 элемента) и преобразует их в N/2 отсортированных последовательностей.

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

Diagram of the bitonic sorting network with 16 inputs

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

Таким образом все синие прямоугольники на рисунке выполняют одинаковые операции. Коричневые прямоугольники являются модифицированными красными блоками, входы и выходы нижней части которых подсоединены в обратном порядке.

Влияние и применение

Битонная сортирока является одним из первых параллельных алгоритмов сортировки. Публикация этого алгоритма, наряду с также предложенным Батчером алгоритмом четно-нечетной сортировки слиянием, стимулировала развитие проектирования и анализа параллельных алгоритмов в общем и параллельной сортировки в частности.

Благодаря высокой параллельности, битонные сортировщики широко применяются в устройствах, нацеленных на массивные параллельные вычисления, таких как графические процессоры и ПЛИС, но редко используется в современных суперкомпьютерах.

В ранних графических процессорах, в связи с ограниченным API и недоступностью операции рассеяния, битонная сортировка была доминирующим алгоритмом. Специально для графических процессоров был разработан алгоритм «GNUTeraSort», основанный на битонной и поразрядной сортировке, а затем GPU-ABiSort, использующий адаптивную битонную сортировку. С появлением программно-аппаратной архитектуры CUDA были представлены эффективные версии других параллельных алгоритмов сортировки и в настоящее время на GPU доминирует поразрядная сортировка.

Литература

• Laxmikant V. Kalé, Edgar Solomonik. Sorting (англ.) // Encyclopedia of Parallel Computing : энциклопедия. — Springer, 2011. — P. 1855-1861. — ISBN 978-0-387-09765-7.
• Selim G. Akl. Bitonic Sort (англ.) // Encyclopedia of Parallel Computing : энциклопедия. — Springer, 2011. — P. 139-146. — ISBN 978-0-387-09765-7.
• Sherenaz W. Al-Haj Baddar, Kenneth E. Batcher. Bitonic merging // Designing Sorting Networks: A New Paradigm. — Springer, 2012. — С. 2-5. — 148 с. — ISBN 978-1461418504.
• Donald E. Knuth. Bitonic sorting // The art of computer programming. — 2. — Addison-Wesley, 1998. — Т. 3. — С. 230-232. — 780 с. — ISBN 9780201896855.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Bitonic sorting // Introduction to algorithms. — 2. — MIT Press, 2001. — С. 608-611. — 984 с. — ISBN 9780070131514.
• Mueller R., Teubner J., Alonso G. Data processing on FPGAs (англ.) // Proceedings of the VLDB Endowment. — 2009. — August. — P. 910-921. — doi:10.14778/1687627.1687730.
• Owens J. D. et al. GPU Computing (англ.) // Proceedings of the IEEE. — 2008. — May (vol. 96, no. 5). — P. 879 - 899. — doi:10.1109/JPROC.2008.917757.