Изменения

Перейти к: навигация, поиск

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

924 байта добавлено, 15:42, 17 января 2019
м
Нет описания правки
==Описание=='''Сортировка слиянием''' (англ. ''Merge sort'') {{---}} алгоритм сортировки. Он был пред­ло­жен Джо­ном фон Ней­ма­ном в 1945 го­ду. Это устойчивый ал­го­ритм, использующий <tex>O(n)</tex> дополнительной памяти и работающий за <tex>O(n</tex> <tex>\log (n))</tex> времени.
==Принцип работы==
[[Файл:Merging_two_arrays.png|270px|right|thumb|Пример работы процедуры слияния.]]
Алгоритм использует прицип «разделяй и властвуй»: задача разбивается на подзадачи меньшего размера, которые решаются по отдельности, после чего их решения комбинируются для получения решения исходной задачи. Конкретно процедуру сортировки слиянием можно описать следующим образом:
[[Файл:Merge sort1.png|300px|right|thumb|Пример работы рекурсивного алгоритма сортировки слиянием]] [[Файл:Merge sort itearative.png|300px|right|thumb|Пример работы итеративного алгоритма сортировки слиянием]] Алгоритм использует принцип «разделяй и властвуй»: задача разбивается на подзадачи меньшего размера, которые решаются по отдельности, после чего их решения комбинируются для получения решения исходной задачи. Конкретно процедуру сортировки слиянием можно описать следующим образом: # Если в рассматриваемом массиве один элемент, то он уже отсортирован {{---}} алгоритм завершает работу.
# Иначе массив разбивается на две части, которые сортируются рекурсивно.
# После сортировки двух частей массива к ним применяется процедура слияния, которая по двум отсортированным частям получает исходный отсортированный массив.
===Слияние двух массивов===
У нас есть два массива <tex>Aa</tex> и <tex>Bb</tex> (фактически это будут две части одного массива, но для удобства будем писать, что у нас просто два массива). Нам надо получить массив <tex>Cc</tex> размером <tex>|Aa| + |Bb|</tex>. Для этого можно применить процедуру слияния. Эта процедура заключается в том, что мы сравниваем элементы массивов (начиная с начала) и меньший из них записываем в финальный. И затем, в массиве у которого оказался меньший элемент, переходим к следующему элементу и сравниваем теперь его. В конце, если один из массивов закончился, мы просто дописываем в финальный другой массив. После мы наш финальный массив записываем заместо двух исходных и получаем отсортированный участок.
Ниже приведён псевдокод процедуры слияния, который сливает две части массива A — Множество отсортированных списков с операцией <tex>[left; mid)\mathrm{merge}</tex> и <tex>является [[mid; right)</tex>Моноид|моноидом]], где нейтральным элементом будет пустой список.
Ниже приведён псевдокод процедуры слияния, который сливает две части массива <tex>a</tex> {{---}} <tex>[left; mid)</tex> и <tex>[mid; right)</tex><code style="display: inline-block"> Merge'''function''' merge(A a : '''int[1..Nn]'''; left, mid, right : '''int'''):
it1 = 0
it2 = 0
'''while''' left + it1 < mid '''and''' mid + it2 < right
'''if''' Aa[left + it1] < Aa[mid + it2] result[it1 + it2] = Aa[left + it1]
it1 += 1
'''else'''
result[it1 + it2] = Aa[mid + it2]
it2 += 1
'''while''' left + it1 < mid
result[it1 + it2] = Aa[left + it1]
it1 += 1
'''while''' mid + it2 < right
result[it1 + it2] = Aa[mid + it2]
it2 += 1
'''for''' i = 0 '''to''' it1 + it2
Aa[left + i] = result[i]</code>
===Рекурсивный алгоритм===
Функция сортирует подотрезок массива с индексами в полуинтервале <tex>[left; right)</tex>.
[[Файл<code style="display:Merge sort1.png|300px|thumb|Пример работы рекурсивного алгоритма сортировки слиянием]]inline-block"> MergeSort'''function''' mergeSortRecursive(A a : '''int[1..Nn]'''; left, right : '''int'''):
'''if''' left + 1 >= right
'''return'''
mid = (left + right) / 2
MergeSortmergeSortRecursive(Aa, left, mid) MergeSortmergeSortRecursive(Aa, mid, right) Mergemerge(Aa, left, mid, right)</code>
===Итеративный алгоритм===
Функция сортирует подотрезок массива с индексами в полуинтервале При итеративном алгоритме используется на <tex>[left; rightO(\log n)</tex>меньше памяти, которая раньше тратилась на рекурсивные вызовы.<code style="display: inline-block"> '''function''' mergeSortIterative(a : '''int[n]'''): '''for''' i = 1 '''to''' n, i *= 2 '''for''' j = 0 '''to''' n - i, j += 2 * i merge(a, j, j + i, min(j + 2 * i, n))</code>
MergeSortIterative(A : '''int[1..N]'''; left, right : '''int'''):
'''for''' i = 1 '''to''' N, i *= 2
'''for''' j = left '''to''' right - i, j += 2 * i
Merge(A, j, j + i, min(j + 2 * i, right))
==Время работы==
Чтобы оценить время работы этого алгоритма, составим рекуррентное соотношение. Пускай <tex>T(n)</tex> {{---}} время сортировки массива длины <tex>n</tex>, тогда для сортировки слиянием справедливо <tex>T(n)=2T(n/2)+O(n)</tex> <br>(<tex>O(n)</tex> — это {{---}} время, необходимое на то, чтобы слить два массива)длины <tex>n</tex>. Распишем это соотношение:
<tex>T(n)=2T(n/2)+O(n)=4T(n/4)+2O(n)=\dots=2^kTT(1)+kO\log(n)O(n)=O(n\log(n))</tex>.
Осталось оценить ==Сравнение с другими алгоритмами==Достоинства:* устойчивая,* можно написать эффективную [[Многопоточная сортировка слиянием|многопоточную сортировку слиянием]],* сортировка данных, расположенных на периферийных устройствах и не вмещающихся в оперативную память<texref>k<[http://tex>en.wikipedia. Мы знаем, что <tex>2^k=n<org/wiki/tex>, а значит <tex>k=\log nExternal_sorting Wikipedia {{---}} External sorting]</texref>. Уравнение примет вид Недостатки:* требуется дополнительно <tex>TO(n)=nT(1)+ \log n</tex> памяти, но можно модифицировать до <tex>O(n1)</tex>. Так как <tex>T ==См. также==* [[Сортировка кучей]]* [[Быстрая сортировка]]* [[Timsort]]* [[Cортировка слиянием с использованием O(1)</tex> — константа, то <tex>T(n)дополнительной памяти]] ==Примечания=O(n)+\log n </tex> <tex>O(n)=O(n\log n)<references/tex>.
==Источники информации==
*[http://ru.wikipedia.org/wiki/Mergesort Википедия {{---}} сортировка слиянием]
 
==Ссылки==
*[http://www.sorting-algorithms.com/merge-sort Визуализатор]
*[httphttps://ru.wikibooks.org/wiki/%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D1%80%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8_%D1%81%D0%BB%D0%B8%D1%8F%D0%BD%D0%B8%D0%B5%D0%BC Примеры_реализации_сортировки_слиянием Викиучебник {{---}} Примеры реализации на различных языках программирования]
==См. также==
* [[Сортировка кучей]]
* [[Быстрая сортировка]]
*[[Сортировка слиянием с использованием O(1) дополнительной памяти]]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: СортировкаСортировки]]
[[Категория: Сортировки на сравнениях]]

Навигация