Алгоритм слияния

Алгоритмы слияния - это семейство алгоритмов, которые принимают несколько отсортированных списков в качестве входных и создают один список в качестве выходных данных, содержащий все элементы входных списков в отсортированном порядке. Эти алгоритмы используются в качестве подпрограмм в различных алгоритмах сортировки , наиболее известный из которых - сортировка слиянием .

Заявление [ править ]

Пример сортировки слиянием

Алгоритм слияния играет решающую роль в алгоритме сортировки слиянием, алгоритме сортировки на основе сравнения . Концептуально алгоритм сортировки слиянием состоит из двух шагов:

Рекурсивно разделите список на подсписки (примерно) равной длины, пока каждый подсписок не будет содержать только один элемент, или, в случае итеративной (восходящей) сортировки слиянием, рассмотрите список из n элементов как n подсписок размера 1. A Список, содержащий единственный элемент, по определению отсортирован.
Неоднократно объединяйте подсписки, чтобы создать новый отсортированный подсписок, пока один список не будет содержать все элементы. Единый список - это отсортированный список.

Алгоритм слияния многократно используется в алгоритме сортировки слиянием.

Пример сортировки слиянием приведен на иллюстрации. Он начинается с несортированного массива из 7 целых чисел. Массив разделен на 7 разделов; каждый раздел содержит 1 элемент и сортируется. Затем отсортированные разделы объединяются для создания более крупных отсортированных разделов, пока не останется 1 раздел, отсортированный массив.

Объединение двух списков [ править ]

Объединение двух отсортированных списков в один может быть выполнено за линейное время и линейное или постоянное пространство (в зависимости от модели доступа к данным). Следующий псевдокод демонстрирует алгоритм , который сливается входные списки (либо связанные списки или массивы ) и $Б$ в новый список $C$ . ^[1]^[2]^:¹⁰⁴ Функция головки дает первый элемент списка; «удаление» элемента означает удаление его из списка, обычно путем увеличения указателя или индекса.

алгоритм слияния (A, B) - это  входы A, B: список возвращает список C: = новый пустой список пока A не пусто, а B не пусто ,  если head (A) ≤ head (B), то добавить голову (A) к C опустить голову A еще добавить голову (B) к C опустить голову B // К настоящему времени либо A, либо B пусто. Осталось очистить другой список ввода.  пока А не пусто делать добавить голову (A) к C опустить голову A в то время как B не пусто делать добавить голову (B) к C опустить голову B вернуть C

Когда входы представляют собой связанные списки, этот алгоритм может быть реализован для использования только постоянного количества рабочего пространства; указатели в узлах списков могут быть повторно использованы для бухгалтерского учета и для построения окончательного объединенного списка.

В алгоритме сортировки слиянием, эта подпрограмма , как правило , используется для объединения двух суб-массивов A [lo..mid] , А [mid..hi] из одного массива A . Это можно сделать, скопировав подмассивы во временный массив, а затем применив описанный выше алгоритм слияния. ^[1] Выделения временного массива можно избежать, но за счет скорости и простоты программирования. Были разработаны различные алгоритмы слияния на месте, ^[3] иногда жертвуя линейным временем, чтобы получить алгоритм $O$ $($ $n$ $log$ $n$ $)$ ; ^[4] см. Сортировку слиянием § Варианты для обсуждения.

K-way слияние [ править ]

$k$ -way слияние обобщает двоичное слияние для произвольного числа $k$ отсортированных списков ввода. Приложения $k-$ way слияния возникают в различных алгоритмах сортировки, включая сортировку терпения ^[5] и внешний алгоритм сортировки , который делит входные данные на $k = 1 / M - 1$ блок, который помещается в памяти, сортирует их один за другим, а затем объединяет эти блоки. ^[2]^{: 119–120}

Существует несколько решений этой проблемы. Наивное решение - сделать цикл по $k$ спискам, чтобы каждый раз выбирать минимальный элемент, и повторять этот цикл, пока все списки не станут пустыми:

Вход: список из $k$ списков.
Пока какой-либо из списков не пуст:
- Прокрутите списки, чтобы найти тот, у которого минимальный первый элемент.
- Выведите минимальный элемент и удалите его из списка.

