Стр. 97 - Основы алгоритмов и структур данных

Содержание 95
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
Вместо двух файлов, можно легко использовать один массив, если
рассматривать его как последовательность с двумя концами. Вместо того,
чтобы сливать элементы из двух исходных файлов, мы можем брать их с двух
концов массива. Таким образом, общий вид объединенной фазы слияния-
разбиения можно изобразить, как показано на рис. 74. Направление пересылки
сливаемых элементов меняется (переключается) после каждой упорядоченной
пары на первом проходе, после каждой упорядоченной четверки на втором
проходе и т. д.; таким образом, равномерно заполняются две выходные
последовательности, представленные двумя концами одного массива
(выходного). После каждого прохода два массива меняются ролями: входной
становится выходным, и наоборот.
входной массив выходной массив
слияние разбиение
i j k l
Рис. 75. Сортировка двух массивов методом простого слияния
Программу можно еще больше упростить, объединив два концептуально
различных массива в один массив двойной длины.
Пусть индексы i и j указывают два исходных элемента, тогда как k и l
обозначают два места пересылки (см. рис. 74). Исходные данные — это,
элементы a1 ,..., аn. Очевидно, что нужна булевская переменная up для указания
направления пересылки данных; up = true будет означать, что на текущем
проходе компоненты a1,..., аn будут пересылаться “вверх” — в переменные
an+1,..., а2n , тогда как up – false будет указывать, что an+1,..., а2 n должны
переписываться “вниз” — в a1 ,..., аn . Значение up строго чередуется между
двумя последовательными проходами. И, наконец, вводится переменная р для
обозначения длины сливаемых подпоследовательностей (р-наборов). Ее
начальное значение равно 1, и оно удваивается перед каждым очередным
проходом. Для простоты мы будем считать, что n — всегда степень двойки.
Таким образом, программа простого слияния имеет вид