8.4. Усовершенствования базового алгоритма

Как уже было видно на примере быстрой сортировки, можно усовершенствовать большую часть рекурсивных алгоритмов, применяя для обработки файлов небольших размеров другие методы, отличные от основного. Рекурсия гарантирует, что эти методы будут использоваться для случаев небольших файлов, так что более совершенная обработка файлов небольших размеров приводит к тому, что улучшается и весь алгоритм. Следовательно, как это имело место и для случая быстрой сортировки, переключение на сортировку вставками подфайлов небольших размеров приводит к уменьшению времени выполнения типовой реализации операции сортировки слиянием от 10 до 15 процентов.

В качестве следующего усовершенствования целесообразно рассмотреть возможность сведения к нулю времени копирования данных во вспомогательный массив, используемый процедурой слияния. Поступая таким образом, следует так организовать рекурсивные вызовы, что процесс вычисления сам меняет в нужный момент роли входного и вспомогательного массивов на каждом уровне. Один из способов реализации такого подхода заключается в создании двух вариантов программ - одного для приема входных данных в файл а и пересылки выходных данных в файл aux, а другого для приема входных данных в файл aux и пересылки выходных данных в файл а, после чего обе версии поочердно вызывают одна другую. Другой подход продемонстрирован в программе 8.4, которая вначале создает копию входного массива, а затем использует программу 8.1 и переключает аргументы в рекурсивных вызовах с целью отказа от явно заданной процедуры копирования массива. Вместо нее путем поочередных переключений результат слияний помещается то во вспомогательный, то во входной файл. (Это достаточно хитроумная программа.)

Данный метод позволяет избежать копирования массива ценой включения во внутренний цикл проверки с целью определения, когда входные файлы будут исчерпаны. (Напоминаем, что предложенный метод устранения подобного рода проверок в программе 8.2 предусматривает превращение этого файла в битонный на время копирования.) Эту потерю можно восполнить посредством реализации той же идеи: мы пишем программы как слияния, так и сортировки слиянием, одну для представления массива в порядке возрастания, а другую - для представления массива в порядке убывания. Вооружившись такой стратегией, можно снова обратиться к битон-ной стратегии и устроить так, что внутреннему циклу слияния никогда не понадобятся служебные метки.

Принимая во внимание тот факт, что такая супероптимизация использует четыре копии базовых программ и умопомрачительные рекурсивные переключения аргументов, она может быть рекомендована экспертам (или студентам!), но в то же время она существенно ускоряет сортировку слиянием. Экспериментальные результаты, которые будут обсуждаться в разделе 8.6, показывают, что сочетание всех предложенных выше усовершенствований ускоряют сортировку слиянием примерно на 40 процентов, однако сортировка слиянием все еще выполняется примерно на 25 процентов медленнее, чем быстрая сортировка. Эти показатели зависят от реализации и от машины, однако подобные результаты возможны в различных ситуациях.

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

Программа 8.4. Сортировка слиянием без копирования

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

template <class Item>

void mergesortABr (Item a[], Item b[], int 1, int r) { if (r-l <= 10) { insertion(a, 1, r) ; return; } int m = (l+r)/2; mergesortABr(b, a, 1, m); mergesortABr(b, a, m+1, r); mergeAB(a+l, b+1, m-1+1, b+m+1, r-m) ;

template <class Item>

void mergesortAB (Item a[], int 1, int r) { static Item aux[maxN] ;

for (int i = 1; i <= r; i++) aux[i] = a[i]; mergesortABr(a, aux, 1, r);

Упражнения

8.16. Реализовать абстрактное обменное слияние, использующее дополнительное пространство памяти, размер которого пропорционален размеру меньшего из файлов, подвергаемых слиянию. (Ваш метод должен наполовину уменьшать потребность в пространстве сортировки слиянием.)

8.17. Выполните сортировку слиянием крупного файла с произвольной организацией и эмпирическим путем определите длину другого подфайла на момент исчерпания первого подфайла как функцию от Л (сумма длин двух сливаемых подфайлов).

8.18. Предположим, что программа 8.3 модифицирована таким образом, что пропускает функцию merge, когда а[т] < а[т+1]. Сколько сравнений экономится в этом случае, если в файле, представленном к сортировке, уже установлен порядок, предусматриваемый данной сортировкой?

8.19. Выполните модифицированный алгоритм, предложенный в упражнении 8.18, для крупных файлов с произвольной организацией. Определите эмпирическим путем среднее число пропусков функции merge в зависимости от N (размер исходного файла, представленного к сортировке).

8.20. Предположим, что сортировка слиянием должна быть выполнена на Л-сор-тированном файле для небольшого значения Л. Какие изменения вы внесете в подпрограмму merge, чтобы воспользоваться преимуществами, предоставляемыми упомянутым свойством входных данных? Выполните эксперименты с гибридами сортировки методом Шелла и сортировки слиянием, основанными на этой подпрограмме.

8.21. Разработайте реализацию слияния, которое уменьшает потребность в дополнительном пространстве памяти до тах(М, N/Af), воспользовавшись следующей идеей. Разбейте массив на N/M блоков размером М (для простоты предположим, что Л кратно М). Затем, (/) рассматривая эти блоки как записи, первые ключи которых суть сортировочные ключи, отсортировать их, используя для этой цели сортировку выбором, и (ii) выполнить проход по массиву, выполняя слияние первого блока со вторым, затем второго блока с третьим и так далее.

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

8.23. Реализовать битонную сортировку слиянием без копирования,

8.5. Восходящая сортировка слиянием

Как отмечалось в главе 5, у каждой рекурсивной программы имеется нерекурсивный аналог, который хотя и выполняет эквивалентные вычисления, тем не менее, он делает это по-другому. Будучи прототипами теории разработки алгоритмов по принципу разделяй и властвуй , нерекурсивные реализации сортировки слиянием заслуживают детального изучения.

Рассмотрим последовательность слияний, выполняемую рекурсивным алгоритмом. В примере, представленном на рис. 8,2, видно, что файл размером 15 сортируется в виде следующей последовательности слияний:

1-С-1 1-С-1 2-С-2 1-С-1 1-С-1 2-С-2 4-с-4 1-С-1 1-С-1 2-С-2 1-С-1 2-С-1 4-с-З 8-С-7,

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

1-С-1 1-С-1 1-С-1 1-С-1 1-С-1 1-С-1 1-С-1

2-С-2 2-С-2 2-С-2 2-с-1 4-с-4 4-с-З 8-С-7.

Последовательность слияний, выполняемая рекурсивным алгоритмом, определяется деревом типа разделяй и властвуй , показанным на рис. 8.3: мы просто проходим по дереву в обратном порядке. Как было показано в главе 3, можно разработать нерекурсивный алгоритм, использующий явно определяемый стек, который даст ту же последовательность слияний. Однако нет необходимости ограничиваться только