Студопедия — Сортировка фон Неймана (слиянием)
Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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






Заданы два упорядоченных по возрастанию элементов одномерных массива: а размерности 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

 







Дата добавления: 2015-09-07; просмотров: 813. Нарушение авторских прав; Мы поможем в написании вашей работы!



Функция спроса населения на данный товар Функция спроса населения на данный товар: Qd=7-Р. Функция предложения: Qs= -5+2Р,где...

Аальтернативная стоимость. Кривая производственных возможностей В экономике Буридании есть 100 ед. труда с производительностью 4 м ткани или 2 кг мяса...

Вычисление основной дактилоскопической формулы Вычислением основной дактоформулы обычно занимается следователь. Для этого все десять пальцев разбиваются на пять пар...

Расчетные и графические задания Равновесный объем - это объем, определяемый равенством спроса и предложения...

Что такое пропорции? Это соотношение частей целого между собой. Что может являться частями в образе или в луке...

Растягивание костей и хрящей. Данные способы применимы в случае закрытых зон роста. Врачи-хирурги выяснили...

ФАКТОРЫ, ВЛИЯЮЩИЕ НА ИЗНОС ДЕТАЛЕЙ, И МЕТОДЫ СНИЖЕНИИ СКОРОСТИ ИЗНАШИВАНИЯ Кроме названных причин разрушений и износов, знание которых можно использовать в системе технического обслуживания и ремонта машин для повышения их долговечности, немаловажное значение имеют знания о причинах разрушения деталей в результате старения...

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

Виды сухожильных швов После выделения культи сухожилия и эвакуации гематомы приступают к восстановлению целостности сухожилия...

КОНСТРУКЦИЯ КОЛЕСНОЙ ПАРЫ ВАГОНА Тип колёсной пары определяется типом оси и диаметром колес. Согласно ГОСТ 4835-2006* устанавливаются типы колесных пар для грузовых вагонов с осями РУ1Ш и РВ2Ш и колесами диаметром по кругу катания 957 мм. Номинальный диаметр колеса – 950 мм...

Studopedia.info - Студопедия - 2014-2024 год . (0.008 сек.) русская версия | украинская версия