В худшем случае этот алгоритм выполняет $(k -1) (n - k / 2)$ сравнения элементов для выполнения своей работы, если в списках всего $n$ элементов. ^[6] Его можно улучшить, сохранив списки в очереди с приоритетами ( min-heap ) с ключом их первого элемента:

Создайте минимальную кучу $h$ из $k$ списков, используя первый элемент в качестве ключа.
Пока какой-либо из списков не пуст:
- Пусть $i = find-min (h)$ .
- Выведите первый элемент списка $i$ и удалите его из списка.
- Повторно нагружать $h$ .

Поиск следующего наименьшего элемента для вывода (find-min) и восстановление порядка кучи теперь могут выполняться за время $O (log k)$ (более конкретно, $2⌊log k ⌋$ сравнений ^[6] ), и полная проблема может быть решено за время $O (n log k)$ (примерно $2 n ⌊log k ⌋$ сравнений). ^[6]^[2]^{: 119–120}

Третий алгоритм решения проблемы - это решение « разделяй и властвуй» , основанное на алгоритме двоичного слияния:

Если $k = 1$ , вывести единственный входной список.
Если $k = 2$ , выполните двоичное слияние.
В $противном случае$ рекурсивно объедините первые $⌊$ $k$ $/ 2⌋$ списков и последние $⌈ k / 2⌉$ списки, а затем объедините их двоичным образом.

Когда входные списки для этого алгоритма упорядочены по длине, сначала $самые$ короткие, для этого требуется меньше $n log k$ сравнений, т. $Е.$ Меньше половины числа, используемого алгоритмом на основе кучи; на практике он может быть таким же быстрым или медленным, как алгоритм на основе кучи. ^[6]

Параллельное слияние [ править ]

Параллельная версия алгоритма двоичного слияния может служить в качестве строительного блока в параллельной сортировки слиянием . Следующий псевдокод демонстрирует этот алгоритм в параллельном стиле « разделяй и властвуй» (адаптировано из Cormen et al. ^[7]^{: 800} ). Он работает на двух отсортированных массивов $A$ и $B$ и записывает отсортированный вывод в массив $C$ . Обозначение A [i ... j] обозначает часть $A$ от индекса $i$ до $j$ , исключая.

алгоритм слияния (A [i ... j], B [k ... ℓ], C [p ... q]) - это  входы A, B, C: массив i, j, k, ℓ, p, q: индексы пусть m = j - i, п = ℓ - к если m <n, то поменяйте местами A и B // убедитесь, что A является большим массивом: i, j все еще принадлежат A; k, ℓ к B поменять местами m и n если m ≤ 0, то  вернуть  // базовый случай, объединять нечего пусть r = ⌊ (i + j) / 2⌋ let s = binary-search (A [r], B [k ... ℓ]) пусть t = p + (r - i) + (s - k) C [t] = A [r] параллельно делаем объединить (A [i ... r], B [k ... s], C [p ... t]) объединить (A [r + 1 ... j], B [s ... ℓ], C [t + 1 ... q])

Алгоритм работает путем разделения $A$ или $B$ , в зависимости от того, что больше, на (почти) равные половины. Затем он разбивает другой массив на часть со значениями, меньшими, чем средняя точка первого, и часть с большими или равными значениями. (В бинарном поиске возвращается подпрограмма индекс в $B$ , где $[$ $г$ $]$ был бы, если бы это было в $B$ , что это всегда число между $к$ и $л$ .) Наконец, каждая пара половинок сливается рекурсивно, а поскольку рекурсивные вызовы независимы друг от друга, они могут выполняться параллельно. Гибридный подход, при котором последовательный алгоритм используется для базового случая рекурсии, показал себя на практике хорошо ^[8]

