Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 41
Текст из файла (страница 41)
Эта процедура всегда выбирает элемент х = А[т] в качестве опорного (р!то!). Разбиение подмассива А[р .. т] будет выполняться относительно этого элемента. В начале выполнения процедуры массив разделяется на четыре области (они могут быть пустыми). В начале каждой итерации цикла !ог в строках 3 — 6 каждая область удовлетворяет определенным свойствам, показанным на рис.
7.2. Эти свойства можно сформулировать в виде инварнанта цикла. В начале каждой итерации цикла в строках 3-6 для любого индекса lс мас- сива справедливо следующее: 1. если р < lс < 1, то А[/с] < х; 2. если 4+ 1 < lс < 7' — 1, то А[/с] > х; 3, если й = т, то А[к] = х. Часть Рб Сортировка ы ларядкавая статыстика ! р,! (а) л,! ) (в) Н 8 ~ 7 ( ) ) 3 ~ 5 ~ 6$4! р,! (в) (2 71( ~3 ~ 5ЛХ64 ( р! ! г (г) ';2 ) '3(516$4 ,о !' 1 г 00 :'2,:1 3:5.6~4. р ! г (е) ('2т(1 (3 5; 6~4( р ! 1 г (к) ~2 Г) ~3 6$4~ р ! г сб (2) )1З .! р ! (л) (:2 ) 1 ~:3 ~ 4 Рнс. 7.1. Пример действия процедуры Рлкт(тюн на массив.
Элемент массива А~т~ становится опорным элементом к. Светло-серым цветом обозначены элементы массива, которые попали в первую часть разбиения; их значения не превышают х. Элементы темно-серого цвета образуют вторую часть массива; их величина больше х. Незакрашенные элементы — это элементы, которые пока что не попали ни в цлиу из первых двух частей; последний незакрашенный элемент явллегса опорным элементом х, (а) Начальное состояние массива и значения переменных. Ни один элемент не помещен ни в шшу из первых двух частей.
(6) Элемент со значением 2 "переспшлен сам с собой" и помещен в часгь с меньшими значениями. (в) и (г) Элементы со значениями 8 и 7 добавлены в часть с большими значениями. (д) Элементы 1 и 8 поменялись местами, в результате чего количеспю элементов в первой части возросло. (е) Обмен местами элементов 3 и 7, в результате чего колнчеспю элементов в первой час!и возрастает. (л!) и (з) Вторая часть уееличиваегся за счет включения в нее элементов б и б, после чего цикл завершается. (и) В строках 7 и 8 опорный элемент меняется местами с тем, который находится между лвумя областями. Индексы между 3 и т — 1 не подпадают ни под один из трех перечисленных случаев, и значения соответствующих им элементов не имеют определенной связи с опорным элементом х.
Нам необходимо показать, что сформулированный выше инвариант цикла справедлив перед первой итерацией, что каждая итерация цикла сохраняет этот инвариант и что он позволяет продемонстрировать корректность алгоритма по завершении цикла. Инициализации. Перед первой итерацией цикла ! = р — 1 и 2 = р. Мелсзу элементами с индексами р и з нет никаких элементов, как нет их и между ги Глава 1 Быонрая сармараека >х >х Огрвннчвнка нвт Рне. 7.2.
Четыре области, поддерживаемые процедурой Рлит~тюм в подмассиве А]р..г]. Все элементы псдмассиаа А]р .. в] меньше либо равны х, все элементы подмассива А]в+ 1 .. У вЂ” Ц больше х, а АИ = х. Полмасснв А]у .. г — Ц может иметь любые значения. Р г 7 г (в) >х >х р г >х Рнс. 7З.
Два варианта итерации в процедуре Рлкт~тюн. (а) Если А]у] > х, единственным действяем выметая увеличение 3, что сохраняет инвариант цикла. (6) Если А]1] < х, индекс в увеличиваекя, А]в] и А]у] меняются местами, после чего увеличнваетса т. Инвариант цикла сгираняетсв н в этом случае. элементами с индексами з' + 1 и 7 — 1, поэтому первые два условия инварианта цикла тривиально выполняются.
Присваивание в строке 1 удонлепюряет третьему условию. Сохранение. Как видно из рис. 7.3, нужно рассмотреть два случая, выбор одного из которых определяется проверкой в строке 4. На рис.7.3,(а) показано, что происходит, если А[)] > х; единственное действие, которое выполняется в этом случае в цикле, — это увеличение на единицу значения З.
При увеличении значения 7 условие 2 выполняется для элемента А[7 — 1], а все остальные элементы остаются неизменными. На рис. 7.3,(б) показано, что происходит„ если А[]] < х; в этом случае увеличивается значение т, элементы А[т] и А[7] меняются местами, после чего на единицу увеличивается значение ~. В результате перестановки получаем А[з] < х, и условие 1 выполняется. Аналогично получаем А[7' — 1] > х, поскольку элемент, который был переставлен в позицию элемента А[7' — 1], согласно инварианту цикла больше х.
Часть!!. Сортировка и лорядковая статистика Завершение. По завершении работы алгоритма ! = г. Поэтому каждый элемент массива является членом одного из трех множеств, описанных в инварианте цикла. Таким образом, все элементы массива разбиты на три множества; величина которых не превышает х, превышаюшие х и одноэлементное множество, состоящее из элемента х. В последних двух строках процедуры РАКТ|т|О|ч опорный элемент перемещается на свое место в средину массива с помопгью его перестановки с крайним левым элементом, превышающим величину х.
После этого процедура возвращает новый индекс опорного элемента. Выход процедуры РАкт|тюн удовлетворяет требованиям, наложенным шагом разделения. Фактически он удовлетворяет немного более строгому условию: после строки 2 процедуры |,|г||скзокт элемент А[о[ строго меньше любого элемента А[а+ 1 .. г[ Время работы процедуры РАкт|т|оы над подмассивом А[р..г~ равно !В(п), где и = г — р + 1 (см. упр. 7,1.3). Упражнении 7.1.1 Воспользовавшись рис. 7.1 в качестве образца, проиллюстрируйте работу процедуры РАкт!т|ОМ с массивом А = (13, 19,9,5, 12,8, 7,4,21, 2,6, 11). 7.1.2 Какое значение о возвращает процедура РАкт|т|оы, если все элементы массива А[р.. г[ одинаковы? Модифнцируйте эту процедуру так, чтобы в случае, когда все элементы массива А[р ..
г~ имеют одно и то же значение, о определялось следующим образом: д = [(р+ г)|2[. 7.1.3 Приведите краткое обоснование утверждения, что время обработки процедурой РАкт!тю|ч подмассива, состоящего из п элементов, равно !Э(п). 7.1.4 Как бы вы изменили процедуру С|г||скзокт для сортировки в невозрастаюшем порядке? 7.2. Производительность быстрой сортировки Время работы алгоритма быстрой сортировки зависит от степени сбалансированности, которой характеризуется разбиение. Сбалансированность, в свою очередь, зависит от того, какой элемент выбран в качестве опорного. Если разбиение сбалансированное, асимптотически алгоритм работает так же быстро, как и сортировка слиянием.
В противном случае асимптотическое поведение этого алгоритма столь же медленное, как и у сортировки вставкой. В данном разделе л03 Глава 7. аыстраа сартиравка будет проведено неформальное исследование поведения быстрой сортировки при условии сбалансированного и несбалансированного разбиений. Разбиение в наихудшем случае Наихудшее поведение алгоритма быстрой сортировки имеет место в случае, когда подпрограмма, выполняющая разбиение, порождает одну подзадачу с п — 1 элементами, а вторую — пустую. (Это будет доказано в разделе 7.4.1.) Предположим, что такое несбалансированное разбиение возникает при каждом рекурсивном вызове. Для выполнения разбиения требуется время 9(п). Поскольку рекурсивный вызов процедуры разбиения, на вход которой подается массив размером О, приводит к немедленному возврату из этой процедуры без выполнения каких-либо операций, Т(0) = 9(1).
Таким образом, рекуррентное соотношение, описывающее время работы процедуры в указанном случае, записывается следующим образом: Т(п) = Т(п — 1) + Т(0) + 9(и) = Т(п — 1) + й(п) . Интуитивно понятно, что при суммировании промежутков времени, затрачиваемых на каждый уровень рекурсии, получается арифметическая прогрессия (уравнение (А.2)), что приводит к результату тэ(пз). В самом деле, с помощью метода подстановок легко доказать, что решением рекурреитного соотношения Т(п) = Т(п — 1) + й(п) является Т(п) = вэ(пз) (см. упр. 7.2.1). Таким образом, если на каждом уровне рекурсии алгоритма разбиение максимально несбалансированное, то время работы алгоритма равно 9(пз).
Следовательно, производительность быстрой сортировки в наихудшем случае не превышает производительности сортировки вставкой. Более того, это же время требуется алгоритму быстрой сортировки для обработки уже полностью отсортированного массива (распространенная ситуация, в которой время работы алгоритма сортировки вставкой равно 0(п)). Разбиение в наилучшем случае В наиболее благоприятном случае процедура Рлкт171ом приводит к двум подзадачам, размер каждой из которых не превышает и/2, поскольку размер одной из них равен ~п/2), а второй — ~п/21 — 1, В такой ситуации быстрая сортировка работает намного производительнее, и время ее работы описывается следующим рекуррентным соотношением; Т(п) = 2Т(п/2) + й(п), где мы не обращаем внимания на неточность, связанную с игнорированием функций апола и "потолок", и вычитанием 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
