Участник:Снисаренко Ольга/Алгоритм четно-нечетного слияния Бетчера

Алгоритм четно-нечетного слияния Бетчера

Алгоритм четно-нечетного слияния Бетчера (odd-even mergesort) является вариантом сортировки слиянием, который использует параллельные вычисления для ускорения процесса сортировки. Он был разработан в 1968 году американским информатиком Ричардом Бетчером.

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

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

Алгоритм не слишком популярный и не слишком известный. Однако он достаточно легко параллелится и его реализация не слишком сложна. Он основан на алгоритме слияния, который объединяет две отсортированные половины последовательности в полностью отсортированную последовательность. В отличие от сортировки слиянием, этот алгоритм не зависит от данных, т.е. одни и те же сравнения выполняются независимо от фактических данных. Следовательно, четно-нечетную сортировку слиянием можно реализовать как сортировочную сеть.[1] Вместе с битонной сортировкой является одним из первых методов построения сортировочной сети для любого количества входов. [2]

Время работы алгоритма составляет O(log2(n)) (с использованием параллелизма), как и в алгоритмах битонной сортировки и сортировки Шелла. Однако сортировка слиянием нечетной четности требует наименьшего количества операций сравнения.

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

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

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

Идея алгоритма Бэтчера заключается в следующем утверждении: если вы разделите последовательность пополам, далее рекурсивно отсортируете первую половину списка, а так же рекурсивно отсортируете вторую половину отедельно, а затем отсортируете записи с нечетным индексом всей последовательности (первая, третья, пятая,...) и записи с четным индексом всей последовательности (второй, четвертый, шестой,...) отдельно, то после повторения операций сравнения между отдельными парами на четных и нечетных позициях элементов, мы получим отсортированный список.

К примеру:

Давайте посмотрим, что происходит с конкретным списком длины 8. Предположим, нам дан следующий список

2 7 6 3 9 4 1 8

Мы хотим отсортировать его от меньшего к большему. Если отсортировать первую и вторую половинки отдельно, получим:

2 3 6 7 1 4 8 9

Сортировка ключей с нечетным индексом (2, 6, 1, 8), а затем ключей с четным индексом (3, 7, 4, 9) при выходе их в нечетных и четных местах соответственно дает:

1 3 2 4 6 7 8 9

Этот список теперь почти отсортирован: делаем сравнение между элементами в позициях (2 и 3), (4 и 5) и (6 и 7) фактически завершат сортировку.[3]

Входные и выходные данные алгоритма

Исходные данные: последовательность a₀, ..., a_n-1 длины n > 1 , где половины a₀, ..., a_n/2-1 and a_n/2, ..., a_n-1 отсортированы (n является степенью 2) [4] Выходные данные: отсортированная последовательность

Литература

1. Habr:Четно-нечетная сортировка слиянием Бэтчера [[1]]
2. Википедия: Битонная сортировка [[2]]
3. Batcher’s Algorithm(англ) //Prof. Michel Goemans - Fall 2010 - Prof. Michel Goemans[[3]]
4. Odd-even mergesort:[[4]]