Работа выполняется с помощью алгоритма для двух массивов , занимающих в общей сложности $п$ элементов, то есть, время работы в серийную версию этого, является $О (п)$ . Это является оптимальным , так как $п$ элементы должны быть скопированы в $C$ . Чтобы вычислить диапазон алгоритма, необходимо вывести отношение повторения . Поскольку два рекурсивных вызова слияния выполняются параллельно, необходимо учитывать только более затратный из двух вызовов. В худшем случае максимальное количество элементов в одном из рекурсивных вызовов не больше, поскольку массив с большим количеством элементов идеально разделяется пополам. Добавление ${\ textstyle {\ frac {3} {4}} п}$ $\Theta \left(\log(n)\right)$ стоимость двоичного поиска, мы получаем это повторение как верхнюю границу:

$T_{\infty }^{\text{merge}}(n)=T_{\infty }^{\text{merge}}\left({\frac {3}{4}}n\right)+\Theta \left(\log(n)\right)$

Решение состоит в том, что на идеальной машине с неограниченным количеством процессоров требуется столько времени. ^[7]^:^801–802 $T_{\infty }^{\text{merge}}(n)=\Theta \left(\log(n)^{2}\right)$

Примечание. Процедура нестабильна : если равные элементы разделены разделением $A$ и $B$ , они будут чередоваться в $C$ ; также обмен местами $A$ и $B$ уничтожит порядок, если одинаковые элементы распределены между обоими входными массивами. В результате при использовании этого алгоритма для сортировки получается нестабильная сортировка.

Языковая поддержка [ править ]

Некоторые компьютерные языки предоставляют встроенную или библиотечную поддержку для объединения отсортированных коллекций .

C ++ [ править ]

В C ++ «сек Стандартная библиотека шаблонов имеет функцию зЬй :: слияния , который объединяет два сортируются диапазоны итераторы и зЬй :: inplace_merge , который объединяет два последовательных отсортированных диапазонов в месте . Кроме того, класс std :: list (связанный список) имеет собственный метод слияния, который объединяет другой список в себя. Тип объединяемых элементов должен поддерживать оператор «меньше» ( < ) или должен быть предоставлен с настраиваемым компаратором.

C ++ 17 допускает различные политики выполнения, а именно последовательное, параллельное и неупорядоченное параллельное выполнение. ^[9]

Python [ править ]

Python «s стандартная библиотека (с 2.6) также имеет слияние функцию в heapq модуле, который принимает несколько отсортированных итерируемый, и объединяют их в один итератор. ^[10]

См. Также [ править ]

Слияние (контроль версий)
Присоединиться (реляционная алгебра)
Присоединиться (SQL)
Присоединиться (Unix)

Ссылки [ править ]

^ a b Скиена, Стивен (2010). Руководство по разработке алгоритмов (2-е изд.). Springer Science + Business Media . п. 123. ISBN 978-1-849-96720-4.
^ a b c Курт Мельхорн ; Питер Сандерс (2008). Алгоритмы и структуры данных: базовый набор инструментов . Springer. ISBN 978-3-540-77978-0.
^ Катаянен, Юрки; Пасанен, Томи; Теухола, Юкка (1996). «Практическая сортировка слиянием на месте». Nordic J. Computing . 3 (1): 27–40. CiteSeerX 10.1.1.22.8523 .
^ Ким, Пок-Сон; Куцнер, Арне (2004). Стабильное слияние минимальной памяти путем симметричных сравнений . Европейский Symp. Алгоритмы. Конспект лекций по информатике. 3221 . С. 714–723. CiteSeerX 10.1.1.102.4612 . DOI : 10.1007 / 978-3-540-30140-0_63 . ISBN 978-3-540-23025-0.
^ Чандрамули, Бадриш; Гольдштейн, Джонатан (2014). Терпение - это добродетель: пересмотр слияния и сортировки на современных процессорах . SIGMOD / PODS.
^ a b c d Грин, Уильям А. (1993). k-way слияние и k-арная сортировка (PDF) . Proc. 31-я ежегодная Юго-восточная конференция ACM. С. 127–135.
^ а б Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2009) [1990]. Введение в алгоритмы (3-е изд.). MIT Press и McGraw-Hill. ISBN 0-262-03384-4.
^ Victor J. Duvanenko (2011), "Параллельный Merge" , журнал доктора Добба
^ "std: merge" . cppreference.com. 2018-01-08 . Проверено 28 апреля 2018 .
^ https://docs.python.org/library/heapq.html#heapq.merge

