tgoop.com/the_algorithms/4571
Last Update:
Битоническая сортировка
Алгоритм сортировки, названный в честь понятия «битонической последовательности».
Для эффективной работы алгоритма длина списка должна быть степенью 2.
Шаг 1: Разделите список на две равные половины. Отсортируйте каждую половину таким образом, чтобы она стала битонической последовательностью.
Шаг 2: Битоническое слияние. Слияние предполагает сравнение элементов из обеих последовательностей и их перестановку для сохранения битонического свойства.
Шаг 3: Продолжайте делить последовательности на половины и объединять их, пока не получите одну полную отсортированную битоническую последовательность.
Шаг 4: После получения отсортированной битонической последовательности переверните ее, чтобы отсортировать в желаемом порядке (по возрастанию или по убыванию).
Сложность: O(log^2n)
BY Алгоритмы и структуры данных

Share with your friend now:
tgoop.com/the_algorithms/4571