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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Время работы)
Строка 1: Строка 1:
==Описание==
+
'''Сортировка слиянием''' (англ. ''Merge sort'') {{---}} алгоритм сортировки, пред­ло­женный Джо­ном фон Ней­ма­ном в 1945 го­ду.
'''Сортировка слиянием''' алгоритм сортировки. Он был пред­ло­жен Джо­ном фон Ней­ма­ном в 1945 го­ду.
 
  
Это устойчивый ал­го­ритм, использующий <tex>O(n)</tex> дополнительной памяти и <tex>O(n</tex> <tex>\log n)</tex> времени.
+
Это устойчивый алгоритм, использующий <tex>O(n)</tex> дополнительной памяти и <tex>O(n</tex> <tex>\log n)</tex> времени.
  
 
==Принцип работы==
 
==Принцип работы==
 
[[Файл:Merging_two_arrays.png|270px|right|thumb|Пример работы процедуры слияния.]]
 
[[Файл:Merging_two_arrays.png|270px|right|thumb|Пример работы процедуры слияния.]]
Алгоритм использует прицип «разделяй и властвуй»: задача разбивается на подзадачи меньшего размера, которые решаются по отдельности, после чего их решения комбинируются для получения решения исходной задачи. Конкретно процедуру сортировки слиянием можно описать следующим образом:
+
Алгоритм использует принцип «разделяй и властвуй»: задача разбивается на подзадачи меньшего размера, которые решаются по отдельности, после чего их решения комбинируются для получения решения исходной задачи. Конкретно процедуру сортировки слиянием можно описать следующим образом:
  
# Если в рассматриваемом массиве один элемент, то он уже отсортирован алгоритм завершает работу.
+
# Если в рассматриваемом массиве один элемент, то он уже отсортирован {{---}} алгоритм завершает работу.
 
# Иначе массив разбивается на две части, которые сортируются рекурсивно.
 
# Иначе массив разбивается на две части, которые сортируются рекурсивно.
 
# После сортировки двух частей массива к ним применяется процедура слияния, которая по двум отсортированным частям получает исходный отсортированный массив.
 
# После сортировки двух частей массива к ним применяется процедура слияния, которая по двум отсортированным частям получает исходный отсортированный массив.
Строка 15: Строка 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>. Для этого можно применить процедуру слияния. Эта процедура заключается в том, что мы сравниваем элементы массивов (начиная с начала) и меньший из них записываем в финальный. И затем, в массиве у которого оказался меньший элемент, переходим к следующему элементу и сравниваем теперь его. В конце, если один из массивов закончился, мы просто дописываем в финальный другой массив. После мы наш финальный массив записываем заместо двух исходных и получаем отсортированный участок.
  
Ниже приведён псевдокод процедуры слияния, который сливает две части массива A <tex>[left; mid)</tex> и <tex>[mid; right)</tex>
+
Ниже приведён псевдокод процедуры слияния, который сливает две части массива <tex>A</tex> {{---}} <tex>[left; mid)</tex> и <tex>[mid; right)</tex>
  
  Merge(A : '''int[1..N]'''; left, mid, right : '''int'''):
+
  merge(a : '''int[N]'''; left, mid, right : '''int'''):
 
     it1 = 0
 
     it1 = 0
 
     it2 = 0
 
     it2 = 0
Строка 23: Строка 22:
 
    
 
    
 
     '''while''' left + it1 < mid '''and''' mid + it2 < right
 
     '''while''' left + it1 < mid '''and''' mid + it2 < right
         '''if''' A[left + it1] < A[mid + it2]
+
         '''if''' a[left + it1] < a[mid + it2]
             result[it1 + it2] = A[left + it1]
+
             result[it1 + it2] = a[left + it1]
 
             it1 += 1
 
             it1 += 1
 
         '''else'''
 
         '''else'''
             result[it1 + it2] = A[mid + it2]
+
             result[it1 + it2] = a[mid + it2]
 
             it2 += 1
 
             it2 += 1
 
    
 
    
 
     '''while''' left + it1 < mid
 
     '''while''' left + it1 < mid
         result[it1 + it2] = A[left + it1]
+
         result[it1 + it2] = a[left + it1]
 
         it1 += 1
 
         it1 += 1
 
    
 
    
 
     '''while''' mid + it2 < right
 
     '''while''' mid + it2 < right
         result[it1 + it2] = A[mid + it2]
