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

'''<big>Алгоритм четно-нечетного слияния Бетчера</big>'''

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

=== Свойства и структура алгоритмов ===
==== Общее описание алгоритма ====


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

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

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

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

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

К примеру: <br>

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

2 7 6 3 9 4 1 8<br>

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

2 3 6 7 1 4 8 9<br>

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

1 3 2 4 6 7 8 9<br>

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


====  Вычислительное ядро алгоритма ====
==== Макроструктура алгоритма ====
==== Схема реализации последовательного алгоритма ====
==== Последовательная сложность алгоритма ====
==== Информационный граф ====
==== Ресурс параллелизма алгоритма ====
==== Входные и выходные данные алгоритма ====
Исходные данные: последовательность a<sub>0</sub>, ..., a<sub>n-1</sub> длины n > 1 , где половины  a<sub>0</sub>, ..., a<sub>n/2-1</sub> and a<sub>n/2</sub>, ..., a<sub>n-1</sub> отсортированы (n является степенью 2) [4]
Выходные данные: отсортированная последовательность

==== Свойства алгоритма ====
=== Программная реализация алгоритма ===
==== Особенности реализации последовательного алгоритма ====
==== Локальность данных и вычислений ====
==== Масштабируемость алгоритма и его реализации ====
====Динамические характеристики и эффективность реализации алгоритма ====
==== Выводы для классов архитектур ====
====  Существующие реализации алгоритма ====
===  Литература ===
#  Habr:Четно-нечетная сортировка слиянием Бэтчера [[https://habr.com/ru/articles/261777/]]
# Википедия: Битонная сортировка [[https://ru.wikipedia.org/wiki/%D0%91%D0%B8%D1%82%D0%BE%D0%BD%D0%BD%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0#:~:text=%D0%91%D0%B8%D1%82%D0%BE%D0%BD%D0%BD%D0%B0%D1%8F%20%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0%20(%D0%B0%D0%BD%D0%B3%D0%BB.,%D0%BB%D0%B5%D0%B6%D0%B8%D1%82%20%D0%BF%D0%BE%D0%BD%D1%8F%D1%82%D0%B8%D0%B5%20%C2%AB%D0%B1%D0%B8%D1%82%D0%BE%D0%BD%D0%BD%D0%BE%D0%B9%20%D0%BF%D0%BE%D1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE%D1%81%D1%82%D0%B8%C2%BB.]]
# Batcher’s Algorithm(англ) //Prof. Michel Goemans - Fall 2010 - Prof. Michel Goemans[[https://math.mit.edu/~shor/18.310/batcher.pdf]]
# Odd-even mergesort:[[https://hwlang.de/algorithmen/sortieren/networks/oemen.htm]]