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

2012-05-17T10:10:22Z

109.205.250.119:

==Описание==
[[Файл:Merge-sort1.gif|right|380px|thumb|Действие алгоритма.]]
'''Сортировка слиянием''' — алгоритм сортировки, хороший пример использования принципа «разделяй и властвуй». Он был предложен Джоном фон Нейманом в 1945 году.

Это стабильный алгоритм сортировки, использующий <tex>O(n)</tex> дополнительной памяти и <tex>O(n</tex> <tex>\log(n))</tex> времени.

==Принцип работы==
Принцип «разделяй и властвуй» — сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.

Процедура слияния требует два отсортированных массива. Заметив, что массив из одного элемента по определению является отсортированным, мы можем осуществить сортировку следующим образом:

# Разбить имеющиеся элементы массива на пары и осуществить слияние элементов каждой пары, получив отсортированные цепочки длины 2 (кроме, быть может, одного элемента, для которого не нашлось пары).
# Разбить имеющиеся отсортированные цепочки на пары, и осуществить слияние цепочек каждой пары.
# Если число отсортированных цепочек больше единицы, перейти к шагу 2.

===Слияние двух массивов===
Допустим, у нас есть два отсортированных массива А и B размерами <tex>N_a </tex> и <tex>N_b </tex> соответственно, и мы хотим объединить их элементы в один большой отсортированный массив C размером <tex>N_a + N_b </tex> . Для этого можно применить процедуру слияния, суть которой заключается в повторяющемся «отделении» элемента, наименьшего из двух имеющихся в началах исходных массивов, и присоединении этого элемента к концу результирующего массива. Элементы мы переносим до тех пор, пока один из исходных массивов не закончится. После этого оставшийся «хвост» одного из входных массивов дописывается в конец результирующего массива. Пример работы процедуры показан на рисунке:
[[Файл:Mergearr.png|right|300px|thumb|Пример работы процедуры слияния.]]
<br>
Алгоритм слияния формально можно записать следующим образом:

<pre>// слияние двух массивов с помощью временного
merge(array a, int left, int middle, int right) // left - левая граница, right - правая, middle - середина
array b = a[middle + 1, right];
i = left, j = middle + 1, k = 0;
array temp;
while i <= middle and j <= right
temp[k++] = (a[j] < b[i]) ? a[j++] : b[i++];
while i <= middle
temp[k++] = b[i++];
while j <= right
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|Пример работы рекурсивного алгоритма сортировки слиянием]]
Проще всего формализовать этот алгоритм рекурсивным способом. Функция сортирует участок массива от элемента с номером left до элемента с номером right:

<pre>
sort(array a, int left, int right) // right и left — правая и левая граница массива, middle — середина
middle = right / 2
if middle == right // условие выхода — если массив стал состоять из 1 элемента
return
sort(a, left, middle)
sort (a, middle + 1, right)
merge(array a, left, middle, right)
</pre>

Пример работы алгоритма показан на рисунке:

==Время работы==
Чтобы оценить время работы этого алгоритма, составим рекуррентное соотношение. Пускай <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>.

==Ссылки==
*[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 Примеры реализации на различных языках (Википедия)]
*[http://iproc.ru/parallel-programming/lection-6/ Сортировка слиянием в картинках (источник картинок в статье)]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировки]]

Конкурс для более удачного URL сайта вики-конспектов

2012-02-15T14:57:50Z

109.205.250.119: /* Варианты */

Хочется избавиться от имени mediawiki, потому что это название вики-движка .

Предлагайте варианты URL для вики-конспектов на этой странице.
Подписывайтесь, бонусы возможны.

== Варианты ==

{| class="wikitable"
!Вариант!!Автор (<nowiki>~~~</nowiki>)
|-
|knowledge||[[Участник:Kirelagin|Кирилл Елагин]]
|-
|wikiconsp||[[Участник:Igor buzhinsky|Игорь Бужинский]]
|-
|wk ''(что бы это ни значило)''||[[Участник:Kirelagin|Кирилл Елагин]]
|-
|lectures||[[Участник:Igor buzhinsky|Игорь Бужинский]]
|-
|theory||[[Участник:Shevchen|Дмитрий Шевченко]]
|-
|outlines||[[Участник:Shevchen|Дмитрий Шевченко]]
|-
|wikikt||[[Участник:Mamoshkin.Arseny|Арсений Мамошкин]]
|-
|lecturenotes||[[Участник:Dgerasimov|Дмитрий Герасимов]]
|-
|ktlectures||[[Участник:SkudarnovYaroslav|Ярослав Скударнов]]
|-
|wiki||[[Участник:Андрей Шулаев|Андрей Шулаев]]
|-
|pediwikia||[[Участник:Pashkal|Павел Кротков]]
|-
|wikisynopses||[[Участник:Rybak|Андрей Рыбак]]
|-
|ctpedia||[[Участник:Borisov|Сергей Борисов]]
|-
|ctd||[[Участник:Borisov|Сергей Борисов]]
|-
|wikimath||[[Участник:Yurik|Александров Юрий]]
|-
|itmopedia||Марат Валиахметов
|-
|w||[[Участник:Tsar|Иоанн Волков]]
|-
|notes||[[Участник:Grechko|Гречко Владислав]]
|-
|medialibrary||[[Участник:Андреев Кирилл|Андреев Кирилл]]
|-
|algowiki||[[Участник:ЗабылПароль|Иванов Денис]]
|-
|wiki.ifmo.ru||[[Участник:Proshev|Прошев Семен]]
|-
|db.algowiki.ru||[[Участник:GeraltFromRivia|Завадский Дмитрий]]
|-
|wikicat ||[[Участник:Русин Никита|Русин Никита]]
|-
|algostore ||[[Участник:Русин Никита|Русин Никита]]
|-
|store ||[[Участник:Русин Никита|Русин Никита]]
|-
|ourwiki || [[Участник:kir1251|Голубев Кирилл]]
|-
|KTwiki || [[Участник:igorjan94|Колобов Игорь]]
|}
+1 за педивикию :D
: +1
:: +1 [3]
+1 за версию "вики". Легче всего будет запомнить, wiki.ifmo

Викиконспекты - Вклад участника [ru]

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

Конкурс для более удачного URL сайта вики-конспектов