Сортировка слиянием — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Рекурсивный алгоритм)
м (rollbackEdits.php mass rollback)
 
(не показана 71 промежуточная версия 13 участников)
Строка 1: Строка 1:
=Сортировка слиянием=
+
'''Сортировка слиянием''' (англ. ''Merge sort'') {{---}} алгоритм сортировки, использующий <tex>O(n)</tex> дополнительной памяти и работающий за <tex>O(n\log(n))</tex> времени.
[[Файл:Merge-sort1.gif|right|380px|thumb|Действие алгоритма.]]
 
'''Сортировка слиянием''' — Сор­ти­ров­ка слия­ни­ем — ве­ро­ят­но, один из са­мых про­стых ал­го­рит­мов сор­ти­ров­ки (сре­ди «быст­рых» ал­го­рит­мов). Осо­бен­но­стью это­го ал­го­рит­ма яв­ля­ет­ся то, что он ра­бо­та­ет с эле­мен­та­ми мас­си­ва пре­иму­ще­ствен­но по­сле­до­ва­тель­но, бла­го­да­ря че­му имен­но этот ал­го­ритм ис­поль­зу­ет­ся при сор­ти­ров­ке в си­сте­мах с раз­лич­ны­ми ап­па­рат­ны­ми огра­ни­че­ни­я­ми.
 
  
Кро­ме то­го, сор­ти­ров­ка слия­ни­ем — чуть ли не един­ствен­ный ал­го­ритм, ко­то­рый мо­жет быть эф­фек­тив­но ис­поль­зо­ван для сор­ти­ров­ки та­ких ст­рук­тур дан­ных, как свя­зан­ные спис­ки. По­сле­до­ва­тель­ная ра­бо­та с эле­мен­та­ми мас­си­ва зна­чи­тель­но уве­ли­чи­ва­ет ско­рость сор­ти­ров­ки в си­сте­мах с кэ­ши­ро­ва­ни­ем.
+
==Принцип работы==
 +
[[Файл:Merging_two_arrays.png|270px|right|thumb|Пример работы процедуры слияния.]]
  
Сор­ти­ров­ка слия­ни­ем — ста­биль­ный ал­го­ритм сор­ти­ров­ки. Это озна­ча­ет, что по­ря­док «рав­ных» эле­мен­тов не из­ме­ня­ет­ся в ре­зуль­та­те ра­бо­ты ал­го­рит­ма. В не­ко­то­рых за­да­чах это свой­ство до­ста­точ­но важ­но.
+
[[Файл:Merge sort1.png|300px|right|thumb|Пример работы рекурсивного алгоритма сортировки слиянием]]
Этот ал­го­ритм был пред­ло­жен Джо­ном фон Ней­ма­ном в 1945 го­ду
 
  
=Принцип работы=
+
[[Файл:Merge sort itearative.png|300px|right|thumb|Пример работы итеративного алгоритма сортировки слиянием]]
Эта сортировка — хороший пример использования принципа «разделяй и властвуй». Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.
 
  
Про­це­ду­ра слия­ния тре­бу­ет два от­сор­ти­ро­ван­ных мас­си­ва. За­ме­тив, что мас­сив из од­но­го эле­мен­та по опре­де­ле­нию яв­ля­ет­ся от­сор­ти­ро­ван­ным, мы мо­жем осу­ще­ствить сор­ти­ров­ку сле­дую­щим об­ра­зом:
+
Алгоритм использует принцип «разделяй и властвуй»: задача разбивается на подзадачи меньшего размера, которые решаются по отдельности, после чего их решения комбинируются для получения решения исходной задачи. Конкретно процедуру сортировки слиянием можно описать следующим образом:
  
1. Раз­бить имею­щие­ся эле­мен­ты мас­си­ва на па­ры и осу­ще­ствить слия­ние эле­мен­тов каж­дой па­ры, по­лу­чив от­сор­ти­ро­ван­ные це­поч­ки дли­ны 2 (кро­ме, быть мо­жет, од­но­го эле­мен­та, для ко­то­ро­го не на­шлось па­ры).
+
# Если в рассматриваемом массиве один элемент, то он уже отсортирован {{---}} алгоритм завершает работу.
 +
