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

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

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
'''Сортировка слиянием''' (англ. ''Merge sort'') {{---}} алгоритм сортировки, использующий <tex>O(n)</tex> дополнительной памяти и работающий за <tex>O(n\log(n))</tex> времени.
+
==Описание==
 +
'''Сортировка слиянием''' алгоритм сортировки. Он был пред­ло­жен Джо­ном фон Ней­ма­ном в 1945 го­ду.
 +
 
 +
Это устойчивый ал­го­ритм, использующий <tex>O(n)</tex> дополнительной памяти и <tex>O(n</tex> <tex>\log(n))</tex> времени.
 +
*[http://www.sorting-algorithms.com/merge-sort Анимированная работа алгоритма (англ.)]
  
 
==Принцип работы==
 
==Принцип работы==
[[Файл:Merging_two_arrays.png|270px|right|thumb|Пример работы процедуры слияния.]]
+
[[Файл:Merge-sort-example.png|right|300px|thumb|Пример работы процедуры слияния.]]
 +
Этот алгоритм использует принцип «разделяй и властвуй». Этот принцип заключается в том, что исходная задача разбивается на подзадачи меньшего размера, а потом они решаются рекурсивным методом или же конкретно, если их размер мал. Потом из решения объединяются и получается решение основной (исходной) задачи.
  
[[Файл:Merge sort1.png|300px|right|thumb|Пример работы рекурсивного алгоритма сортировки слиянием]]
+
Для процедуры слияния требуется два отсортированных массива. Зная, что массив из одного элемента по определению отсортирован, мы можем разработать такой алгоритм:
  
[[Файл:Merge sort itearative.png|300px|right|thumb|Пример работы итеративного алгоритма сортировки слиянием]]
+
# Массив разбивается на равные (или почти равные) части, до тех пор, пока он не разобьется на части, размер которых равен единице.
 +
# Далее каждая из частей сортируется по отдельности. Или нет, в случае, если это у нас одиночный элемент.
 +
# После происходия слияние двух упорядоченных массивов в один.
  
Алгоритм использует принцип «разделяй и властвуй»: задача разбивается на подзадачи меньшего размера, которые решаются по отдельности, после чего их решения комбинируются для получения решения исходной задачи. Конкретно процедуру сортировки слиянием можно описать следующим образом:
+
===Слияние двух массивов===
 +
У нас есть два массива <tex>A</tex> и <tex>B</tex> (фактически это будут две части одного массива, но для удобства будем писать, что у нас просто два массива). Нам надо получить массив <tex>C</tex> размером <tex>|A| + |B|</tex>. Для этого можно применить процедуру слияния. Эта процедура заключается в том, что мы сравниваем элементы массивов (начиная с начала) и меньший из них записываем в финальный. И затем, в массиве у которого оказался меньший элемент, переходим к следующему элементу и сравниваем теперь его. В конце, если один из массивов закончился, мы просто дописываем в финальный другой массив. После мы наш финальный массив записываем заместо двух исходных и получаем отсортированный участок.
  
# Если в рассматриваемом массиве один элемент, то он уже отсортирован {{---}} алгоритм завершает работу.
+
Алгоритм слияния формально можно записать следующим образом:
# Иначе массив разбивается на две части, которые сортируются рекурсивно.
 
# После сортировки двух частей массива к ним применяется процедура слияния, которая по двум отсортированным частям получает исходный отсортированный массив.
 
  
===Слияние двух массивов===
+
Будет происходить слияние частей [left, middle) и [middle, right]
У нас есть два массива <tex>a</tex> и <tex>b</tex> (фактически это будут две части одного массива, но для удобства будем писать, что у нас просто два массива). Нам надо получить массив <tex>c</tex> размером <tex>|a| + |b|</tex>. Для этого можно применить процедуру слияния. Эта процедура заключается в том, что мы сравниваем элементы массивов (начиная с начала) и меньший из них записываем в финальный. И затем, в массиве у которого оказался меньший элемент, переходим к следующему элементу и сравниваем теперь его. В конце, если один из массивов закончился, мы просто дописываем в финальный другой массив. После мы наш финальный массив записываем заместо двух исходных и получаем отсортированный участок.
 
  
Множество отсортированных списков с операцией <tex>\mathrm{merge}</tex> является [[Моноид|моноидом]], где нейтральным элементом будет пустой список.
+
<pre>// слияние двух частей одного массива с помощью временного
 
+
// left - левая граница, right - правая, middle - середина
Ниже приведён псевдокод процедуры слияния, который сливает две части массива <tex>a</tex> {{---}} <tex>[left; mid)</tex> и <tex>[mid; right)</tex>
+
merge(array a, int left, int middle, int right)  
<code style="display: inline-block">
+
  i = left, j = middle, k = 0;
'''function''' merge(a : '''int[n]'''; left, mid, right : '''int'''):
+
  array temp = new array[a.size()];
    it1 = 0
+
  while i < middle and j <= right
    it2 = 0
+
    if (a[j] < a[i])
    result : '''int[right - left]'''
+
      temp[k++] = a[j++];
 
+
    else
    '''while''' left + it1 < mid '''and''' mid + it2 < right
+
      temp[k++] = a[i++];
        '''if''' a[left + it1] < a[mid + it2]
+
  while i < middle
            result[it1 + it2] = a[left + it1]
+
    temp[k++] = a[i++];
            it1 += 1
+
  while j <= right
        '''else'''
+
    temp[k++] = a[j++];
            result[it1 + it2] = a[mid + it2]
+
  for (int t = 0; t != k; t++)
            it2 += 1
+
    a[t] = temp[t];
 
+
// в конце a[1..k] это будет отсортированный массив
    '''while''' left + it1 < mid
+
</pre>
        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>
 
  
 
===Рекурсивный алгоритм===
 
===Рекурсивный алгоритм===
Функция сортирует подотрезок массива с индексами в полуинтервале <tex>[left; right)</tex>.
+
[[Файл:Merge sort1.png|300px|right|thumb|Пример работы рекурсивного алгоритма сортировки слиянием]]
<code style="display: inline-block">
+
Функция сортирует участок массива от элемента с номером left до элемен­та с номером right. Будем реализовывать так, что бы производилась сортировка полуинтервала [left, right)
'''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>
 
 
 
===Итеративный алгоритм===
 
При итеративном алгоритме используется на <tex>O(\log n)</tex> меньше памяти, которая раньше тратилась на рекурсивные вызовы.
 
<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>
 
  
==Время работы==
+
right и left — правая и левая граница массива, middle — середина.
Чтобы оценить время работы этого алгоритма, составим рекуррентное соотношение. Пускай <tex>T(n)</tex> {{---}} время сортировки массива длины <tex>n</tex>, тогда для сортировки слиянием справедливо <tex>T(n)=2T(n/2)+O(n)</tex> <br>
 
<tex>O(n)</tex> {{---}} время, необходимое на то, чтобы слить два массива длины <tex>n</tex>. Распишем это соотношение:
 
  
<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>.
+
<pre>
 +
sort(array a, int left, int right)
 +
  middle = (left + right) / 2; 
 +
  if left >= right   
 +
    return;
 +
  sort(a, left, middle);
 +
  sort (a, middle, right);
 +
  merge(array a, left, middle, right);
 +
</pre>
  
==Сравнение с другими алгоритмами==
+
Пример работы алгоритма показан на рисунке:
Достоинства:
 
* устойчивая,
 
* можно написать эффективную [[Многопоточная сортировка слиянием|многопоточную сортировку слиянием]],
 
* сортировка данных, расположенных на периферийных устройствах и не вмещающихся в оперативную память<ref>[http://en.wikipedia.org/wiki/External_sorting Wikipedia {{---}} External sorting]</ref>.
 
Недостатки:
 
* требуется дополнительно <tex>O(n)</tex> памяти, но можно модифицировать до <tex>O(1)</tex>.
 
  
==См. также==
+
==Время работы==
* [[Сортировка кучей]]
+
Чтобы оценить время работы этого алгоритма, составим рекуррентное соотношение. Пускай <tex>T(n)</tex> — время сортировки массива длины n, тогда для сортировки слиянием справедливо <tex>T(n)=2T(n/2)+O(n)</tex> <br>
* [[Быстрая сортировка]]
+
(<tex>O(n)</tex> — это время, необходимое на то, чтобы слить два массива). Распишем это соотношение:
* [[Timsort]]
 
* [[Cортировка слиянием с использованием O(1) дополнительной памяти]]
 
  
==Примечания==
+
<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>2O(n)</tex> <tex>=</tex> <tex>...</tex> <tex>=</tex> <tex>2^kT(1)</tex> <tex>+</tex> <tex>kO(n).</tex>
<references/>
 
  
==Источники информации==
+
Осталось оценить <tex>k</tex>. Мы знаем, что <tex>2^k=n</tex>, а значит <tex>k=\log n</tex>. Уравнение примет вид <tex>T(n)=nT(1)+ \log n</tex> <tex>O(n)</tex>. Так как <tex>T(1)</tex> — константа, то <tex>T(n)=O(n)+\log n </tex> <tex>O(n)=O(n\log n)</tex>.
*[http://ru.wikipedia.org/wiki/Mergesort Википедия {{---}} сортировка слиянием]
 
*[http://www.sorting-algorithms.com/merge-sort Визуализатор]
 
*[https://ru.wikibooks.org/wiki/Примеры_реализации_сортировки_слиянием Викиучебник {{---}} Примеры реализации на различных языках программирования]
 
  
 +
==Ссылки==
 +
*[http://ru.wikipedia.org/wiki/Mergesort Википедия — сортировка слиянием]
 +
*[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/ Сортировка слиянием в картинках (источник картинок в статье)]
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Сортировки]]
 
[[Категория: Сортировки]]
[[Категория: Сортировки на сравнениях]]
 

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблон, используемый на этой странице: