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

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

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

Битонная сортировка – это параллельный алгоритм сортировки, основанный на битонной последовательности. Алгоритм разработан американским информатиком Кеннетом Бэтчером в 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]\displaystyle{ O(log^2(n)) }[/math].