Cтраница 1
Нисходящая сортировка слиянием аналогична принципу угфавдсния сверху вниз-в рамках которого руководитель организует работы тиким образом, что получив большую задачу, он ра биьй г ее на ползадачи, которые подмены независимо решать его подчиненные. Если каждый руководитель Г5удет решать Сйою адддчу, разбивая ее на две равные части с последующим объединением решений, полученных ею подчиненными н последующей ЕЕСрслачей результата своему начальству, то примерна также организован и сортировка слияние - РаГюта нел чско продвинется, аюка кто-то, кто не имеет в своем подчинении иссю ь нитслей, не получит и не выполнит соою з шачу ( н рассматриваемом случае это слияние лву файлов размером I); однако руководство выполняет значительную часть работыh соединяя рс ультять. [1]
Нисходящая сортировка слиянием аналогична принципу управления сверху вниз, в рамках которого руководитель организует работы таким образом, что получив большую задачу, он разбивает ее на подзадачи, которые должны независимо решать его подчиненные. Если каждый руководитель будет решать свою задачу, разбивая ее на две равные части с последующим объединением решений, полученных его подчиненными и последующей передачей результата своему начальству, то примерно также организована сортировка слиянием. Работа недалеко продвинется, пока кто-то, кто не имеет в своем подчинении исполнителей, не получит и не выполнит свою задачу ( в рассматриваемом случае это слияние двух файлов размером 1); однако руководство выполняет значительную часть работы, соединяя результаты работы подчиненных в единое целое. [2]
Удалите рекурсию из нисходящей сортировки слиянием, чтобы получить нерекурсивную сортировку слиянием, которая выполняет ту же последовательность слияний. [3]
Сортировка Бэтчера представляет собой в точности нисходящую сортировку слиянием, описанную в разделе 8.3; различие состоит лишь в том, что вместо одной из адаптивных реализаций слияний из главы 8 она использует нечетно-четное слияние Бэтчера, представляющее собой неадаптивное нисходящее рекурсивное слияние. Программа 8.3 сама по себе вообще не выполняет доступа к данным, так что из факта использования нами неадаптивного слияния следует, что и сама сортировка неадаптивная. [4]
Имея в своем распоряжении такую функцию слияния, легко получить рекурсивную нисходящую сортировку слиянием списков. Программа 8.7 является прямой рекурсивной реализацией функции, которая принимает в качестве входного параметра указатель на неупорядоченный список и возвращает указатель на список, содержащий те же элементы в отсортированном порядке. Эта программа выполняет свою работу, переупорядочивая узлы списка - память не резервируется ни для временных узлов, ни для списков. Для нахождения середины списка программа 8.7 использует следующий прием: разные реализации могут делать это либо передавая длину списка как параметр в рекурсивную программу, либо сохраняя длину в самом списке. Такая программа в рекурсивной формулировке проста для понимания, даже если реализует достаточно сложный алгоритм. [5]
Написать программу восходящей сортировки слиянием, которая выполняет те же слияния, что и нисходящая сортировка слиянием. [6]
Эта лемма не имеет особого значения для пирамидальной сортировки, поскольку основная доля времени ее выполнения все еще приходится на vVlogW - время, затрачиваемое на выполнение нисходящей сортировки, однако оно играет важную роль в тех приложениях очередей по приоритетам, в которых операция создать ( construct) приводит к алгоритму, обеспечивающему линейную зависимость времени выполнения. [7]
Используя программу 9.5 в программе 9.6 непосредственно для перемещения по массиву слева направо, применим функцию fixUp с тем, чтобы элементы, располагающиеся слева от указателя просмотра, образовывали пирамидально упорядоченное полное дерево. Затем, во время выполнения процесса нисходящей сортировки мы помещаем наибольший элемент на то место, которое освобождается по мере уменьшения размеров сортирующего дерева. Иначе говоря, процесс нисходящей сортировки подобен сортировке выбором, однако при этом он пользуется более эффективным методом обнаружения наибольшего элемента в неотсортированной части массива. [8]
Восходящая сортировка слиянием соответствует прохождению дерева типа разделяй и властвуй в порядке уровней, снизу вверх. В противоположность этому, мы обращались к рекурсивному алгоритму как к нисходящей сортировке слиянием, поскольку при обратном порядке прохождения дерева просмотр начинается сверху и следует вниз по дереву. [9]
Исследованы другие способы дальнейшего улучшения пирамидальной сортировки. Одна из идей, развитая Флойдом, состоит в использовании того обстоятельства, что элемент, повторно вставляемый в процессе нисходящей сортировки, проделывает весь путь на нижний уровень, так что мы можем сэкономить время, затрачиваемое на проверку достижения таким элементом своей позиции, просто продвигая больший из двух потомков до тех пор, пока не будет достигнут нижний уровень с последующим продвижением вверх по сортирующему дереву в соответствующую позицию. Благодаря этой идее коэффициент сокращения числа выполняемых операций сравнения асимптотически стремится к 2 и принимает значение, близкое к IgjV. [10]
Восходящая сортировка слиянием ( слева) состоит из последовательности проходов по файлу, которые выполняют слияние отсортированных подфайлов до тех пор, пока не останется только один подфайл. Каждый элемент файла, за исключением разве что нескольких в самом конце, используется в каждом проходе. В противоположность этому, нисходящая сортировка слиянием ( справа) сортирует первую половину файла, прежде чем перейти ко второй половине ( в рекурсивном режиме), так что схемы выполнения обеих видов сортировки слиянием существенно различаются. [11]
Используя программу 9.5 в программе 9.6 непосредственно для перемещения по массиву слева направо, применим функцию fixUp с тем, чтобы элементы, располагающиеся слева от указателя просмотра, образовывали пирамидально упорядоченное полное дерево. Затем, во время выполнения процесса нисходящей сортировки мы помещаем наибольший элемент на то место, которое освобождается по мере уменьшения размеров сортирующего дерева. Иначе говоря, процесс нисходящей сортировки подобен сортировке выбором, однако при этом он пользуется более эффективным методом обнаружения наибольшего элемента в неотсортированной части массива. [12]
Время выполнения пирамидальной сортировки не слишком чувствительно к природе входных данных. Независимо от того, какие значения принимают входные величины, наибольший элемент обнаруживается за число шагов, меньшее IgN. Вторая диаграмма сверху демонстрирует сортирующее дерево, построенное с помощью восходящего алгоритма, остальные диаграммы отображают для каждого файла процесс нисходящей сортировки. Вначале сортирующие деревья отображают в какой-то степени исходный файл, но по мере продвижения процесса сортировки они все больше напоминают сортирующие деревья, полученные для файла с произвольной организацией. [13]