+
         result[it1 + it2] = a[mid + it2]
 
         it2 += 1
 
         it2 += 1
 
    
 
    
 
     '''for''' i = 0 '''to''' it1 + it2
 
     '''for''' i = 0 '''to''' it1 + it2
         A[left + i] = result[i]
+
         a[left + i] = result[i]
  
 
===Рекурсивный алгоритм===
 
===Рекурсивный алгоритм===
Строка 45: Строка 44:
 
[[Файл:Merge sort1.png|300px|thumb|Пример работы рекурсивного алгоритма сортировки слиянием]]
 
[[Файл:Merge sort1.png|300px|thumb|Пример работы рекурсивного алгоритма сортировки слиянием]]
  
  MergeSort(A : '''int[1..N]'''; left, right : '''int'''):
+
  mergeSortRecursive(a : '''int[N]'''; left, right : '''int'''):
 
     '''if''' left + 1 >= right
 
     '''if''' left + 1 >= right
         return
+
         '''return'''
 
     mid = (left + right) / 2
 
     mid = (left + right) / 2
     MergeSort(A, left, mid)
+
     mergeSortRecursive(a, left, mid)
     MergeSort(A, mid, right)
+
     mergeSortRecursive(a, mid, right)
     Merge(A, left, mid, right)
+
     merge(a, left, mid, right)
  
 
===Итеративный алгоритм===
 
===Итеративный алгоритм===
 
Функция сортирует подотрезок массива с индексами в полуинтервале <tex>[left; right)</tex>.
 
Функция сортирует подотрезок массива с индексами в полуинтервале <tex>[left; right)</tex>.
  
  MergeSortIterative(A : '''int[1..N]'''; left, right : '''int'''):
+
  mergeSortIterative(a : '''int[N]'''; left, right : '''int'''):
 
     '''for''' i = 1 '''to''' N, i *= 2
 
     '''for''' i = 1 '''to''' N, i *= 2
 
         '''for''' j = left '''to''' right - i, j += 2 * i
 
         '''for''' j = left '''to''' right - i, j += 2 * i
             Merge(A, j, j + i, min(j + 2 * i, right))
+
             Merge(a, j, j + i, min(j + 2 * i, right))
 
   
 
   
 
==Время работы==
 
==Время работы==
Чтобы оценить время работы этого алгоритма, составим рекуррентное соотношение. Пускай <tex>T(n)</tex> время сортировки массива длины <tex>n</tex>, тогда для сортировки слиянием справедливо <tex>T(n)=2T(n/2)+O(n)</tex> <br>
+
Чтобы оценить время работы этого алгоритма, составим рекуррентное соотношение. Пускай <tex>T(n)</tex> {{---}} время сортировки массива длины <tex>n</tex>, тогда для сортировки слиянием справедливо <tex>T(n)=2T(n/2)+O(n)</tex> <br>
(<tex>O(n)</tex> — это время, необходимое на то, чтобы слить два массива). Распишем это соотношение:
+
<tex>O(n)</tex> {{---}} время, необходимое на то, чтобы слить два массива. Распишем это соотношение:
  
 
<tex>T(n)=2T(n/2)+O(n)=4T(n/4)+2O(n)=\dots=2^kT(1)+kO(n)</tex>.
 
<tex>T(n)=2T(n/2)+O(n)=4T(n/4)+2O(n)=\dots=2^kT(1)+kO(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>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://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 Викиучебник {{---}} Примеры реализации на различных языках программирования]
 
  
 
==См. также==
 
==См. также==
 
* [[Сортировка кучей]]
 
* [[Сортировка кучей]]
 
* [[Быстрая сортировка]]
 
* [[Быстрая сортировка]]
*[[Сортировка слиянием с использованием O(1) дополнительной памяти]]
+
*[[Cортировка слиянием с использованием O(1) дополнительной памяти]]
 +
*[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 Викиучебник {{---}} Примеры реализации на различных языках программирования]
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Сортировка]]
 
[[Категория: Сортировка]]
 
[[Категория: Сортировки на сравнениях]]
 
[[Категория: Сортировки на сравнениях]]

Версия 12:54, 9 мая 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]A[/math][math][left; mid)[/math] и [math][mid; right)[/math]

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].

Пример работы рекурсивного алгоритма сортировки слиянием
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][left; right)[/math].

mergeSortIterative(a : int[N]; left, right : int):
    for i = 1 to N, i *= 2
        for j = left to right - i, j += 2 * i
            Merge(a, j, j + i, min(j + 2 * i, right))

Время работы

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

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

См. также