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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Описание)
Строка 1: Строка 1:
 
==Описание==
 
==Описание==
[[Файл:Merge-sort1.gif|right|380px|thumb|Действие алгоритма.]]
 
 
'''Сортировка слиянием''' — алгоритм сортировки. Он был пред­ло­жен Джо­ном фон Ней­ма­ном в 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> времени.
 +
*[http://www.sorting-algorithms.com/merge-sort Анимированная работа алгоритма (англ.)]
  
 
==Принцип работы==
 
==Принцип работы==
 +
[[Файл:Merge-sort-example.jpg|right|300px|thumb|Пример работы процедуры слияния.]]
 
Этот алгоритм использует принцип «разделяй и властвуй». Этот принцип заключается в том, что исходная задача разбивается на подзадачи меньшего размера, а потом они решаются рекурсивным методом или же конкретно, если их размер мал. Потом из решения объединяются и получается решение основной (исходной) задачи.
 
Этот алгоритм использует принцип «разделяй и властвуй». Этот принцип заключается в том, что исходная задача разбивается на подзадачи меньшего размера, а потом они решаются рекурсивным методом или же конкретно, если их размер мал. Потом из решения объединяются и получается решение основной (исходной) задачи.
  
Строка 15: Строка 16:
  
 
===Слияние двух массивов===
 
===Слияние двух массивов===
[[Файл:Mergearr.png|right|300px|thumb|Пример работы процедуры слияния.]]
 
 
У нас есть два массива <tex>A</tex> и <tex>B</tex>. Нам надо получить массив <tex>C</tex> размером <tex>sizeof(A) + sizeof(B)</tex>. Для этого можно применить процедуру слияния. Эта процедура заключается в том, что мы сравниваем элементы массивов (начиная с начала) и меньший из них записываем в финальный. И затем, в массиве у которого оказался меньший элемент, переходим к следующему элементу и сравниваем теперь его. В конце, если один из массивов закончился, мы просто дописываем в финальный другой массив. После мы наш финальный массив записываем заместо двух исходных и получаем отсортированный участок.
 
У нас есть два массива <tex>A</tex> и <tex>B</tex>. Нам надо получить массив <tex>C</tex> размером <tex>sizeof(A) + sizeof(B)</tex>. Для этого можно применить процедуру слияния. Эта процедура заключается в том, что мы сравниваем элементы массивов (начиная с начала) и меньший из них записываем в финальный. И затем, в массиве у которого оказался меньший элемент, переходим к следующему элементу и сравниваем теперь его. В конце, если один из массивов закончился, мы просто дописываем в финальный другой массив. После мы наш финальный массив записываем заместо двух исходных и получаем отсортированный участок.
  
Строка 23: Строка 23:
 
// left - левая граница, right - правая, middle - середина
 
// left - левая граница, right - правая, middle - середина
 
merge(array a, int left, int middle, int right)  
 
merge(array a, int left, int middle, int right)  
  array b = a[middle, right];
 
 
   i = left, j = middle, k = 0;
 
   i = left, j = middle, k = 0;
 
   array temp = new array[sizeof(a) + sizeof(b)];
 
   array temp = new array[sizeof(a) + sizeof(b)];
 
   while i <= middle and j < right
 
   while i <= middle and j < right
     temp[k++] = (a[j] < b[i]) ? a[j++] : b[i++];
+
     temp[k++] = (a[j] < a[i]) ? a[j++] : a[i++];
 
   while i <= middle
 
   while i <= middle
     temp[k++] = b[i++];
+
     temp[k++] = a[i++];
 
   while j < right
 
   while j < right
 
     temp[k++] = a[j++];
 
     temp[k++] = a[j++];
Строка 36: Строка 35:
 
// в конце a[1..k] это будет отсортированный массив
 
// в конце a[1..k] это будет отсортированный массив
 
</pre>
 
</pre>
 +
  
 
==Рекурсивный алгоритм==
 
==Рекурсивный алгоритм==
 
[[Файл:Merge sort1.png|300px|right|thumb|Пример работы рекурсивного алгоритма сортировки слиянием]]
 
[[Файл:Merge sort1.png|300px|right|thumb|Пример работы рекурсивного алгоритма сортировки слиянием]]
Функция сортирует участок массива от элемента с номером left до элемен­та с номером right:
+
Функция сортирует участок массива от элемента с номером left до элемен­та с номером right. Будем реализовывать так, что бы производилась сортировка полуинтервала [left, right)
  
 
right и left — правая и левая граница массива, middle — середина.
 
right и left — правая и левая граница массива, middle — середина.
Строка 55: Строка 55:
  
 
Пример работы алгоритма показан на рисунке:
 
Пример работы алгоритма показан на рисунке:
 
==Восходящая сортировка слиянием==
 
[[Файл: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>
 
  
 
==Время работы==
 
==Время работы==
Строка 89: Строка 60:
 
(<tex>O(n)</tex> — это время, необходимое на то, чтобы слить два массива). Распишем это соотношение:
 
(<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>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>
  
Осталось оценить <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>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>.
  
  

Версия 11:38, 7 июня 2012

Описание

Сортировка слиянием — алгоритм сортировки. Он был пред­ло­жен Джо­ном фон Ней­ма­ном в 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]sizeof(A) + sizeof(B)[/math]. Для этого можно применить процедуру слияния. Эта процедура заключается в том, что мы сравниваем элементы массивов (начиная с начала) и меньший из них записываем в финальный. И затем, в массиве у которого оказался меньший элемент, переходим к следующему элементу и сравниваем теперь его. В конце, если один из массивов закончился, мы просто дописываем в финальный другой массив. После мы наш финальный массив записываем заместо двух исходных и получаем отсортированный участок.

Алгоритм слияния формально можно записать следующим образом:

// слияние двух массивов с помощью временного
// left - левая граница, right - правая, middle - середина
merge(array a, int left, int middle, int 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] < a[i]) ? a[j++] : a[i++];
  while i <= middle
    temp[k++] = a[i++];
  while j < right
    temp[k++] = a[j++];
  for (int t = 0; t != k; t++)
    a[t] = temp[t];
// в конце a[1..k] это будет отсортированный массив


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

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

Функция сортирует участок массива от элемента с номером left до элемен­та с номером right. Будем реализовывать так, что бы производилась сортировка полуинтервала [left, right)

right и left — правая и левая граница массива, middle — середина.

Условие выхода — если массив стал состоять из 1 элемента.

sort(array a, int left, int right)
  middle = (left + right) / 2;  
  if middle == right    
    return;
  sort(a, left, middle);
  sort (a, middle, right);
  merge(array a, left, middle, right);

Пример работы алгоритма показан на рисунке:

Время работы

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

[math]T(n)[/math] [math]=[/math] [math]2T(n/2)[/math] [math]+[/math] [math]O(n)[/math] [math]=[/math] [math]4T(n/4)[/math] [math]+[/math] [math]2O(n)[/math] [math]=[/math] [math]...[/math] [math]=[/math] [math]2^kT(1)[/math] [math]+[/math] [math]kO(n).[/math]

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


Ссылки