Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 35
Текст из файла (страница 35)
Это означает, что алгоритмы пирамидальной сортировки и сортировки слиянием являются асимптотически оптимальными. Далее в главе 8 показано, что нижнюю границу й (и 18п) можно превзойти, если информацию о порядке расположения входных элементов можно получить методами, отличными от попарного сравнения. Например, в алгоритме сортировки, работающем по методу перечисления, предполагается, что входные данные образуют множество чисел 10, 1, 2,..., к). Используя в качестве инструмента для определения относительного порядка элементов массива механизм индексации, алгоритм сортировки перечислением может выполнить сортировку п чисел за время 9 (п+ Е). Таким образом, если 1с = 0 (и), то время работы этого алгоритма линейно зависит от размера входного массива.
Родственный алгоритм поразрядной сортировки может быть использован для расширения области применения сортировки перечислением. Если нужно выполнить сортировку и д-значных чисел, где каждая цифра может принимать до Й возможных значений, то алгоритм поразрядной сортировки справится с этой задачей за время 9(И(п+ й)). Если Н вЂ” константа, а величина й ведет себя как 0 (и), то время выполнения этого алгоритма линейно зависит от размера входного массива. Для применения третьего алгоритма, алгоритма блочной сортировки, необходимы знания о распределении чисел во входном массиве.
Этот алгоритм позволяет выполнить сортировку п равномерно распределенных на полуоткрытом интервале 10,1) чисел в среднем за время 0(п). Часть!1. Сортировка и порядковая статистика 177 Порядковая статистика В множестве, состоящем из п чисел, г-й порядковой статистикой называется г-е по величине значение в порядке возрастания. Конечно же, г-ю порядковую статистику можно выбрать путем сортировки входных элементов и индексирования ю'-го значения в выходных данных. Если не делается никаких предположений о распределении входных элементов, время работы данного метода равно 11 (п 1к п), как следует из величины нижней границы, найденной в главе 8.
В главе 9 будет показано, что тчй по величине (в порядке возрастания) элемент можно найти за время О(п), что справедливо даже для случая произвольных действительных чисел. Мы покажем в этой главе алгоритм с компактным псевдокодом, время работы которого в наихудшем случае равно О (пз), а в среднем линейно возрастает с увеличением количества входных элементов. Там же описан и более сложный алгоритм, время работы которого даже в наихудшем случае равно О (и). Теоретическая подготовка В основном в этой части не используется сложная математика, однако для освоения некоторых разделов требуется знание определенных разделов математики.
В частности, при анализе алгоритмов быстрой сортировки, блочной сортировки и алгоритма порядковой статистики используются некоторые положения теории вероятности, рассмотренные в приложении В, а также материал по вероятностному анализу и рандомизированным алгоритмам из главы 5. Анализ алгоритма порядковой статистики в наихудшем случае содержит более сложные математические выкладки, чем используемые при анализе других рассмотренных в этой части алгоритмов. ГЛАВА 6 Пирамидальная сортировка В этой главе описывается еще один алгоритм сортировки, а именно — пирамидальная сортировка. Время работы этого алгоритма, как и время работы алгоритма сортировки слиянием (и в отличие от времени работы алгоритма сортировки вставкой), равно 0(п!йп). Как и сортировка методом вставок, и в отличие от сортировки слиянием, пирамидальная сортировка выполняется без привлечения дополнительной памяти: в любой момент времени требуется память для хранения вне массива только некоторого постоянного количества элементов.
Таким образом, в пирамидальной сортировке сочетаются лучшие особенности двух рассмотренных ранее алгоритмов сортировки. В ходе рассмотрения пирамидальной сортировки мы также познакомимся с еще одним методом разработки алгоритмов, а именно — использованием специализированных структур данных для управления информацией в ходе выполнения алгоритма. В рассматриваемом случае такая структура данных называется "пирамидой" (оеар) и может оказаться полезной не только при пирамидальной сортировке, но и при создании эффективной очереди с приоритетами.
В последующих главах эта структура данных появится снова. Изначально термин ")зеар" использовался в контексте пирамидальной сортировки (леарзоп), но в последнее время его основной смысл изменился, и он стал обозначать память со сборкой мусора, в частности, в языках программирования 11зр и 5ача (и переводиться как "куча"). Однако в данной книге термину пеар (который здесь переводится как "пирамида'*) возвращен его первоначальный смысл.
Глава 6. Пирамидальная сортировка 179 6.1 Пирамиды Пирамида (Ьшагу 1зеар) — это структура данных, представляющая собой объект-массив, который можно рассматривать как почти полное бинарное дерево (см. раздел 5.3 приложения Б, а также рис.
6.1). Каждый узел этого дерева соответствует определенному элементу массива. На всех уровнях, кроме, может быль, последнего, дерево полностью заполнено (заполненный уровень — это такой, который содержит максимально возможное количество узлов). Последний уровень заполняется слева направо до тех пор, пока в массиве не закончатся элементы.
Представляющий пирамиду массив А является объектом с двумя атрибутами: 1епдаЬ [А], т.е. количество элементов массива, и Ьеар э!яе [А], т.е. количество элементов пирамиды, содержащихся в массиве А. Другими словами, несмотря на то, что в массиве А [1.. 1епдгЬ [А]] все элементы могут быть корректными числами, ни один из элементов, следующих после элемента А [Ьеар вые [А]], где Ьеар згяе [А] < 1еид!Ь [А], не является элементом пирамиды. В корне дерева находится элемент А [1], а дальше оно строится по следующему принципу: если какому-то узлу соответствует индекс г, то индекс его родительского узла вычисляется с помощью представленной ниже процедуры РАкент(г), индекс левого дочернего узла — с помощью процедуры 1.ЕЕТ(1), а индекс правого дочернего узла — с помощью процедуры К!СНТ(1): РАкент(г) ге!игл [г/2] 1.ЕЕТ(1) ге!игл 21 К!сит(1) ге!пгп 2г'+ 1 В пирамиде, представленной на рис.
6.1, число в окружности, представляющей каждый узел дерева, является значением, сортируемым в данном узле. Число над узлом — это соответствующий индекс массива. Линии, попарно соединяющие элементы массива, обозначают взаимосвязь вида "родитель-потомок". Родительские элементы всегда расположены слева от дочерних. Данное дерево имеет высоту, равную 3; узел с индексом 4 (и значением 8) расположен на первом уровне. На большинстве компьютеров операция 21 в процедуре 1.ЕЕТ выполняется при помощи одной команды процессора путем побитового сдвига числа! на один бит влево.
Операция 21+ 1 в процедуре Кгцнт тоже выполняется очень быстро — достаточно биты двоичного представления числа ! сдвинуть на одну позицию влево, а затем младший бит установить равным 1. Процедура РАке!чт выполняется путем сдвига числа 1 на один бит вправо. При реализации пирамидальной сортировки эти функции часто представляются в виде макросов или встраиваемых процедур. Часть й. Сортировка и порядковая статистика 180 Рнс. 6.1.
Пирамида, представленная в виде а) бинарного дерева и б) массива Различают два вида бинарных пирамид: неубывающие и невозрастающие. В пирамидах обоих видов значения, расположенные в узлах, удовлетворяют свойству пирамиды (Беар ргореггу), являющемуся отличительной чертой пирамиды того или иного вида. Свойство невозрастающих пирамид (шах-Ьеар ргореггу) заключается в том, что для каждого отличного от корневого узла с индексом 1 выполняется следующее неравенство: А [РАкннт (1)] > А [1] . Другими словами, значение узла не превышает значение родительского по отношению к нему узла.
Таким образом, в невозрастающей пирамиде самый большой элемент находится в корне дерева, а значения узлов поддерева, берущего начало в каком-то элементе, не превышают значения самого этого элемента. Принцип организации неубывающей пирамиды (пип-Ьеар) прямо противоположный. Свойство неубывающих пирамид (пил-леар ргореггу) заключается в том, что для всех отличных от корневого узлов с индексом 1 выполняется такое неравенство: А [РАвннт (1)] < А [1] . Таким образом, наименьший элемент такой пирамиды находится в ее корне. В алгоритме пирамидальной сортировки используются невозрастающие пирамиды. Неубывающие пирамиды часто применяются в приоритетных очередях (этот вопрос обсуждается в разделе 6.5). Для каждого приложения будет указано, с пирамидами какого вида мы будем иметь дело — с неубывающими или невозрастающими. При описании свойств как неубывающих, так и невозрастающих пирамид будет использоваться общий термин "пирамида".
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
