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

Снисаренко Ольга в 20:58, 5 декабря 2023

2023-12-05T20:58:09Z

@@ Строка 40: / Строка 40: @@
 ====  Вычислительное ядро алгоритма ====
 ==== Макроструктура алгоритма ====
 ==== Схема реализации последовательного алгоритма ====
 ==== Последовательная сложность алгоритма ====
 ==== Информационный граф ====
 ==== Ресурс параллелизма алгоритма ====
 ==== Входные и выходные данные алгоритма ====
 Исходные данные: последовательность 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]
@@ Строка 50: / Строка 76: @@
 ==== Свойства алгоритма ====
 === Программная реализация алгоритма ===
 ==== Особенности реализации последовательного алгоритма ====
 ==== Локальность данных и вычислений ====
 ==== Масштабируемость алгоритма и его реализации ====
 ====Динамические характеристики и эффективность реализации алгоритма ====
 ==== Выводы для классов архитектур ====
 ====  Существующие реализации алгоритма ====
 ===  Литература ===
 #  Habr:Четно-нечетная сортировка слиянием Бэтчера [[https://habr.com/ru/articles/261777/]]

Снисаренко Ольга: Новая страница: «'''Алгоритм четно-нечетного слияния Бетчера''' Алгоритм четно-нечетного слияния Бе...»

2023-10-31T18:35:02Z

Новая страница: «'''<big>Алгоритм четно-нечетного слияния Бетчера</big>''' Алгоритм четно-нечетного слияния Бе...»

Новая страница

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

Алгоритм четно-нечетного слияния Бетчера (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]

==== Вычислительное ядро алгоритма ====
==== Макроструктура алгоритма ====
==== Схема реализации последовательного алгоритма ====
==== Последовательная сложность алгоритма ====
==== Информационный граф ====
==== Ресурс параллелизма алгоритма ====
==== Входные и выходные данные алгоритма ====
Исходные данные: последовательность a0, ..., an-1 длины n > 1 , где половины a0, ..., an/2-1 and an/2, ..., an-1 отсортированы (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]]