Описание алгоритма. Многие алгоритмы по природе своей рекурсивны(recursive): решая некото­рую задачу, они вызывают самих себя для решения её подзадач

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

Многие алгоритмы по природе своей рекурсивны (recursive): решая некото­рую задачу, они вызывают самих себя для решения её подзадач. Идея метода «разделяй и властвуй» состоит как раз в этом. Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются (с помо­щью рекурсивного вызова – или непосредственно, если размер достаточно мал). Наконец, их решения комбинируются и получается решение исходной задачи.

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

Нетривиальным этапом является соединение двух упорядоченных массивов в один. Оно выполняется с помощью вспомогательной процедуры Merge (A,p,q,r). Параметрами этой процедуры являются массив А и числа р, q, r, указывающие границы сливаемых участков. Процедура предполагает, что p ≤ q < r и что участки А [ р..q ]и A [ q + 1.. r ] уже отсортированы, и сливает (merges) их в один участок А [ р..r ]. Алгоритм данной процедуры очень прост – на начало каждого из участков устанавливаются два курсора – i и j. Процедура объединения потребует наличия дополнительной памяти, равной объему входа, и количества элементарных шагов, прямо пропорционального объему входа, т.к. на каждой итерации один из элементов будет помещаться в результирующий массив. Предположим, что исходные объединяемые массивы отсортированы по возрастанию. Процедура очень проста – на каждой из итераций производится соревнование между курсорами. Право на копирование своего элемента в целевой массив получает тот курсор, который в данный момент находится над наименьшим элементом. Если оба элемента под курсорами равны, выигрывает находящийся слева (i), иначе данная сортировка не будет устойчивой, т.е. сохраняющей исходный порядок на одинаковых ключах. При сортировке по убыванию приоритет в соревновании также остается за левым курсором i. Ясно, что каждый шаг требует ограниченного числа действий, и общее число действий есть Θ(n).

Рисунок 2.2 – Сортировка слиянием для массива А =

На листинге 2.1 представлен листинг процедуры сортировки слиянием

Merge-Sort(A, p, r), которая сортирует участок А [ р.. r ] массива А, не меняя остальную часть массива. При р ≥ r участок содержит максимум один элемент, и тем самым уже отсор­тирован. В противном случае мы отыскиваем число q, которое делит участок на две примерно равные части А [ р.. q ] (содержит элементов) и A [ q + 1.. r ] содержит элементов. Здесь через обозначается целая часть х (наибольшее целое число, меньшее или равное х), а через – наименьшее целое число, большее или равное х. Иначе, можно расшифровать как «округление вниз» а как «округление вверх».

Листинг 2.1 – Процедура сортировки слиянием

Весь массив теперь можно отсортировать с помощью вызова

Merge-Sort(A, 1, length [ A ]). Если длина массива n = length [ A ] есть степень двойки, то в процессе сортировки произойдёт слияние пар элементов в отсортирован­ные участки длины 2, затем слияние пар таких участков в отсортированные участки длины 4 и так далее до n (на последнем шаге соединяются два отсортированных участка длины n / 2).

procedure MergeSort(n: integer;

var A: array[1..n] of integer);

{Процедура сортировки слиянием}

var

i, j, k, t, s, Start1, Fin1, Fin2: integer;

B: array[1..n] of integer;

begin

k:= 1; {Начальное значение длины участков}

while k < n do begin {пока участок не весь массив}

t:= 0; {начало 1-й пары участков}

while t+k < n do begin {пока не все участки просмотрели}

{Определяем границы рассматриваемых участков}

Start1:= t+1; Fin1:= t+k; {Начало и конец 1-го участка}

if t+2*k > n then Fin2:= n

else Fin2:= t+2*k; {Конец 2-го участка}

i:= Start1; {Начальное значение индекса в 1-м участке}

j:= Fin1 + 1; {Начальное значение индекса в 2-м участке}

s:= 1; {Начальное значение индекса в массиве B}

{Заполняем B элементами из двух участков}

while (i <= Fin1) and (j <= Fin2) do begin

{Сравниваем попарно элементы из двух участков}

if A[i] < A[j] then begin

{Вставляем элемент из 1-го участка}

B[s]:= A[i];

i:= i + 1;

end else begin

{Вставляем элемент из 2-го участка}

B[s]:= A[j];

j:= j + 1;

end;

s:= s + 1;

end;

{Добавляем в массив B оставшиеся элементы из 1-го участка}

while (i <= Fin1) do begin

B[s]:= A[i];

i:= i + 1; s:= s + 1;

end;

{Добавляем в массив B оставшиеся элементы из 2-го участка}

while (j <= Fin2) do begin

B[s]:= A[j];

j:= j + 1; s:= s + 1;

end;

t:= Fin2; {Переходим к следующей паре участков}

end;

k:= k * 2; {Удваиваем значение длины участков}

{Сохраняем полученный промежуточный результат}

for s:= 1 to t do A[s]:= B[s];

end;

end;

Листинг 2.2 – Нерекурсивная процедура сортировки слиянием (неустойчивый вариант реализации)

2.3.2 Анализ времени работы алгоритмов «разделяй и властвуй»

Как оценить время работы рекурсивного алгоритма? При подсчёте требуется учитывать время, затрачиваемое на рекурсивные вызовы, так что получа­ется некоторое рекуррентное соотношение (recurrence equation). Далее следует оценить время работы, исходя из этого соотношения.

Предположим, что алгоритм разбивает за­дачу размера п на а подзадач, каждая из которых имеет в b раз меньший размер. Будем считать, что разбиение требует времени D (n), а соединение полученных решений – времени С (п). Тогда получаем соотношение для времени работы Т (п)на задачах размера п (в худшем случае):

Т (п)= a·T (n / b)+ D (n)+ С (п).

Это соотношение выполнено для достаточно больших n, когда задачу имеет смысл разбивать на подзадачи. Для малых n, когда такое разбиение невозможно или не нужно, применяется один из прямых методов решения задачи. Поскольку n огра­ничено, время работы тоже не превосходит некоторой константы.