# Иначе массив разбивается на две части, которые сортируются рекурсивно.
 +
# После сортировки двух частей массива к ним применяется процедура слияния, которая по двум отсортированным частям получает исходный отсортированный массив.
  
2. Раз­бить имею­щие­ся от­сор­ти­ро­ван­ные це­поч­ки на па­ры, и осу­ще­ствить слия­ние це­по­чек каж­дой па­ры.
+
===Слияние двух массивов===
 +
У нас есть два массива <tex>a</tex> и <tex>b</tex> (фактически это будут две части одного массива, но для удобства будем писать, что у нас просто два массива). Нам надо получить массив <tex>c</tex> размером <tex>|a| + |b|</tex>. Для этого можно применить процедуру слияния. Эта процедура заключается в том, что мы сравниваем элементы массивов (начиная с начала) и меньший из них записываем в финальный. И затем, в массиве у которого оказался меньший элемент, переходим к следующему элементу и сравниваем теперь его. В конце, если один из массивов закончился, мы просто дописываем в финальный другой массив. После мы наш финальный массив записываем заместо двух исходных и получаем отсортированный участок.
  
3. Ес­ли чис­ло от­сор­ти­ро­ван­ных це­по­чек боль­ше еди­ни­цы, пе­рей­ти к ша­гу 2.
+
Множество отсортированных списков с операцией <tex>\mathrm{merge}</tex> является [[Моноид|моноидом]], где нейтральным элементом будет пустой список.
  
=Слияние 2-х массивов=
+
Ниже приведён псевдокод процедуры слияния, который сливает две части массива <tex>a</tex> {{---}} <tex>[left; mid)</tex> и <tex>[mid; right)</tex>
Допустим, у нас есть два отсортированных массива А и B размерами <tex>N_a </tex> и <tex>N_b </tex> со­ответственно, и мы хотим объединить их элементы в один большой отсортирован­ный массив C размером <tex>N_a + N_b </tex> . Для этого можно применить процедуру слия­ния, суть которой заключается в повторяющемся «отделении» элемента, наи­меньшего из двух имеющихся в началах исходных массивов, и присоединении это­го элемента к концу результирующего массива. Элементы мы переносим до тех пор, пока один из исходных массивов не закончится. После этого оставшийся «хвост» одного из входных массивов дописывается в конец результирующего мас­сива. Пример работы процедуры показан на рисунке:
+
<code style="display: inline-block">
[[Файл:Mergearr.png|right|500px|thumb|Пример работы процедуры слияния.]]
+
'''function''' merge(a : '''int[n]'''; left, mid, right : '''int'''):
<br>
+
    it1 = 0
Алгоритм слияния формально можно записать следующим образом:
+
    it2 = 0
 +
    result : '''int[right - left]'''
 +
 
 +
    '''while''' left + it1 < mid '''and''' mid + it2 < right
 +
        '''if''' a[left + it1] < a[mid + it2]
 +
            result[it1 + it2] = a[left + it1]
 +
            it1 += 1
 +
        '''else'''
 +
            result[it1 + it2] = a[mid + it2]
 +
            it2 += 1
 +
 
 +
    '''while''' left + it1 < mid
 +
        result[it1 + it2] = a[left + it1]
 +
        it1 += 1
 +
 
 +
    '''while''' mid + it2 < right
 +
        result[it1 + it2] = a[mid + it2]
 +
        it2 += 1
 +
 
 +
    '''for''' i = 0 '''to''' it1 + it2
 +
        a[left + i] = result[i]
 +
</code>
  
[[Файл:merge41.png]]
+
===Рекурсивный алгоритм===
 +
Функция сортирует подотрезок массива с индексами в полуинтервале <tex>[left; right)</tex>.
 +
<code style="display: inline-block">
 +
