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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Итеративный алгоритм)
Строка 14: Строка 14:
 
У нас есть два массива <tex>a</tex> и <tex>b</tex> (фактически это будут две части одного массива, но для удобства будем писать, что у нас просто два массива). Нам надо получить массив <tex>c</tex> размером <tex>|a| + |b|</tex>. Для этого можно применить процедуру слияния. Эта процедура заключается в том, что мы сравниваем элементы массивов (начиная с начала) и меньший из них записываем в финальный. И затем, в массиве у которого оказался меньший элемент, переходим к следующему элементу и сравниваем теперь его. В конце, если один из массивов закончился, мы просто дописываем в финальный другой массив. После мы наш финальный массив записываем заместо двух исходных и получаем отсортированный участок.
 
У нас есть два массива <tex>a</tex> и <tex>b</tex> (фактически это будут две части одного массива, но для удобства будем писать, что у нас просто два массива). Нам надо получить массив <tex>c</tex> размером <tex>|a| + |b|</tex>. Для этого можно применить процедуру слияния. Эта процедура заключается в том, что мы сравниваем элементы массивов (начиная с начала) и меньший из них записываем в финальный. И затем, в массиве у которого оказался меньший элемент, переходим к следующему элементу и сравниваем теперь его. В конце, если один из массивов закончился, мы просто дописываем в финальный другой массив. После мы наш финальный массив записываем заместо двух исходных и получаем отсортированный участок.
  
Множество отсортированных списков с операцией <tex>\mathrm{merge}</tex> является [[Моноид|моноидом]], где нейтральным элементом будет <tex>\varnothing</tex>.
+
Множество отсортированных списков с операцией <tex>\mathrm{merge}</tex> является [[Моноид|моноидом]], где нейтральным элементом будет пустой список.
  
 
Ниже приведён псевдокод процедуры слияния, который сливает две части массива <tex>a</tex> {{---}} <tex>[left; mid)</tex> и <tex>[mid; right)</tex>
 
Ниже приведён псевдокод процедуры слияния, который сливает две части массива <tex>a</tex> {{---}} <tex>[left; mid)</tex> и <tex>[mid; right)</tex>
Строка 72: Строка 72:
 
Осталось оценить <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>.
 
Осталось оценить <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>.
  
Достоинства:
+
==Сравнение с другими алгоритмами==
 +
===Достоинства===
 
* устойчивая.
 
* устойчивая.
Недостатки:
+
===Недостатки===
 
* при любых входных данных время работы {{---}} <tex>O(n\log{n})</tex>,
 
* при любых входных данных время работы {{---}} <tex>O(n\log{n})</tex>,
* требуется дополнительно <tex>O(n)</tex> памяти.
+
* требуется дополнительно <tex>O(n)</tex> памяти, но можно модифицировать до <tex>O(1)</tex>.
  
 
==См. также==
 
==См. также==

Версия 16:32, 23 мая 2015

Сортировка слиянием (англ. Merge sort) — алгоритм сортировки, пред­ло­женный Джо­ном фон Ней­ма­ном в 1945 го­ду.

Это устойчивый алгоритм, использующий [math]O(n)[/math] дополнительной памяти и работающий за [math]O(n[/math] [math]\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]T(n)=2T(n/2)+O(n)=4T(n/4)+2O(n)=\dots=2^kT(1)+kO(n)[/math].

Осталось оценить [math]k[/math]. Мы знаем, что [math]2^k=n[/math], а значит [math]k=\log n[/math]. Уравнение примет вид [math]T(n)=nT(1)+ \log n[/math] [math]O(n)[/math]. Так как [math]T(1)[/math] — константа, то [math]T(n)=O(n)+\log n [/math] [math]O(n)=O(n\log n)[/math].

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

Достоинства

  • устойчивая.

Недостатки

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

См. также

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