Изменения
Нет описания правки
=Сортировка слиянием=
[[Файл:Merge-sort1.gif|right|380px|thumb|Действие алгоритма.]]
'''Сортировка слиянием''' — Сортировка слиянием — вероятно, один из самых простых алгоритмов сортировки (среди «быстрых» алгоритмов)очень простой алгоритм сортировки. Особенностью этого алгоритма является то, что он работает с элементами массива преимущественно последовательно, благодаря чему именно этот алгоритм используется при сортировке Он был предложен Джоном фон Нейманом в системах с различными аппаратными ограничениями1945 году.
=Принцип работы=
Процедура слияния требует два отсортированных массива. Заметив, что массив из одного элемента по определению является отсортированным, мы можем осуществить сортировку следующим образом:
=Слияние 2-х массивов=
Допустим, у нас есть два отсортированных массива А и B размерами <tex>N_a </tex> и <tex>N_b </tex> соответственно, и мы хотим объединить их элементы в один большой отсортированный массив C размером <tex>N_a + N_b </tex> . Для этого можно применить процедуру слияния, суть которой заключается в повторяющемся «отделении» элемента, наименьшего из двух имеющихся в началах исходных массивов, и присоединении этого элемента к концу результирующего массива. Элементы мы переносим до тех пор, пока один из исходных массивов не закончится. После этого оставшийся «хвост» одного из входных массивов дописывается в конец результирующего массива. Пример работы процедуры показан на рисунке:
[[Файл:Mergearr.png|right|500px300px|thumb|Пример работы процедуры слияния.]]
<br>
Алгоритм слияния формально можно записать следующим образом:
<pre>// слияние двух массивов с помощью временногоmerge (array a, array b) // a - левая половина (от l до m), b - правая половина (от m + 1 до r) i = l, j = m + 1, k = 0; array temp; while i <= m and j <= r temp[k++] = (a[j] < b[i]) ? a[Файлj++] :merge41b[i++]; while i <= m temp[k++] = b[i++]; while j <= r temp[k++] = a[j++]; for (int t = 0; t != k; t++) a[t] = temp[t]// в конце a[1.png].k]это будет отсортированный массив</pre>
=Рекурсивный алгоритм=
[[Файл:Merge sort1.png|500px300px|right|thumb|Пример работы рекурсивного алгоритма сортировки слиянием]]
Проще всего формализовать этот алгоритм рекурсивным способом. Функция сортирует участок массива от элемента с номером a до элемента с номером b:
<pre>// r и l - правая и левая граница массива, m - середина m = r / 2 // делим на 2 половины <tex> if m</tex> <tex>=</tex> = <tex>r</tex> <tex>/</tex> <tex>2</tex> // условие выхода - если массив стал состоять из 1 элемента return<tex>if</tex> sort <tex>a[l..m</tex> <tex>==</tex> <tex>r</tex> <tex>return</tex> ] // рекурсивная сортировка правой и левой частей, в функцию передаются левая и правая границы массива <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]) // делаем процедуру слияния 2х отсортированных половинок</texpre>
Пример работы алгоритма показан на рисунке:
=Ссылки=
*[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| Примеры реализации на различных языках (Википедия)]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировки]]