Дальнейшее чтение [ править ]

Дональд Кнут . Искусство программирования , Том 3: Сортировка и поиск , третье издание. Аддисон-Уэсли, 1997. ISBN 0-201-89685-0 . Страницы 158–160 раздела 5.2.4: Сортировка по объединению. Раздел 5.3.2: Слияние минимального сравнения, стр. 197–207.

Внешние ссылки [ править ]

Высокопроизводительная реализация параллельного и последовательного слияния на C # с исходным кодом в GitHub и C ++ GitHub

[skiena-1] Скиена, Стивен (2010). Руководство по разработке алгоритмов (2-е изд.). Springer Science + Business Media . п. 123. ISBN 978-1-849-96720-4.

[toolbox-2] Курт Мельхорн ; Питер Сандерс (2008). Алгоритмы и структуры данных: базовый набор инструментов . Springer. ISBN 978-3-540-77978-0.

[3] Катаянен, Юрки; Пасанен, Томи; Теухола, Юкка (1996). «Практическая сортировка слиянием на месте». Nordic J. Computing . 3 (1): 27–40. CiteSeerX 10.1.1.22.8523 .

[4] Ким, Пок-Сон; Куцнер, Арне (2004). Стабильное слияние минимальной памяти путем симметричных сравнений . Европейский Symp. Алгоритмы. Конспект лекций по информатике. 3221 . С. 714–723. CiteSeerX 10.1.1.102.4612 . DOI : 10.1007 / 978-3-540-30140-0_63 . ISBN 978-3-540-23025-0.

[Chandramouli-5] Чандрамули, Бадриш; Гольдштейн, Джонатан (2014). Терпение - это добродетель: пересмотр слияния и сортировки на современных процессорах . SIGMOD / PODS.

[greene-6] Грин, Уильям А. (1993). k-way слияние и k-арная сортировка (PDF) . Proc. 31-я ежегодная Юго-восточная конференция ACM. С. 127–135.

[clrs-7] а б Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2009) [1990]. Введение в алгоритмы (3-е изд.). MIT Press и McGraw-Hill. ISBN 0-262-03384-4.

[vjd-8] Victor J. Duvanenko (2011), "Параллельный Merge" , журнал доктора Добба

[9] "std: merge" . cppreference.com. 2018-01-08 . Проверено 28 апреля 2018 .

[10] ttps://docs.python.org/library/heapq.html#heapq.merge

[1]

vтеАлгоритмы сортировки
Теория	Теория вычислительной сложности Обозначение Big O Общий заказ Списки Замена Стабильность Сравнительная сортировка Адаптивная сортировка Сортировочная сеть Целочисленная сортировка X + Y сортировка Трансдихотомическая модель Квантовая сортировка
Обменные сорта	Пузырьковая сортировка Сорт коктейльный шейкер Нечетно-четная сортировка Сортировка гребней Сортировка гномов Пропорция расширить сортировку Быстрая сортировка Slowsort Stooge sort Богосорт
Выборочные сорта	Выборочная сортировка Heapsort Smoothsort Сортировка декартовых деревьев Сортировка турнира Цикл сортировки Сортировка слабой кучи
Вставки	Вставка сортировки Shellsort Сортировка Сортировка дерева Сортировка библиотеки Сортировка терпения
Сортировка слияния	Сортировка слиянием Каскадная сортировка слиянием Осциллирующая сортировка слиянием Полифазная сортировка слиянием
Виды распространения	Американский флаг сортировка Сортировка бисера Ковшовая сортировка Burstsort Счетная сортировка Сортировка интерполяции Сорт голубятни Proxmap сортировка Radix sort Flashsort
Параллельные сортировки	Bitonic сортировщик Сортировка по четным и нечетным дозаторам Сеть попарной сортировки Samplesort
Гибридные сорта	Блокировать сортировку слиянием Сорт Киркпатрика-Райша Тимсорт Интросорт Spreadsort Сортировка слиянием-вставкой
Другой	Топологическая сортировка Предпотопологический порядок Сортировка блинов Сортировка спагетти