Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 39
Текст из файла (страница 39)
Пирамидальная сортировка 197 последовательность. Такая ситуация встречается во многих важных приложениях, например, в алгоритме поиска кратчайшего пути Дейкстры (01)кмга), который рассматривается в главе 24, и при моделировании дискретных событий. Для алгоритма Дейкстры особенно важна эффективность операции Пнскназн Кку. Для частного случая монотонности для целочисленных данных из диапазона 1, 2, ..., С, Ахуйя (АЬп)а), Мельхорн (МеЬ1Ьогп), Орлин (Ог!1п) и Таржан (Таг)ан) [8) описали, как с помощью структуры данных под названием позиционная пирамида (гайх Ьеар) реализовать операции Ехтклст М[м и 1мзнкт со временем выполнения 0 (18 С) (более подробные сведения на эту тему можно найти в главе 17), и операцию 1)нскнлзн Кнт со временем выполнения 0 (1). Граница 0 (18 С) может быть улучшена до 0 [~48 С) путем совместного использования пирамид Фибоначчи (см.
главу 20) и позиционных пирамид. Дальнейшее улучшение этой границы до О (18'7з+' С) было осуществлено Черкасским (СЬегказзку), Гольдбергом (Оо!дЬег8) и Сильверстайном (811чегзге(п) [581, которые объединили многоуровневую группирующую структуру (пш1!1-1ече! иске!1п8 з!гпсшге) Денардо (1)елагино) и Фокса (Рох) [72) с уже упоминавшейся пирамидой Торупа. Раману (Кашап) [256! удалось еще больше улучшить эти результаты и получить границу, которая равна 0 (ппп ~18'~~+' С,!8~7~+'и)) для произвольной фиксированной величины е ) О. Более подробное обсуждение этих результатов можно найти в работах Рамана [256! и Торупа [299!.
ГЛАВА 7 Быстрая сортировка Быстрая сортировка — это алгоритм сортировки, время работы которого для входного массива из п чисел в наихудшем случае равно О (и"). Несмотря на такую медленную работу в наихудшем случае, этот алгоритм на практике зачастую оказывается оптимальным благодаря тому, что в среднем время его работы намного лучше: 9 (и 1я и). Кроме того, постоянные множители, не учтенные в выражении 9 (и 1я и), достаточно малы по величине.
Алгоритм обладает также тем преимуществом, что сортировка в нем выполняется без использования дополнительной памяти, поэтому он хорошо работает даже в средах с виртуальной памятью. В разделе 7.1 описан сам алгоритм и важная подпрограмма, использующаяся в нем. Поскольку поведение алгоритма быстрой сортировки достаточно сложное, мы начнем с нестрогого, интуитивного обсуждения производительности этого алгоритма в разделе 7.2, а строгий анализ отложим до конца данной главы. В разделе 7.3 представлена версия быстрой сортировки, в которой используется случайная выборка.
У этого алгоритма хорошее среднее время работы, при этом никакие конкретные входные данные не могут ухудшить его производительность до уровня наихудшего случая. Этот рандомизированный алгоритм анализируется в разделе 7.4, где показано, что время его работы в наихудшем случае равно Э (пз), а среднее время работы в предположении, что все элементы различны, составляет О (и 1я п). Глава 7. Быстрая сортировка 199 7.1 Описание быстрой сортировки Быстрая сортировка, подобно сортировке слиянием, основана на парадигме "разделяй и властвуй", представленной в разделе 2.3.1. Ниже описан процесс сортировки подмассива А [р..т), состоящий, как н все алгоритмы с использованием декомпозиции, из трех этапов.
Разделение. Массив А [р..т) разбивается (путем переупорядочения его элементов) на два (возможно, пустых) подмассива А [р..д — 1] н А [д+ 1..т). Каждый элемент подмассива А [р..д — 1] не превышает элемент АЦ, а каждый элемент подмасснва А [д + 1..т) не меньше элемента А[у]. Индекс д вычисляется в ходе процедуры разбиения. Покорение. Подмасснвы А [р..д — 1] и А [д + 1..т] сортируются путем рекурсивного вызова процедуры быстрой сортировки. Комбинирование.
Поскольку подмассивы сортируются на месте, для их объединения не нужны никакие действия: весь массив А [р..т) оказывается отсортирован. Алгоритм сортировки реализуется представленной ниже процедурой: ОО1СК8ОКт(А, р, т) 1 Ир<т 2 1йеп д — РАкт1т1ом(А, р, т) 3 Оо1скзокт(А, р, «1 — 1) 4 1 ИЛСК8ОКт(А, д+ 1, т) Чтобы выполнить сортировку всего массива А, вызов процедуры должен иметь вид Оо1скзокт(А, 1, 1елдг6 [А]).
Разбиение массива Ключевой частью рассматриваемого алгоритма сортировки является процедура Рлкт1т1ох, изменяющая порядок элементов подмассива А [р..т] без привлечения дополнительной памяти: РЛКт1т1ОМ(А, р, т) 1 х — А[т) 2 г — р — 1 3 1ог,1 — р 1о т — 1 4 бо И А[7'] < х 5 1йеп 1 — г+ 1 6 Обменять А[1) «-+ А[2] т Обменять А[1+ Ц + А[т) 8 ге1пгп г'+ 1 Часть П. Сортировка и порядковая статистика 200 Рис. 7.1. Пример действия иа массив процедуры Рлкт[тюн На рис. 7.1 приведен пример работы процедуры Рлкт~тюм с 8-элементным массивом. Эта процедура всегда выбирает элемент т = А [т] в качестве опорного (рпог) элемента.
Разбиение подмассива А [р..т] будет выполняться относительно этого элемента. В начале выполнения процедуры массив разделяется на четыре области (они могут быть пустыми). В начале каждой итерации цикла аког в строках 3-6 каждая область удовлетворяет определенным свойствам, которые можно сформулировать в виде следующего инварианта цикла. В начале каждой итерации цикла в строках 3-6 для любого индекса и массива справедливо следующее: 1) если р < Й < г, то А [Й] < х; 2) если г + 1 < и < з — 1, то А [/с] > х; 3) если к = г, то А [lс] = х. Соответствующая структура показана на рис.
7.2. Индексы между 7' и т — 1 не подпадают ни под один из трех перечисленных случаев, и значения соответствующих им элементов никак не связаны с опорным элементом к. Глава 7. Быстрая сортировка 201 Рис. 7.2. Четыре области, поддерживаемые процедурой Рлкт~тюи в подмассиве А )р..г); все элементы полмассива А)р.л) меньше либо равны х, все элементы подмассива А )1+ 1..З' — Ц больше х и А )г) = х, а все элементы подмассива А )1'..г — Ц могут иметь любые значения Перед тем как приступить к работе со сформулированным инвариантом цикла, давайте еще раз рассмотрим рис. 7.1. Светло-серым цветом обозначены элементы массива, которые попали в первую часть разбиения; значения всех этих элементов не превышают величину х.
Элементы темно-серого цвета образуют вторую часть массива; их величина больше х. Незакрашенные элементы — это те, что не попали ни в одну из первых двух частей; последний незакрашенный элемент является опорным. В части а рисунка показано начальное состояние массива и значения переменных. Ни один элемент не помещен ни в одну из первых двух частей.
В части б рисунка элемент со значением 2 "переставлен сам с собой" и помещен в ту часть, элементы которой не превышают х. В частях в и г элементы со значениями 8 и 7 добавлены во вторую часть массива (которая до этого момента была пустой). В части д элементы 1 и 8 поменялись местами, в результате чего количество элементов в первой части возросло. В части е меняются местами элементы 3 и 7, в результате чего количество элементов в первой части возрастает. В частях ж и з вторая часть увеличивается за счет включения в нее элементов 5 и 6, после чего цикл завершается. В части и, иллюстрирующей действие строк 7 и 8, опорный элемент меняется местами с тем, который находится на границе раздела двух областей. Теперь нам необходимо показать, что сформулированный выше инвариант цикла справедлив перед первой итерацией, что каждая итерация цикла сохраняет этот инвариант и что инвариант позволяет продемонстрировать корректность алгоритма по завершении цикла.
Инициализация. Перед первой итерацией цикла 1 = р — 1 и 7' = р. Между элементами с индексами р и г нет никаких элементов, как нет их и между элементами с индексами г + 1 и 3 — 1, поэтому первые два условия инварианта цикла выполняются. Присваивание, которое выполняется в строке 1 процедуры, приводит к тому, что становится справедливым третье условие. Сохранение. Как видно из рис. 7.3, нужно рассмотреть два случая, выбор одного из которых определяется проверкой в строке 4 алгоритма.
На рис. 7.3а показано, что происходит, если А )7] ) х; единственное действие, которое Глава 7. Быстрая сортировка 203 Упражнения 7.1-1. Используя в качестве модели рис. 7.1, проиллюстрируйте действие про- цедуры РАкт~тюх на массив А = (13, 19, 9, 5, 12, 8, 7, 4, 21, 2, 6, 11). 7.1-2. Какое значение 9 возвращает процедура РАкт1т1сяч, если все элементы массива А [р..г] одинаковы? Модифицируйте эту процедуру так, чтобы в случае, когда все элементы массива А (р..г] одинаковы, д определялось следующим образом: д = '1(р+ г)(2].
7.1-3. Приведите краткое обоснование утверждения, что время обработки процедурой РАкт!тюм подмассива, состоящего из и элементов, равно 9 (и). 7.1-4. Как бы вы изменили процедуру Яискзокт для сортировки в невозрастающем порядке? 7.2 Производительность быстрой сортировки Время работы алгоритма быстрой сортировки зависит от степени сбалансированности, которой характеризуется разбиение. Сбалансированность, в свою очередь, зависит от того, какой элемент выбран в качестве опорного.
Если разбиение сбалансированное, асимптотически алгоритм работает так же быстро, как и сортировка слиянием. В противном случае асимптотическое поведение этого алгоритма столь же медленное, как и у сортировки вставкой. В данном разделе будет проведено неформальное исследование поведения быстрой сортировки при условии сбалансированного и несбалансированного разбиения. Наихудшее разбиение Наихудшее поведение алгоритма быстрой сортировки имеет место в том случае, когда подпрограмма, выполняющая разбиение, порождает одну подзадачу с и — 1 элементов, а вторую — с 0 элементов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
