Участница:Полина Кривуля/Сеть битонной сортировки

1 Свойства и структура алгоритмов

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

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

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

Время работы алгоритма составляет [math] O(log^2(n))[/math] (в случае использования параллелизма).

1.2 Математическое описание алгоритма

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

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

Заметим, что в данном алгоритме необходимо, чтобы размер исходного массива был равен степени двойки. В противном случае, его придется дополнять фиктивными элементами, что, однако, не влияет не асимптотику .