Упражнения

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

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

8.35. Добавить в программу 8.7 отсечение подфайлов малых размеров. Определить пределы, в рамках которых правильный выбор размеров отсекаемых файлов ускоряет действие полученной программы.

о 8.36. Реализовать восходящую сортировку слиянием применительно к циклическому связному списку, описание которого содержится в тексте.

8.37. Добавить отсечение подфайлов малых размеров в восходящую сортировку слиянием связных списков из упражнения 8.36. Определить пределы, в рамках которых правильный выбор размеров отсекаемых файлов ускоряет действие полученной программы.

8.38. Добавить в программу 8.7 отсечение подфайлов малых размеров. Определить пределы, в рамках которых правильный выбор размеров отсекаемых файлов ускоряет действие полученной программы.

о 8.39. Нарисовать дерево типа объединяй и властвуй , которое отображает слияния, которые выполняет программа 8.8 для jV= 16, 24, 31, 32, 33 и 39.

8.40. Нарисовать дерево типа объединяй и властвуй , которое подводит итог слияниям, выполняемым сортировкой слиянием на циклическом списке (упражнение 8.38) для N= 16, 24, 31, 32, 33 и 39.

8.41. Выполнить эмпирические исследования с целью выдвижения гипотезы, касающейся числа упорядоченных подфайлов в массиве из N случайных 32-разрядных целых чисел.

8.42. Определить эмпирическим путем количество проходов, необходимых для выполнения естественной сортировки слиянием случайных 64-разрядных ключей при N = 10, 10 , 10 и 10. Совет: чтобы выполнить это упражнение, не обязательно пользоваться сортировкой (и даже не нужно генерировать полные 64-разрядные ключи).

8.43. Преобразовать программу 8.8 в процедуру естественной сортировки слиянием, предварительно заполнив очередь упорядоченными подфайлами, которые содержатся во входном файле.

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

8.8. Возврат к рекурсии

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

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

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

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

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

индуктивному доказательству устойчивости. Что касается реализации быстрой сортировки, ориентированной на массивы, то простого способа устойчивого разбиения файлов не видно, так что возможность положительного решения проблемы устойчивости исключается еше до того, как рекурсия вступит в дело. Тем не менее, прямолинейная реализация быстрой сортировки применительно к связным спискам является устойчивой (см. упражнение 7.4).

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

Упражнения

8.45. Предположим, что сортировка слиянием реализована таким образом, что дробление файла осуществляется в произвольной точке, а не точно в середине файла. Сколько операций сравнения выполняются в среднем по этому методу для сортировки N элементов?

8.46. Провести анализ эффективности сортировки слиянием при сортировке строк. Сколько в среднем нужно выполнить операций сравнения символов при сортировке файлов больших размеров?

8.47. Провести эмпирические исследования с целью сравнения эффективности быстрой сортировки связных списков (см. упражнение 7.4) и нисходящей сортировки слиянием связных списков (программа 8.7).