'''function''' mergeSortRecursive(a : '''int[n]'''; left, right : '''int'''):
 +
    '''if''' left + 1 >= right
 +
        '''return'''
 +
    mid = (left + right) / 2
 +
    mergeSortRecursive(a, left, mid)
 +
    mergeSortRecursive(a, mid, right)
 +
    merge(a, left, mid, right)
 +
</code>
  
=Рекурсивный алгоритм=
+
===Итеративный алгоритм===
[[Файл:Merge sort1.png|500px|right|thumb|Пример работы рекурсивного алгоритма сортировки слиянием]]
+
При итеративном алгоритме используется на <tex>O(\log n)</tex> меньше памяти, которая раньше тратилась на рекурсивные вызовы.
Проще всего формализовать этот алгоритм рекурсивным способом. Функ­ция сортирует участок массива от элемента с номером a до элемен­та с номером b:
+
<code style="display: inline-block">
 +
  '''function''' mergeSortIterative(a : '''int[n]'''):
 +
    '''for''' i = 1 '''to''' n, i *= 2
 +
        '''for''' j = 0 '''to''' n - i, j += 2 * i
 +
            merge(a, j, j + i, min(j + 2 * i, n))
 +
</code>
  
// r и l - правая и левая граница массива, m - середина
+
==Время работы==
 +
Чтобы оценить время работы этого алгоритма, составим рекуррентное соотношение. Пускай <tex>T(n)</tex> {{---}} время сортировки массива длины <tex>n</tex>, тогда для сортировки слиянием справедливо <tex>T(n)=2T(n/2)+O(n)</tex> <br>
 +
<tex>O(n)</tex> {{---}} время, необходимое на то, чтобы слить два массива длины <tex>n</tex>. Распишем это соотношение:
  
// делим на 2 половины
+
<tex>T(n)=2T(n/2)+O(n)=4T(n/4)+2O(n)=\dots=T(1)+\log(n)O(n)=O(n\log(n))</tex>.
  
<tex>m</tex>  <tex>=</tex>  <tex>r</tex> <tex>/</tex> <tex>2</tex>
+
==Сравнение с другими алгоритмами==
 +
Достоинства:
 +
* устойчивая,
 +
* можно написать эффективную [[Многопоточная сортировка слиянием|многопоточную сортировку слиянием]],
 +
* сортировка данных, расположенных на периферийных устройствах и не вмещающихся в оперативную память<ref>[http://en.wikipedia.org/wiki/External_sorting Wikipedia {{---}} External sorting]</ref>.
 +
Недостатки:
 +
* требуется дополнительно <tex>O(n)</tex> памяти, но можно модифицировать до <tex>O(1)</tex>.
  
// условие выхода - если массив стал состоять из 1 элемента
+
==См. также==
 +
* [[Сортировка кучей]]
 +
* [[Быстрая сортировка]]
 +
* [[Timsort]]
 +
* [[Cортировка слиянием с использованием O(1) дополнительной памяти]]
  
<tex>if</tex>  <tex>m</tex>  <tex>==</tex>  <tex>r</tex>
+
==Примечания==
 +
<references/>
  
<tex>return</tex>
+
==Источники информации==
 +
*[http://ru.wikipedia.org/wiki/Mergesort Википедия {{---}} сортировка слиянием]
 +
*[http://www.sorting-algorithms.com/merge-sort Визуализатор]
 +
*[https://ru.wikibooks.org/wiki/Примеры_реализации_сортировки_слиянием Викиучебник {{---}} Примеры реализации на различных языках программирования]
  
// рекурсивная сортировка правой и левой частей, в функцию передаются левая и правая границы массива
 
  
<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]</tex>
 
 
Пример работы алгоритма показан на рисунке:
 
 
=Время работы=
 
Чтобы оценить время работы этого алгоритма, составим рекуррентное соотношение. Пускай <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>.
 
 
=Свойства=
 
Стабильный.
 
 
<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| Примеры реализации на различных языках (Википедия)]
 
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Сортировки]]
 
[[Категория: Сортировки]]
 +
[[Категория: Сортировки на сравнениях]]

Текущая версия на 19:10, 4 сентября 2022

Сортировка слиянием (англ. Merge sort) — алгоритм сортировки, использующий [math]O(n)[/math] дополнительной памяти и работающий за [math]O(n\log(n))[/math] времени.

Принцип работы

Пример работы процедуры слияния.
Пример работы рекурсивного алгоритма сортировки слиянием
Пример работы итеративного алгоритма сортировки слиянием

Алгоритм использует принцип «разделяй и властвуй»: задача разбивается на подзадачи меньшего размера, которые решаются по отдельности, после чего их решения комбинируются для получения решения исходной задачи. Конкретно процедуру сортировки слиянием можно описать следующим образом:

  1. Если в рассматриваемом массиве один элемент, то он уже отсортирован — алгоритм завершает работу.
  2. Иначе массив разбивается на две части, которые сортируются рекурсивно.
  3. После сортировки двух частей массива к ним применяется процедура слияния, которая по двум отсортированным частям получает исходный отсортированный массив.

Слияние двух массивов

У нас есть два массива [math]a[/math] и [math]b[/math] (фактически это будут две части одного массива, но для удобства будем писать, что у нас просто два массива). Нам надо получить массив [math]c[/math] размером [math]|a| + |b|[/math]. Для этого можно применить процедуру слияния. Эта процедура заключается в том, что мы сравниваем элементы массивов (начиная с начала) и меньший из них записываем в финальный. И затем, в массиве у которого оказался меньший элемент, переходим к следующему элементу и сравниваем теперь его. В конце, если один из массивов закончился, мы просто дописываем в финальный другой массив. После мы наш финальный массив записываем заместо двух исходных и получаем отсортированный участок.

Множество отсортированных списков с операцией [math]\mathrm{merge}[/math] является моноидом, где нейтральным элементом будет пустой список.

Ниже приведён псевдокод процедуры слияния, который сливает две части массива [math]a[/math][math][left; mid)[/math] и [math][mid; right)[/math]

function merge(a : int[n]; left, mid, right : int):
    it1 = 0
    it2 = 0
    result : int[right - left]
  
    while left + it1 < mid and mid + it2 < right
        if a[left + it1] < a[mid + it2]
            result[it1 + it2] = a[left + it1]
            it1 += 1
        else
            result[it1 + it2] = a[mid + it2]
            it2 += 1
  
    while left + it1 < mid
        result[it1 + it2] = a[left + it1]
        it1 += 1
  
    while mid + it2 < right
        result[it1 + it2] = a[mid + it2]
        it2 += 1
  
    for i = 0 to it1 + it2
        a[left + i] = result[i]

Рекурсивный алгоритм

Функция сортирует подотрезок массива с индексами в полуинтервале [math][left; right)[/math].

function mergeSortRecursive(a : int[n]; left, right : int):
    if left + 1 >= right
        return
    mid = (left + right) / 2
    mergeSortRecursive(a, left, mid)
    mergeSortRecursive(a, mid, right)
    merge(a, left, mid, right)

Итеративный алгоритм

При итеративном алгоритме используется на [math]O(\log n)[/math] меньше памяти, которая раньше тратилась на рекурсивные вызовы.

function mergeSortIterative(a : int[n]):
    for i = 1 to n, i *= 2
        for j = 0 to n - i, j += 2 * i
            merge(a, j, j + i, min(j + 2 * i, n))

Время работы

Чтобы оценить время работы этого алгоритма, составим рекуррентное соотношение. Пускай [math]T(n)[/math] — время сортировки массива длины [math]n[/math], тогда для сортировки слиянием справедливо [math]T(n)=2T(n/2)+O(n)[/math]
[math]O(n)[/math] — время, необходимое на то, чтобы слить два массива длины [math]n[/math]. Распишем это соотношение:

[math]T(n)=2T(n/2)+O(n)=4T(n/4)+2O(n)=\dots=T(1)+\log(n)O(n)=O(n\log(n))[/math].

Сравнение с другими алгоритмами

Достоинства:

Недостатки:

  • требуется дополнительно [math]O(n)[/math] памяти, но можно модифицировать до [math]O(1)[/math].

См. также

Примечания

Источники информации