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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 19: Строка 19:
 
Алгоритм слияния формально можно записать следующим образом:
 
Алгоритм слияния формально можно записать следующим образом:
  
[[Файл:Merge1.png|center|380px|thumb]]
+
a = 0; b = 0;
 +
While (a < <tex>n_a</tex>) and (b < <tex>n_b</tex>) 
 +
  If A[a] <tex>\leqslant</tex> B[b]
 +
    C[a + b] = A[a];
 +
    a = a + 1;
 +
  Else
 +
    C[a + b] = B[b];
 +
    b = b + 1;
 +
  End;
 +
End;
 +
If a <<tex>n_a</tex>
 +
  Copy remain part of A
 +
Else
 +
  Copy remain part of B
 +
End;
 +
 
  
 
=Рекурсивный алгоритм=
 
=Рекурсивный алгоритм=
 
Проще всего формализовать этот алгоритм рекурсивным способом. Функ­ция  сортирует участок массива от элемента с номером a до элемен­та с номером b:
 
Проще всего формализовать этот алгоритм рекурсивным способом. Функ­ция  сортирует участок массива от элемента с номером a до элемен­та с номером b:
[[Файл:Merge2.png|center|380px|thumb]]
+
Function MergeSort(a,b)
 +
  If b = a then Exit;
 +
  c = (a + b)/2;
 +
  Mergesort(a,c);
 +
  MergeSort(c + 1,b);
 +
  Merge fragments (a,c) and (c + 1,b);
 +
End

Версия 01:17, 16 мая 2011

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

Действие алгоритма на примере сортировки случайных точек.

Сортировка слиянием — вероятно, один из самых простых алгоритмов сортиров­ки (среди «быстрых» алгоритмов).Сортировка слиянием — стабильный алгоритм сортировки. Это означает, что по­рядок «равных» элементов не изменяется в результате работы алгоритма. В не­которых задачах это свойство достаточно важно. Этот алгоритм был предложен Джоном фон Нейманом в 1945 году.

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

Эта сортировка — хороший пример использования принципа «разделяй и властвуй». Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.

Для решения задачи сортировки эти три этапа выглядят так:

  • Сортируемый массив разбивается на две части примерно одинакового размера;
  • Каждая из получившихся частей сортируется отдельно, например — тем же самым алгоритмом;
  • Два упорядоченных массива половинного размера соединяются в один.

Рекурсивное разбиение задачи на меньшие происходит до тех пор, пока размер массива не достигнет единицы
(любой массив длины 1 можно считать упорядоченным).

Слияние 2-х массивов

Допустим, у нас есть два отсортированных массива А и B размерами [math]N_a [/math] и [math]N_b [/math] со­ответственно, и мы хотим объединить их элементы в один большой отсортирован­ный массив C размером [math]N_a + N_b [/math] . Для этого можно применить процедуру слия­ния, суть которой заключается в повторяющемся «отделении» элемента, наи­меньшего из двух имеющихся в началах исходных массивов, и присоединении это­го элемента к концу результирующего массива. Элементы мы переносим до тех пор, пока один из исходных массивов не закончится. После этого оставшийся «хвост» одного из входных массивов дописывается в конец результирующего мас­сива. Пример работы процедуры показан на рисунке:

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


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

a = 0; b = 0;
While (a < [math]n_a[/math]) and (b < [math]n_b[/math])  
  If A[a] [math]\leqslant[/math] B[b]
    C[a + b] = A[a];
    a = a + 1;
  Else
    C[a + b] = B[b];
    b = b + 1;
  End;
End;
If a <[math]n_a[/math]
  Copy remain part of A
Else
  Copy remain part of B
End;


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

Проще всего формализовать этот алгоритм рекурсивным способом. Функ­ция сортирует участок массива от элемента с номером a до элемен­та с номером b:

Function MergeSort(a,b)
  If b = a then Exit;
  c = (a + b)/2;
  Mergesort(a,c);
  MergeSort(c + 1,b);
  Merge fragments (a,c) and (c + 1,b);
End