Алгоритмы - построение и анализ (1021735), страница 38
Текст из файла (страница 38)
Дальнейшее улучшение этой границы до О (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 элементов.
(Это будет доказано в разделе 7.4.1.) Предположим, что такое несбалансированное разбиение возникает при каждом рекурсивном вызове. Для выполнения разбиения требуется время О (и). Поскольку рекурсивный вызов процедуры разбиения, на вход которой подается массив размера О, приводит к возврату из этой процедуры без выполнения каких-либо операций, Т (0) = О (1). Итак, рекуррентное соотношение, описывающее время работы этой процедуры, записывается следующим образом: Т(п) = Т (и — 1) + Т(0) + О(п) = Т(п — 1) + 6(п).
Интуитивно понятно, что при суммировании промежутков времени, затрачиваемых на каждый уровень рекурсии, получается арифметическая прогрессия (уравнение (А.2)), что дает нам в результате 6 (пз). В самом деле, с помощью метода Часть й. Сортировка и порядковая статистика 204 подстановок легко доказать, что Т (и) = О (пз) является решением рекуррентного соотношения Т (и) = Т (и — 1) + О (и) (см. упражнение 7.2-1).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
