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

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

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

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

БЛОК – СХЕМА

I = 1 J = 1 K = 1

Æ 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

 

 

rem confluence

const n = 10

const m = 20

const l = n + m

dim x%(1 to n)

dim y%(1 to m)

dim z%(1 to l)

defint k, i, j

for i = 1 to n

input x(i) ‘формирование первого упорядоченного массива

next

for i = 1 to m

input y(i) ‘формирование второго упорядоченного массива

next

I= 1: j=1: l=1 ‘i-индекс первого массива, j-индекс второго массива, l-индекс ‘результирующего массива

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

if x(i) < y(i) then ‘переписываем элементы из первого массивa

z(k) = x(i)

i = i + 1: k = k + 1

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

z(k) = y(j)

j = j + 1: k = k + 1

wend

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

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

Z(k) = x(i): i = i + 1: k = k+1

wend

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

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

Z(k) = y(j): j = j + 1: k = k+ 1

wend

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

print z(i):: next ‘полученного слиянием

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

0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9