Изменения

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

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

1637 байт добавлено, 14:13, 13 мая 2012
Нет описания правки
=Сортировка слиянием=
[[Файл:Merge sort animation2-sort1.gif|right|380px|thumb|Действие алгоритма на примере сортировки случайных точек.]]
'''Сортировка слиянием''' — Сор­ти­ров­ка слия­ни­ем — ве­ро­ят­но, один из са­мых про­стых ал­го­рит­мов сор­ти­ров­ки (сре­ди «быст­рых» ал­го­рит­мов). Осо­бен­но­стью это­го ал­го­рит­ма яв­ля­ет­ся то, что он ра­бо­та­ет с эле­мен­та­ми мас­си­ва пре­иму­ще­ствен­но по­сле­до­ва­тель­но, бла­го­да­ря че­му имен­но этот ал­го­ритм ис­поль­зу­ет­ся при сор­ти­ров­ке в си­сте­мах с раз­лич­ны­ми ап­па­рат­ны­ми огра­ни­че­ни­я­ми.
Эта сортировка — хороший пример использования принципа «разделяй и властвуй». Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.
Для решения задачи сортировки эти три этапа выглядят так:*Сортируемый массив разбивается на две части примерно одинакового размера;*Каждая Про­це­ду­ра слия­ния тре­бу­ет два от­сор­ти­ро­ван­ных мас­си­ва. За­ме­тив, что мас­сив из получившихся частей сортируется отдельноод­но­го эле­мен­та по опре­де­ле­нию яв­ля­ет­ся от­сор­ти­ро­ван­ным, обычно - рекурсивно, тем же самым алгоритмом;*Два упорядоченных массива половинного размера соединяются в один.мы мо­жем осу­ще­ствить сор­ти­ров­ку сле­дую­щим об­ра­зом:
Рекурсивное разбиение задачи 1. Раз­бить имею­щие­ся эле­мен­ты мас­си­ва на меньшие происходит до тех порпа­ры и осу­ще­ствить слия­ние эле­мен­тов каж­дой па­ры, по­лу­чив от­сор­ти­ро­ван­ные це­поч­ки дли­ны 2 (кро­ме, быть мо­жет, од­но­го эле­мен­та, пока размер массива для ко­то­ро­го не достигнет единицы <br>(любой массив длины 1 можно считать упорядоченнымна­шлось па­ры). 2. Раз­бить имею­щие­ся от­сор­ти­ро­ван­ные це­поч­ки на па­ры, и осу­ще­ствить слия­ние це­по­чек каж­дой па­ры. 3. Ес­ли чис­ло от­сор­ти­ро­ван­ных це­по­чек боль­ше еди­ни­цы, пе­рей­ти к ша­гу 2.
=Слияние 2-х массивов=
Алгоритм слияния формально можно записать следующим образом:
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Файл:merge41.png] = 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// r и l - правая и левая граница массива,b)m - середина  If b // делим на 2 половины <tex>m</tex> <tex>= a then Exit;</tex> <tex>r</tex> <tex>/</tex> <tex>2</tex> // условие выхода - если массив стал состоять из 1 элемента  c <tex>if</tex> <tex>m</tex> <tex>= (=</tex> <tex>r</tex> <tex>return</tex> // рекурсивная сортировка правой и левой частей, в функцию передаются левая и правая границы массива <tex>sort</tex> <tex>a + b)[l..m]</2;tex>  Mergesort(<tex>sort</tex> <tex>a,c); MergeSort(c [m+ 1,b);..r]</tex> // делаем процедуру слияния 2х отсортированных половонок  Merge fragments (<tex>merge</tex> <tex>a,c) [l..m]</tex> <tex>and (c </tex> <tex>a[m+ 1,b); End..r]</tex>
Пример работы алгоритма показан на рисунке:
(<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| Примеры реализации на различных языках (Википедия)]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировки]]
Tiss93
139
правок
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/22251»

Навигация