![]() |
| ||||||||||||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||||||||||||
О проекте
|
Тема: Сортировка методом слияний.Определение. Целочисленный массив с расположенными по неубыванию или по невозрастанию значениями элементов называется упорядоченным. Использование упорядоченности позволяет создавать эффективные алгоритмы для решения многих интересных задач. Задача слияния двух входных упорядоченных массивов А и В состоит в формировании упорядоченного выходного массива С, содержащего все элементы из входных массивов. Рассмотрим алгоритм слияния для упорядоченных по неубыванию массивов. Вначале элемент А[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 элементов.
Задача. Составьте программу, реализующую рассмотренный метод. Дополните ее комментариями. Рекурсивная сортировка слиянием (для любопытных)Задача. Напишите программу, содержащую алгоритм слияния в процедуре Sort(A, B, b1, e1, e2). Алгоритм должен копировать со слиянием два упорядоченные куска из массива А с номерами от b1 до e1 и от e1+1 до e2 соответственно в массив В с номерами элементов от b1 до e2. Предположив, что Вы правильно выполнили предыдущую задачу, алгоритм сортировки можно определить очень просто:
Рассмотрите процедуру сортировки слиянием. На вход процедуры сортировки поступает неупорядоченный кусок массива А с номерами элементов от b до e, на выходе - тот же кусок, но упорядоченный. Массив С - вспомогательный.
| ||||||||||||||||||||||||||||||||||||||
Проект «Pascaler» лучший на ХI Всероссийской конференции молодых исследователей с международным участием «Шаг в будущее», Россия, Москва, 12 – 16 апреля 2004г.
|