Занятие 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 и действия с массивами.

 

i i1 i2 Сравниваются C[i]
A[1]=5 и B[1]=7 A[2]=13 и B[1]=7 A[2]=13 и B[2]=9 A[2]=13 и B[3]=10 A[2]=13 и B[4]=12 В весь переписан В весь переписан

Рассмотрите фрагмент решения задачи на слияние двух массивов А и В, которые содержат соответственно 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;

. . .

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








Дата добавления: 2015-05-16; просмотров: 794; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию, введите в поисковое поле ключевые слова и изучайте нужную вам информацию.

Поделитесь с друзьями:

Если вам понравился данный ресурс вы можете рассказать о нем друзьям. Сделать это можно через соц. кнопки выше.
helpiks.org - Хелпикс.Орг - 2014-2021 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.008 сек.