Изменения

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

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

164 байта убрано, 09:59, 15 мая 2012
Нет описания правки
=Сортировка слияниемОписание=
[[Файл:Merge-sort1.gif|right|380px|thumb|Действие алгоритма.]]
'''Сортировка слиянием''' — очень простой алгоритм сортировки, хороший пример использования принципа «разделяй и властвуй». Он был пред­ло­жен Джо­ном фон Ней­ма­ном в 1945 го­ду.
Это ста­биль­ный ал­го­ритм сор­ти­ров­ки, использующий <tex>O(n)</tex> дополнительной памяти и <tex>O(n</tex> <tex>lglog(n))</tex> времени.
=Принцип работы=
Данный алгоритм — хороший пример использования принципа Принцип «разделяй и властвуй». Сначала — сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.
Про­це­ду­ра слия­ния тре­бу­ет два от­сор­ти­ро­ван­ных мас­си­ва. За­ме­тив, что мас­сив из од­но­го эле­мен­та по опре­де­ле­нию яв­ля­ет­ся от­сор­ти­ро­ван­ным, мы мо­жем осу­ще­ствить сор­ти­ров­ку сле­дую­щим об­ра­зом:
1. # Раз­бить имею­щие­ся эле­мен­ты мас­си­ва на па­ры и осу­ще­ствить слия­ние эле­мен­тов каж­дой па­ры, по­лу­чив от­сор­ти­ро­ван­ные це­поч­ки дли­ны 2 (кро­ме, быть мо­жет, од­но­го эле­мен­та, для ко­то­ро­го не на­шлось па­ры).# Раз­бить имею­щие­ся от­сор­ти­ро­ван­ные це­поч­ки на па­ры, и осу­ще­ствить слия­ние це­по­чек каж­дой па­ры.# Ес­ли чис­ло от­сор­ти­ро­ван­ных це­по­чек боль­ше еди­ни­цы, пе­рей­ти к ша­гу 2.
2. Раз­бить имею­щие­ся от­сор­ти­ро­ван­ные це­поч­ки на па­ры, и осу­ще­ствить слия­ние це­по­чек каж­дой па­ры. 3. Ес­ли чис­ло от­сор­ти­ро­ван­ных це­по­чек боль­ше еди­ни­цы, пе­рей­ти к ша­гу 2. ==Слияние 2-х двух массивов==
Допустим, у нас есть два отсортированных массива А и B размерами <tex>N_a </tex> и <tex>N_b </tex> со­ответственно, и мы хотим объединить их элементы в один большой отсортирован­ный массив C размером <tex>N_a + N_b </tex> . Для этого можно применить процедуру слия­ния, суть которой заключается в повторяющемся «отделении» элемента, наи­меньшего из двух имеющихся в началах исходных массивов, и присоединении это­го элемента к концу результирующего массива. Элементы мы переносим до тех пор, пока один из исходных массивов не закончится. После этого оставшийся «хвост» одного из входных массивов дописывается в конец результирующего мас­сива. Пример работы процедуры показан на рисунке:
[[Файл:Mergearr.png|right|300px|thumb|Пример работы процедуры слияния.]]
<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++] : b[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..k] это будет отсортированный массив
</pre>
==Рекурсивный алгоритм==
[[Файл:Merge sort1.png|300px|right|thumb|Пример работы рекурсивного алгоритма сортировки слиянием]]
Проще всего формализовать этот алгоритм рекурсивным способом. Функ­ция Функция сортирует участок массива от элемента с номером a l до элемен­та с номером br:
<pre>// r и l - правая и левая граница массива, m - середина
m = r / 2 // делим на 2 половины if m == r // условие выхода - если массив стал состоять из 1 элемента return sort a[l..m] // рекурсивная сортировка правой и левой частей, в функцию передаются левая и правая границы массива sort a[m+1..r] merge (a[l..m], a[m+1..r]) // делаем процедуру слияния 2х отсортированных половинок
</pre>
Осталось оценить <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-algorithmsalogorithms.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 Примеры реализации на различных языках (Википедия)]
*[http://iproc.ru/parallel-programming/lection-6/ Сортировка слиянием в картинках]
 
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировки]]
Анонимный участник
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/22346»

Навигация