Схема алгоритма сортировки слиянием

Государственное образовательное учреждение среднего профессионального образования

ВОРКУТИНСКИЙ ГОРНО-ЭКОНОМИЧЕСКИЙ КОЛЛЕДЖ

РАССМОТРЕНО УТВЕРЖДАЮ:

На заседании цикловой комиссии Зам. директора по УВР

«___»_____________2008 г. ______________З.Г. Штокалюк

Председатель цикловой комиссии «___»___________2008 г.

____________ О.В. Гармаш

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

к лабораторной работе № 20

Тема:

«Сортировка файлов слиянием»

Дисциплина: «Программирование на языке высокого уровня»

для студентов специальности 230101

Разработал преподаватель Баев А.В.

2008 г.

Лабораторная работа №20

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

Цель работы:

1. Получить навыки разработки программ сортировки файлов слиянием.

Краткие сведения из теории

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

Рассмотрим алгоритм сортировки слиянием на примере слияния двух предварительно упорядоченных массивов Х и Y в один массив Z. Данные в массивах расположены в порядке возрастания их значений.

Обозначим через переменные dx, dy - длину (размер) массивов X, Y соответственно. Переменные ix, iy - счетчики (адреса) тех же массивов. Переменная iz - счетчик числа элементов нового массива Z.

Схема алгоритма сортировки слиянием