105
правок
Изменения
м
='''Сортировка слиянием=[[Файл:Merge-sort1.gif|right|380px|thumb|Действие алгоритма.]]'''Сортировка слиянием(англ. ''Merge sort'' — Сортировка слиянием — вероятно) {{---}} алгоритм сортировки, один из самых простых алгоритмов сортировки использующий <tex>O(n)</tex> дополнительной памяти и работающий за <tex>O(среди «быстрых» алгоритмовn\log(n)). Особенностью этого алгоритма является то, что он работает с элементами массива преимущественно последовательно, благодаря чему именно этот алгоритм используется при сортировке в системах с различными аппаратными ограничениями</tex> времени.
Кроме того, сортировка слиянием — чуть ли не единственный алгоритм, который может быть эффективно использован для сортировки таких структур данных, как связанные списки==Принцип работы==[[Файл:Merging_two_arrays. Последовательная работа с элементами массива значительно увеличивает скорость сортировки в системах с кэшированиемpng|270px|right|thumb|Пример работы процедуры слияния.]]
Сортировка слиянием — стабильный алгоритм сортировки[[Файл:Merge sort1. Это означает, что порядок «равных» элементов не изменяется в результате работы алгоритма. В некоторых задачах это свойство достаточно важно.Этот алгоритм был предложен Джоном фон Нейманом в 1945 годуpng|300px|right|thumb|Пример работы рекурсивного алгоритма сортировки слиянием]]
=Принцип [[Файл:Merge sort itearative.png|300px|right|thumb|Пример работы=Эта сортировка — хороший пример использования принципа «разделяй и властвуй». Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.итеративного алгоритма сортировки слиянием]]
Процедура слияния требует два отсортированных массива. ЗаметивАлгоритм использует принцип «разделяй и властвуй»: задача разбивается на подзадачи меньшего размера, что массив из одного элемента которые решаются по определению является отсортированнымотдельности, мы можем осуществить сортировку следующим образомпосле чего их решения комбинируются для получения решения исходной задачи. Конкретно процедуру сортировки слиянием можно описать следующим образом:
1# Если в рассматриваемом массиве один элемент, то он уже отсортирован {{---}} алгоритм завершает работу. Разбить имеющиеся элементы массива # Иначе массив разбивается на пары и осуществить слияние элементов каждой парыдве части, получив отсортированные цепочки длины 2 (кроме, быть может, одного элементакоторые сортируются рекурсивно.# После сортировки двух частей массива к ним применяется процедура слияния, для которого не нашлось пары)которая по двум отсортированным частям получает исходный отсортированный массив.
2===Слияние двух массивов===У нас есть два массива <tex>a</tex> и <tex>b</tex> (фактически это будут две части одного массива, но для удобства будем писать, что у нас просто два массива). Нам надо получить массив <tex>c</tex> размером <tex>|a| + |b|</tex>. Для этого можно применить процедуру слияния. Эта процедура заключается в том, что мы сравниваем элементы массивов (начиная с начала) и меньший из них записываем в финальный. Разбить имеющиеся отсортированные цепочки на парыИ затем, в массиве у которого оказался меньший элемент, переходим к следующему элементу и сравниваем теперь его. В конце, если один из массивов закончился, мы просто дописываем в финальный другой массив. После мы наш финальный массив записываем заместо двух исходных и осуществить слияние цепочек каждой парыполучаем отсортированный участок.
3. Если число отсортированных цепочек больше единицыМножество отсортированных списков с операцией <tex>\mathrm{merge}</tex> является [[Моноид|моноидом]], перейти к шагу 2где нейтральным элементом будет пустой список.
=Слияние 2-х массивов=ДопустимНиже приведён псевдокод процедуры слияния, у нас есть два отсортированных который сливает две части массива А и B размерами <tex>N_a a</tex> и {{---}} <tex>N_b [left; mid)</tex> соответственно, и мы хотим объединить их элементы в один большой отсортированный массив C размером <tex>N_a + N_b [mid; right)</tex> . Для этого можно применить процедуру слияния<code style="display: inline-block"> '''function''' merge(a : '''int[n]'''; left, суть которой заключается в повторяющемся «отделении» элементаmid, наименьшего из двух имеющихся в началах исходных массивов, и присоединении этого элемента к концу результирующего массива. Элементы мы переносим до тех пор, пока один из исходных массивов не закончится. После этого оставшийся «хвост» одного из входных массивов дописывается в конец результирующего массива. Пример работы процедуры показан на рисункеright : '''int'''): it1 = 0 it2 = 0 result :'''int[right - left]''' '''while''' left + it1 < mid '''and''' mid + it2 < right '''if''' a[left + it1] < a[mid + it2] result[it1 + it2] = a[left + it1] it1 += 1 '''else''' result[it1 + it2] = a[Файл:Mergearr.png|center|500px|thumb|Пример работы процедуры слияния.mid + it2] it2 += 1 '''while''' left + it1 < mid result[it1 + it2] = a[left + it1] it1 += 1 '''while''' mid + it2 < right result[it1 + it2] = a[mid + it2] it2 += 1 '''for''' i = 0 '''to''' it1 + it2 a[left + i]= result[i]<br/code>Алгоритм слияния формально можно записать следующим образом:
// условие выхода - если массив стал состоять из ==См. также==* [[Сортировка кучей]]* [[Быстрая сортировка]]* [[Timsort]]* [[Cортировка слиянием с использованием O(1 элемента) дополнительной памяти]]
<tex>if</tex> <tex>m</tex> <tex>==Примечания==<references/tex> <tex>r</tex>
<tex>return<==Источники информации==*[http:/tex>/ru.wikipedia.org/wiki/Mergesort Википедия {{---}} сортировка слиянием]*[http://www.sorting-algorithms.com/merge-sort Визуализатор]*[https://ru.wikibooks.org/wiki/Примеры_реализации_сортировки_слиянием Викиучебник {{---}} Примеры реализации на различных языках программирования]
// рекурсивная сортировка правой и левой частей, в функцию передаются левая и правая границы массива
<tex>sort</tex> <tex>a[l..m]</tex>
<tex>sort</tex> <tex>a[m+1..r]</tex>
// делаем процедуру слияния 2х отсортированных половонок
<tex>merge</tex> <tex>a[l..m]</tex> <tex>and</tex> <tex>a[m+1..r]</tex>
Пример работы алгоритма показан на рисунке:
[[Файл:Merge sort1.png|500px|center|thumb|Пример работы рекурсивного алгоритма сортировки слиянием]]
=Время работы=
Чтобы оценить время работы этого алгоритма, составим рекуррентное соотношение. Пускай <tex>T(n)</tex> - время сортировки массива длины n, тогда для сортировки слиянием справедливо <tex>T(n)=2T(n/2)+O(n)</tex> <br>
(<tex>O(n)</tex> - это время, необходимое на то, чтобы слить два массива). Распишем это соотношение:
<tex>T(n)</tex> <tex>=</tex> <tex>2T(n/2)</tex> <tex>+</tex> <tex>O(n)</tex> <tex>=</tex> <tex>4T(n/4)</tex> <tex>+</tex> <tex>2*O(n)</tex> <tex>=</tex> <tex>...</tex> <tex>=</tex> <tex>2^kT(1)</tex> <tex>+</tex> <tex>kO(n).</tex>
Осталось оценить <tex>k</tex>. Мы знаем, что <tex>2^k=n</tex>, а значит <tex>k=\log(n)</tex>. Уравнение примет вид <tex>T(n)=nT(1)+ \log(n)O(n)</tex>. Так как <tex>T(1)</tex> - константа, то <tex>T(n)=O(n)+\log(n)O(n)=O(n\log(n))</tex>.
=Свойства=
Стабильный.
<tex>O(n)</tex> дополнительной памяти для массива.
<tex>O(lg(n))</tex> дополнительной памяти для связных списков.
<tex>O(n</tex> <tex>lg(n))</tex> времени.
=Ссылки=
*[http://ru.wikipedia.org/wiki/Mergesort| Википедия - сортировка слиянием]
*[http://iproc.ru/parallel-programming/lection-6/| Сортировка слиянием]
*[http://www.sorting-algorithms.com/merge-sort| Сортировка слиянием, анимация и свойства (англ.)]
*[http://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| Примеры реализации на различных языках (Википедия)]
Нет описания правки
===Рекурсивный алгоритм===Функция сортирует подотрезок массива с индексами в полуинтервале <tex>[left; right)</tex>.<code style="display: inline-block"> '''function''' mergeSortRecursive(a : '''int[Файлn]'''; left, right : '''int'''):merge41.png]] '''if''' left + 1 >= right '''return''' mid = (left + right) / 2 mergeSortRecursive(a, left, mid) mergeSortRecursive(a, mid, right) merge(a, left, mid, right)</code>
=Рекурсивный ==Итеративный алгоритм===Проще всего формализовать этот алгоритм рекурсивным способомПри итеративном алгоритме используется на <tex>O(\log n)</tex> меньше памяти, которая раньше тратилась на рекурсивные вызовы. Функция <code style="display: inline-block"> сортирует участок массива от элемента с номером '''function''' mergeSortIterative(a до элемента с номером b:'''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>
==Время работы==Чтобы оценить время работы этого алгоритма, составим рекуррентное соотношение. Пускай <tex>T(n)<// r и l tex> {{--- правая и левая граница }} время сортировки массивадлины <tex>n</tex>, m тогда для сортировки слиянием справедливо <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/ делим на 2 половины4)+2O(n)=\dots=T(1)+\log(n)O(n)=O(n\log(n))</tex>.
==Сравнение с другими алгоритмами==Достоинства:* устойчивая,* можно написать эффективную [[Многопоточная сортировка слиянием|многопоточную сортировку слиянием]],* сортировка данных, расположенных на периферийных устройствах и не вмещающихся в оперативную память<texref>m<[http://en.wikipedia.org/tex> <tex>=<wiki/tex> <tex>rExternal_sorting Wikipedia {{---}} External sorting]</texref> .Недостатки:* требуется дополнительно <tex>/O(n)</tex> памяти, но можно модифицировать до <tex>2O(1)</tex>.
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировки]]
[[Категория: Сортировки на сравнениях]]
