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

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

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

Битонная сортировка — один из старейших параллельных алгоритмов сортировки^[2]. Наряду с четно-нечетной сортировки слиянием, является одним из первых методов построения сортировочной сети для любого количества входов^[3].

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

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

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

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

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

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

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

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

В середине 1960-х годов Кеннет Бэтчер работал в Goodyear Aerospace^[англ.], где занимался проектированием параллельных процессоров с тысячами обрабатывающих элементов. Работая над решением задачи сортировки данных он пришел к выводу, что последовательные алгоритмы сортировки слишком медленные и необходимо изучить возможность создания параллельных алгоритмов сортировки. Он рассмотрел хорошо известную сортировку слиянием и обнаружил, что её первые шаги легко распараллеливаются, но более поздние слияния работают последовательно и требуют много времени. В результате он открыл два алгоритма, основанных на слиянии — битонную сортировку и четно-нечетную сортировку слиянием. Бэтчер представил эти алгоритмы в своей статье «Sorting networks and their applications» на конференции Joint Computer Conference^[англ.] в 1968 году^[3].

Сам Бэтчер позднее признал, что название является неграмотным, так как комбинирует латинскую приставку и греческий корень. Более правильным названием было бы «дитонная» (ditonic)^[3][5].

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

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

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

• 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.