Занятие 4. Сортировка методом слияний.

Определение. Целочисленный массив с расположенными по неубыванию или по невозрастанию значениями элементов называется упорядоченным.

Использование упорядоченности позволяет создавать эффективные алгоритмы для решения многих интересных задач.

Задача слияния двух входных упорядоченных массивов А и В состоит в формировании упорядоченного выходного массива С, содержащего все элементы из входных массивов.

Рассмотрим алгоритм слияния для упорядоченных по неубыванию массивов. Вначале элемент А[1] сравнивается с элементом В[1] и наименьший из них записывается в массив С. Если наименьшим был А[1], то на следующем шаге сравниваются А[2] и B[1], а если наименьшим был B[1], то будут сравниваться A[1] и B[2] и т.д. Если на очередном шаге окажется, что из одного входного массива все элементы переписаны в С, то переписывается элемент из другого массива.

Рассмотрим пример работы алгоритма слияния.

Пусть в массиве А содержатся 3 элемента: {5, 13, 14}, а в массиве В – 4 элемента: {7, 9, 10, 12}. Внимательно рассмотрите таблицу, в которой по шагам показано изменение переменных i, i1, i2 и действия с массивами.

Рассмотрите фрагмент решения задачи на слияние двух массивов А и В, которые содержат соответственно n1 и n2 элементов. Результирующий массив С будет содержать n1+n2 элементов.

. . .

i1 := 1;

i2 := 1;

for i := 1 to n1+n2 do

if i1>n1

then

begin

C[i] := B[i2];

i2 := i2+1;

end

else

if i2>n2

then

begin

C[i] := A[i1];

i1 := i1+1;

end

else

if A[i1]<=B[i2]

then

begin

C[i] := A[i1];

i1 := i1+1;

end

else

begin

C[i] := B[i2];

i2 := i2+1;

end;

. . .

Задача. Составьте программу, реализующую рассмотренный метод. Дополните ее комментариями.