40

6. Сортировка последовательных файлов

Вид занятия – лабораторная работа Цель – исследование особенностей сортировки последовательностей

Продолжительность – 4 часа

Все рассмотренные в предыдущих лабораторных работах сортировки неприменимы, если сортируемые данные не помещаются в оперативной памяти и находятся на внешнем запоминающем устройстве с последовательным доступом. В таком случае основной метод сортировки основан на идее слияния.

Слияние обозначает объединение двух (или более) упорядоченных последовательностей в одну упорядоченную последовательность при помощи циклического выбора элементов доступных в данный момент.

Сортировка простым слиянием

Идея метода сортировки простым слиянием заключается в следующем:

1.Последовательность A разбивается на две половины B и C;

2.Последовательности B и C сливаются при помощи объединения отдельных элементов в упорядоченные пары;

3.Полученной последовательности присваивается имя A и шаги 1 и 2 повторяются, но на этот раз упорядоченные пары сливаются в упорядоченные четвёрки;

4.Предыдущие шаги повторяются: четвёрки сливаются в восьмёрки и весь процесс продолжается пока не будет упорядочена вся последовательность (ведь длины слагаемых последовательностей всегда удваиваются).

Изложенная идея представлена на рисунке 6.1.

Рисунок 6.1. – Процесс разделения и слияния файлов

41

Чтобы получить ответ на вопрос: “Каким образом сливать упорядоченные 4-ки, 8-ки, и т.п.?” следует изучить рисунок 6.2.

Для слияния двух последовательностей мы производим сравнение первых элементов файлов B и С. Наименьший элемент следует в файл A, и процесс повторяется вновь до тех пор, пока упорядоченные четвёрки не превратятся в упорядоченные восьмёрки.

Рисунок 6.2. – Слияние двух последовательностей

Сортировка простым слиянием достаточно эффективна. Общее число] пересылок осуществляемых при полной сортировке файла равно M = N [Log 2 N . Число сравнений C по значению ещё меньше, т.к. при копировании остатка последовательности сравнения не производятся.

Хотя показатели сортировки слияния схожи с показателями производительности пирамидальной сортировки, но сортировка слиянием требует вдвое больше памяти (2*N), что затрудняет её использование для больших массивов данных расположенных в ОЗУ.

Естественное слияние

В случае простого слияния мы ничего не выигрываем, если данные уже частично рассортированы. На k-м проходе длина всех рассортированных последовательностей уже меньше или равна 2k и их уже можно объединять.

Метод сортировки, при котором каждый раз сливаются две самые длинные упорядоченные подпоследователь-

ности называется естественным слиянием.

Пусть исходная последовательность элементов задана в виде файла A. Кроме того, у нас имеется два вспомогательных файла B и C. Каждый проход алгоритма состоит из:

-Фазы распределения, которая распределяет серии из A в B и C.

-Фазы слияния, которая сливает серии из B и C в A.

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

42

Рисунок 6.3. – Демонстрация алгоритма естественного слияния

Задание

Сформируйте типизированный файл произвольной размерности, хранящий целые случайные числа. Разработайте две функции, позволяющие упорядочить исходный файл с использованием метода сортировки простым слиянием и сортировки естественным слиянием.