105
правок
Изменения
м
=Сортировка слиянием=[[Файл:Merge sort animation2.gif|right|380px|thumb|Действие алгоритма на примере сортировки случайных точек.]]'''Сортировка слиянием''' — вероятно, один из самых простых алгоритмов сортировки (среди «быстрых» алгоритмовангл. ''Merge sort'').Сортировка слиянием — стабильный {{---}} алгоритм сортировки. Это означает, что порядок «равных» элементов не изменяется в результате работы алгоритма. В некоторых задачах это свойство достаточно важно. Этот алгоритм был предложен Джоном фон Нейманом в 1945 годуиспользующий <tex>O(n)</tex> дополнительной памяти и работающий за <tex>O(n\log(n))</tex> времени.
Для решения задачи сортировки эти три этапа выглядят так[[Файл:*Сортируемый массив разбивается на две части примерно одинакового размера;*Каждая из получившихся частей сортируется отдельно, обычно - рекурсивно, тем же самым алгоритмом;*Два упорядоченных массива половинного размера соединяются в одинMerge sort1.png|300px|right|thumb|Пример работы рекурсивного алгоритма сортировки слиянием]]
Рекурсивное разбиение задачи на меньшие происходит до тех пор, пока размер массива не достигнет единицы <br>(любой массив длины 1 можно считать упорядоченным)[[Файл:Merge sort itearative.png|300px|right|thumb|Пример работы итеративного алгоритма сортировки слиянием]]
=Слияние 2-х массивов=ДопустимАлгоритм использует принцип «разделяй и властвуй»: задача разбивается на подзадачи меньшего размера, у нас есть два отсортированных массива А и B размерами <tex>N_a </tex> и <tex>N_b </tex> соответственнокоторые решаются по отдельности, и мы хотим объединить после чего их элементы в один большой отсортированный массив C размером <tex>N_a + N_b </tex> решения комбинируются для получения решения исходной задачи. Для этого можно применить Конкретно процедуру слияния, суть которой заключается в повторяющемся «отделении» элемента, наименьшего из двух имеющихся в началах исходных массивов, и присоединении этого элемента к концу результирующего массива. Элементы мы переносим до тех пор, пока один из исходных массивов не закончится. После этого оставшийся «хвост» одного из входных массивов дописывается в конец результирующего массива. Пример работы процедуры показан на рисунке:[[Файл:Mergearr.png|center|500px|thumb|Пример работы процедуры слияния.]]<br>Алгоритм слияния формально сортировки слиянием можно записать описать следующим образом:
a = 0; b = 0;# Если в рассматриваемом массиве один элемент, то он уже отсортирован {{---}} алгоритм завершает работу. While (a < <tex>n_a</tex>) and (b < <tex>n_b</tex>) # Иначе массив разбивается на две части, которые сортируются рекурсивно. If A[a] <tex>\leqslant</tex> B[b] C[a + b] = A[a]; a = a + 1; Else C[a + b] = B[b]; b = b + 1; End; End; If a < <tex>n_a</tex> Copy remain part of A Else Copy remain part of B End;# После сортировки двух частей массива к ним применяется процедура слияния, которая по двум отсортированным частям получает исходный отсортированный массив.
=Рекурсивный алгоритм=Проще всего формализовать этот алгоритм рекурсивным способом. Функция сортирует участок массива от элемента с номером a до элемента Множество отсортированных списков с номером b: Function MergeSort(a,b) If b = a then Exit; c = (a + b)операцией <tex>\mathrm{merge}</2; Mergesort(atex> является [[Моноид|моноидом]],c); MergeSort(c + 1,b); Merge fragments (a,c) and (c + 1,b); Endгде нейтральным элементом будет пустой список.
Пример работы алгоритма показан на рисункеНиже приведён псевдокод процедуры слияния, который сливает две части массива <tex>a</tex> {{---}} <tex>[left; mid)</tex> и <tex>[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[Файл:Merge sort1.png|500px|center|thumb|Пример работы рекурсивного алгоритма сортировки слияниемleft + it1] it1 += 1 '''else''' result[it1 + it2] = a[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]</code>
T===Итеративный алгоритм===При итеративном алгоритме используется на <tex>O(\log n) </tex> меньше памяти, которая раньше тратилась на рекурсивные вызовы.<code style= 2T"display: inline-block"> '''function''' mergeSortIterative(a : '''int[n/2]''') + O(: '''for''' i = 1 '''to''' n) , i *= 2 '''for''' j = 4T(0 '''to''' n/4) - i, j + = 2*Oi merge(n) = ... = 2kTa, j, j + i, min(1) j + kO(2 * i, n). )</code>
Осталось ==Время работы==Чтобы оценить <tex>k</tex>время работы этого алгоритма, составим рекуррентное соотношение. Мы знаем, что Пускай <tex>2k=T(n)</tex>, а значит {{---}} время сортировки массива длины <tex>k=log(n)</tex>. Уравнение примет вид , тогда для сортировки слиянием справедливо <tex>T(n)=nT2T(1n/2)+ log(n)O(n)</tex>. Так как <br><tex>TO(1n)</tex> {{- константа--}} время, необходимое на то , чтобы слить два массива длины <tex>n</tex>. Распишем это соотношение: <tex>T(n)=2T(n/2)+O(n)=4T(n/4)+2O(n)=\dots=T(1)+\log(n)O(n)=O(nlogn\log(n))</tex>. ==Сравнение с другими алгоритмами==Достоинства:* устойчивая,* можно написать эффективную [[Многопоточная сортировка слиянием|многопоточную сортировку слиянием]],* сортировка данных, расположенных на периферийных устройствах и не вмещающихся в оперативную память<ref>[http://en.wikipedia.org/wiki/External_sorting Wikipedia {{---}} External sorting]</ref>.Недостатки:* требуется дополнительно <tex>O(n)</tex> памяти, но можно модифицировать до <tex>O(1)</tex>. ==См. также==* [[Сортировка кучей]]* [[Быстрая сортировка]]* [[Timsort]]* [[Cортировка слиянием с использованием O(1) дополнительной памяти]] ==Примечания==<references/> ==Источники информации==*[http://ru.wikipedia.org/wiki/Mergesort Википедия {{---}} сортировка слиянием]*[http://www.sorting-algorithms.com/merge-sort Визуализатор]*[https://ru.wikibooks.org/wiki/Примеры_реализации_сортировки_слиянием Викиучебник {{---}} Примеры реализации на различных языках программирования] [[Категория: Дискретная математика и алгоритмы]][[Категория: Сортировки]][[Категория: Сортировки на сравнениях]]
Нет описания правки
==Принцип работы==Эта сортировка — хороший пример использования принципа «разделяй и властвуй»[[Файл:Merging_two_arrays. Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачиpng|270px|right|thumb|Пример работы процедуры слияния.]]
===Слияние двух массивов===
У нас есть два массива <tex>a</tex> и <tex>b</tex> (фактически это будут две части одного массива, но для удобства будем писать, что у нас просто два массива). Нам надо получить массив <tex>c</tex> размером <tex>|a| + |b|</tex>. Для этого можно применить процедуру слияния. Эта процедура заключается в том, что мы сравниваем элементы массивов (начиная с начала) и меньший из них записываем в финальный. И затем, в массиве у которого оказался меньший элемент, переходим к следующему элементу и сравниваем теперь его. В конце, если один из массивов закончился, мы просто дописываем в финальный другой массив. После мы наш финальный массив записываем заместо двух исходных и получаем отсортированный участок.
=Время работы==Рекурсивный алгоритм===Чтобы оценить время работы этого алгоритма, составим рекуррентное соотношение. Пускай Функция сортирует подотрезок массива с индексами в полуинтервале <tex>T(n[left; right)</tex> .<code style="display: inline- время сортировки массива длины n, тогда для сортировки слиянием справедливо <texblock">T '''function''' mergeSortRecursive(a : '''int[n]'''; left, right : '''int'''): '''if''' left + 1 >= right '''return''' mid =2T(nleft + right) /2 mergeSortRecursive(a, left, mid)+O mergeSortRecursive(na, mid, right)</tex> merge(<tex>O(na, left, mid, right)</texcode> - это время, необходимое на то, чтобы слить два массива). Распишем это соотношение:
