Сортировка фон Неймана (слиянием)

Дата добавления: 2015-07-23; просмотров: 2937; Нарушение авторских прав

Заданы два упорядоченных по возрастанию элементов одномерных массива: а размерности n и b размерности m. Требуется получить третий массив с размерности n+m, который содержал бы все элементы исходных массивов, упорядоченных по возрастанию.

Алгоритм решения этой задачи известен как «сортировка фон Неймана» или сортировка слиянием. Идея алгоритма состоит в следующем. Сначала анализируются первые элементы обоих массивов. Меньший элемент переписывается в новый массив. Оставшийся элемент последовательно сравнивается с элементами из другого массива. В новый массив после каждого сравнения попадает меньший элемент. Процесс продолжается до исчерпания элементов одного из массивов. Затем остаток другого массива дописывается в новый массив. Полученный новый массив упорядочен таким же образом, как исходные.

Программа, реализующая метод Фон-Неймана, имеет следующий вид:

БЛОК – СХЕМА

I = 1 J = 1 K = 1

Æ 1

1 Æ

1 Æ

[(K)=A(I)] I = I+1 K = K+1

[(K)=B(J)] J = J+1 K = K+1

K=N+M+1

[(K)=B(J)] J = J+1 K = K+1

[(K)=A(I)] I = I+1 K = K+1

program confluence;

const n = 10;

m = 20;

l = n + m;

var x: array [1..n] of integer;

y: array [1..m] of integer;

z: array [1..l] of integer;

k, i, j: integer;

begin

for i: = 1 to n do

read (x[i]); {формирование первого упорядоченного массива}

for i: = 1 to m do

read (y[i]); {формирование второго упорядоченного массива}

I:= 1; j:=1; l:=1 {i-индекс первого массива, j-индекс второго

массива, l-индекс результирующего массива}

while (i<=n) and (j<=m) do {пока не закончились элементы в одном из массивов}

if x[i] < y[i] then {переписываем элементы из первого массива}

begin

z[k]: = x[i];

i: = i + 1; k: = k + 1;

end

else {переписываем элемент из второго массива}

begin

z[k]: = y[j];

j: = j + 1; k: = k + 1;

end;

while i < = n do {если не закончились элементы в первом массиве,}

begin {переписываем их в результирующий массив}

z[k]: = x[i]; i: = i + 1; k: = k+1;

end;

while j < = m do {если не закончились элементы во втором массиве}

begin {переписываем их в результирующий массив}

z[k]: = y[j]; j: = j + 1; k: = k+ 1;

end;

for i: = 1 to l do {вывод на экран упорядоченного массива,}

writeln (z[i]); {полученного слиянием}

End.

Результаты работы:

<== предыдущая лекция	\|	следующая лекция ==>
Сортировка обменом («пузырьковая сортировка»)	\|	Описание двумерных массивов.