Читайте также:
|
Как было показано на примере быстрой сортировки, можно усовершенствовать большую часть рекурсивных алгоритмов, применяя для файлов небольших размеров другие методы, отличные от основного. Такой подход с использованием сортировки простыми вставками может уменьшить время работы алгоритма на 10 – 15 процентов.
В качестве следующего усовершенствования целесообразно свести к нулю время копирования данных во вспомогательный массив. Для этого следует так организовать рекурсивные вызовы, чтобы процесс вычисления сам менял в нужный момент роли входного и вспомогательного массивов на каждом уровне. Один из способов реализации данного подхода заключается в создании двух вариантов программ – одного для приема входных данных в файл RES и пересылке выходных данных в файл WORK, а другого – для приема входных данных в файл WORK и пересылке выходных данных в файл RES. После чего обе версии попеременно меняют друг друга.
Данный метод позволяет избежать копирования массива за счёт включённой во внутренний цикл дополнительной проверки, позволяющей попеременно сливать массивы то в порядке возрастания, то в порядке убывания. Это позволяет получить битонную последовательность и организовать процесс так, что внутреннему циклу слияния никогда не понадобятся служебные метки.
Экспериментальные результаты показывают, что сочетание всех предложенных выше усовершенствований ускоряют сортировку слиянием примерно на 40 процентов. Однако она, всё равно, на 25 процентов медленнее, чем быстрая сортировка. Эти показатели, конечно же, зависят от свойств компьютера.
Дата добавления: 2015-08-17; просмотров: 64 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Листинг 1 Абстрактное обменное слияние | | | Восходящая сортировка слиянием |