Изменения

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

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

1531 байт убрано, 11:38, 7 июня 2012
Нет описания правки
==Описание==
[[Файл:Merge-sort1.gif|right|380px|thumb|Действие алгоритма.]]
'''Сортировка слиянием''' — алгоритм сортировки. Он был пред­ло­жен Джо­ном фон Ней­ма­ном в 1945 го­ду.
Это устойчивый ал­го­ритм, использующий <tex>O(n)</tex> дополнительной памяти и <tex>O(n</tex> <tex>\log(n))</tex> времени.
*[http://www.sorting-algorithms.com/merge-sort Анимированная работа алгоритма (англ.)]
==Принцип работы==
[[Файл:Merge-sort-example.jpg|right|300px|thumb|Пример работы процедуры слияния.]]
Этот алгоритм использует принцип «разделяй и властвуй». Этот принцип заключается в том, что исходная задача разбивается на подзадачи меньшего размера, а потом они решаются рекурсивным методом или же конкретно, если их размер мал. Потом из решения объединяются и получается решение основной (исходной) задачи.
===Слияние двух массивов===
[[Файл:Mergearr.png|right|300px|thumb|Пример работы процедуры слияния.]]
У нас есть два массива <tex>A</tex> и <tex>B</tex>. Нам надо получить массив <tex>C</tex> размером <tex>sizeof(A) + sizeof(B)</tex>. Для этого можно применить процедуру слияния. Эта процедура заключается в том, что мы сравниваем элементы массивов (начиная с начала) и меньший из них записываем в финальный. И затем, в массиве у которого оказался меньший элемент, переходим к следующему элементу и сравниваем теперь его. В конце, если один из массивов закончился, мы просто дописываем в финальный другой массив. После мы наш финальный массив записываем заместо двух исходных и получаем отсортированный участок.
// left - левая граница, right - правая, middle - середина
merge(array a, int left, int middle, int right)
array b = a[middle, right];
i = left, j = middle, k = 0;
array temp = new array[sizeof(a) + sizeof(b)];
while i <= middle and j < right
temp[k++] = (a[j] < ba[i]) ? a[j++] : ba[i++];
while i <= middle
temp[k++] = ba[i++];
while j < right
temp[k++] = a[j++];
// в конце a[1..k] это будет отсортированный массив
</pre>
 
==Рекурсивный алгоритм==
[[Файл:Merge sort1.png|300px|right|thumb|Пример работы рекурсивного алгоритма сортировки слиянием]]
Функция сортирует участок массива от элемента с номером left до элемен­та с номером right:. Будем реализовывать так, что бы производилась сортировка полуинтервала [left, right)
right и left — правая и левая граница массива, middle — середина.
Пример работы алгоритма показан на рисунке:
 
==Восходящая сортировка слиянием==
[[Файл:mergenonrec.png|300px|right|thumb|Пример работы восходящей сортировки слиянием]]
Помимо рекурсивного алгоритма существует и альтернативный.
Пример работы алгоритма показан на рисунке:
 
# Выделим память размером с занимаемой памяти исходного массива.
# Попарно сравним элементы, записывая во временную память.
# Поменяем указатели временного и исходного массива.
# Выполним слияние "кусочков" размером два.
# Повторяем до тех пор, пока не сделаем единый кусок.
 
Процедуру слияния надо будет изменить, так, что-бы она записывала результат в результирующий массив (mas1)
<pre>sort(array mas, int elementsAmount)
array mas1 = new array[elementsAmount];
for(int size = 1; size < elementsAmount; size *= 2)
int start = 0;
while ((start + size) < elementsAmount)
merge(mas /*наш массив*/, mas + start /*левая граница*/,
mas + start + size /*середина*/,
mas + start + size + min(size, elementsAmount - start - size)) /*правая граница*/;
start += size * 2;
while (start < elementsAmount)
mas1[start] = mas[start];
++start;
array temp = mas1;
mas1 = mas;
mas = temp;
</pre>
==Время работы==
(<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*O2O(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>.
139
правок

Навигация