Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 44
Текст из файла (страница 44)
В общем случае ситуация такая. Поскольку предполагается, что значения всех элементов различаются, при выборе в качестве опорного элемента такого л, что гч < х < лз, элементы л, и л, впоследствии сравниваться не будут. С другой стороны, если в качестве опорного элемент г, выбран до любого другого элемента Я,!, то он будет сравниваться с каждым элементом множества Я,!, кроме Часть П. Сортировка и иорядковаи статистика Рг(з, сравнивается с з ) = Рг(з, или зу — первый опорный элемент, выбранный из Яг '1 = Рг (з, — первый опорный элемент, выбранный и г,,> + Рг (з, — первый опорный элемент, выбранный ° г„) 1 1 + 1+111+1 2 1 — 1+1 (7.3) Вторая строка в приведенной выше цепочке равенств следует из того, что рассматриваемые события взаимоисключающие.
Комбинируя уравнения (7.2) и (7.3), получаем Е[Х! = ~ Эту сумму можно оценить, если воспользоваться заменой переменных (Й = 7 — 1) и границей для гармонического ряда (уравнение (А,7)): и — 1 Е~Х] = ~ г=1 2 ,1 — 1+ 1 у=г+1 2 и-.1 (,"' 2 1=1 себя самого. Аналогичное утверждение можно сделать по поводу элемента с . В рассматриваемом примере значения 7 и 9 сравниваются, поскольку элемент 7— первый нз множества Ут з, выбранный в качестве опорного. По той же причине (поскольку элемент 7 — первый из множества с за, выбранный в качестве опорного) элементы 2 и 9 сравниваться не будут. Таким образом, элементы гч и к, сравниваются тогда н только тогда, когда первым в роли опорного в множестве У,у выбран один из них. Теперь вычислим вероятность этого события. Перед тем как в множестве Я, будет выбран опорный элемент, все это множество является не разделенным, и любой его элемент с одинаковой вероятностью может стать опорным.
Поскольку всего в этом множестве 1 — 1+ 1 элемент, а опорные элементы выбираются случайным образом и независимо один от другого, вероятность того, что какой- либо фиксированный элемент первым будет выбран в качестве опорного, равна 1/Ц вЂ” г + 1). Таким образом, мы имеем Гвава 7. БыстГкт сортировка и — ! 0(1к п) в=1 = 0(п1ки) . (7.4) Таким образом, можно сделать вывод, что при использовании процедуры Клноом1кпо-Рлкт1т!ом математическое ожидание времени работы алгоритма быстрой сортировки различающихся по величине элементов равно 0(п 1я п). Упражнения 7.4.1 Покажите, что в рекуррентном соотношении Т(и) = !пах (Т(с7) + Т(п — !7 — 1)) + В(п), о<я< -! Т(п) = Й(из).
7.4.2 Покажите, что время работы быстрой сортировки в наилучшем случае равно Й(п!к и). 7.4.3 Покажите, что выражение !7~ + (и — !7 — 1) достигает максимума на множестве значений !? = О, 1,..., п — 1, когда !? = О или !7 = и — 1. 7.4.4 Покажите, что ожидаемое время работы процедуры КАмоом!еео-ЯО1сквокт равно Й(п1кп). 7.4.5 На практике время работы алгоритма быстрой сортировки можно улучшить, воспользовавшись тем, что алгоритм сортировки по методу вставок быстро работает для "почти" отсортированных входных последовательностей. Для этого можно поступить следующим образом.
Когда процедура быстрой сортировки начнет рекурсивно вызываться для обработки подмассивов, содержащих менее )с элементов, в ней не будет производиться никаких действий, кроме выхода из процедуры. После возврата из процедуры быстрой сортировки, вызванной на самом высоком уровне, запускается алгоритм сортировки по методу вставок, на вход которого подается весь обрабатываемый массив. На этом процесс сортировки завершается. Докажите, что математическое ожидание времени работы такого алгоритма сортировки равно 0(па + и1б(п/)с)). Как следует выбирать значение к, исходя из теоретических и практических соображений? 7.4.6 * Рассмотрим следующую модификацию процедуры РАкт1т1ом. В ней случайным образом выбираются три элемента массива А, и разбиение массива выполняет- Часть П.
Сортировка и порядковая статистика 2!4 ся по медиане выбранных элементов (т.е. по среднему из этих трех элементов). Найдите приближенную величину вероятности того, что в худшем случае разбиение будет произведено в отношении а к (1 — сь), как функцию от ск в диапазоне 0 < о < 1. Задачи 7.1. Корректность разбиения ио Хвору Представленная в этой главе версия процедуры РАКТ!Т10М не является реализацией первоначально предложенного алгоритма. Ниже приведен исходный алгоритм разбиения, разработанный Ч.Э.Р. Хоаром (С.А.К. Ноаге).
НОАке-РАкт!т101ч (А, р, т) 1 х = А[р[ 2 д=р — 1 3 2 =т+1 4 згййе ткпе 5 терев! б 2 =2 — 1 7 ппй! А[2[ < х 8 гереа! 9 1=1+1 10 пптН А[1[ > х 11 !А!<2 12 Обменять А[1[ и А[2[ 13 е1ае ге!игл 2' а. Продемонстрируйте, как работает процедура НОАке-РАкт!тю14 с массивом А = (13, 19, 9, 5, 12, 8, 7,4, 11, 2, 6, 21). Для этого укажите, чему будут равны значения элементов массива и значения вспомогательных переменных после каждой итерации цикла твЬйе в строках 4 — 13.
В следующих трех заданиях предлагается привести аргументы в пользу корректности процедуры НОАке-РАкт1тю1ч. В предположении, что подмассив А[р .. т[ содержит как минимум два элемента, докажите следующие утверждения. б. Индексы 1 и 2' принимают такие значения, что никогда не произойдет обращение к элементам массива А, находящимся за пределами подмассива А[р .. т[. в. По завершении процедуры НОАке-РАкт!тюм она возвращает значение 2, такое,чтор<2 <т. а По завершении процедуры НОАке-РАкт1т101ч каждый элемент подмассива А[р., 1] не превышает значений каждого элемента подмассива А[2 + 1 .. т1.
Глава 7. Ьистраа сортировка 215 В описанной в разделе 7.1 процедуре Рлкт1тюы опорный элемент (которым изначально является элемент А[г]) отделяется от двух образованных с его помощью лодмассивов. В процедуре же Нолкк-Рлкт1тюм, напротив, опорный элемент (которым изначально является элемент А[р]) всегда помещается в один из двух полученных подмассивов: А[р..5] или А[7' + 1..
г]. Поскольку р < 5 < г, это разбиение всегда нетривиально. д. Перепишите процедуру Я151скзокт таким образом, чтобы в ней использовалась процедура Нолкк-Рлкт1тюм. 7.2. Быстрая сортировка с равными элементами Анализ ожидаемого времени работы рандомизированной быстрой сортировки в разделе 7.4.2 предполагает, что все значения элементов различны. В данной задаче мы рассмотрим, что произойдет в противном случае. в. Предположим, что значения всех элементов одинаковы.
Каким будет время работы рандомизированной быстрой сортировки в этом случае? б. Процедура Рлкт1тюм возвращает индекс д, такой, что каждый элемент А[р .. д- Ц не превышает А[д], а каждый элемент А[ц+1 .. г] больше А[д]. Модифицируйте процедуру Рлкт171оы таким образом, чтобы получить процедуру Рлкт1т1ом'(А,р, г), которая переставляет элементы А[р .. г] и возвращает два индекса д и 1, где р < д < 1 < г, такие, что все элементы А[д .. 1] равны; каждый элемент А[р ., д — 1] меньше А[д]; каждый элемент А[1 + 1 ..
г] больше А[у]. Как и процедура Рлкт1тюм, ваша процедура Рлкт1тюм' должна иметь время работы Й(г — Р). в. Модифицируйте процедуру КЛМООМ12КО-РЛКт1тЮЫ так, чтобы она вызывала процедуру Рлкт1т1ом', и назовите новую процедуру именем Кл1чоом1ккоРлкт1тюм'. Затем модифицируйте процедуру Я151скзокт таким образом, чтобы, в свою очередь, получить процедуру Я151скзокт'(А, р, г), которая вызывает Кл1чоом1кко-Рлкт1тюм' и рекурсивно работает только с теми частями, элементы которых не равны один другому.
а Каким образом процедура Яо1скзокт' позволяет изменить анализ из разде- ла 7.4.2, чтобы избежать предположения о том, что все элементы различны? 7.3. Альтернативный анализ быстрой сортировки Можно предложить альтернативный анализ рандомизированной быстрой сортировки, в ходе которого внимание сосредоточивается на математическом ожидании времени, которое требуется для выполнения каждого рекурсивного вызова процедуры Яо1скзокт, а не на количестве производимых сравнений. Часть П.
Сортировка и яорядковая статистика Лб сь Докажите, что вероятность того, что какой-либо заданный элемент п-элементного массива будет выбран в качестве опорного, равна 1/п. На основании этого факта определите индикаторную случайную величину Х, = 1(1-й в порядке возрастания элемент выбран опорным) Что собой представляет величина Е [Х;]? б. Пусть Т(п) — случайная величина, обозначающая время работы быстрой сортировки п-элементного массива. Докажите, что Е [Т(п)] = Е 1 Хо (Т(д — 1) + Т(п — а) + 9(п)) . (7.5) 1д=1 в. Покажите, что уравнение (7.5) можно представить в виде 2 и — 1 Е [Т(п)] = — ~~~ Е [Т(о)] + 9(п) . я=2 (7.6) г. Покажите, что 2 1 2 )с18)с < — и 1йп — — п 2 8 (7.7) (Указание; разбейте сумму на две части, в одной из которых суммирование проводится по индексам к = 2, 3,..., [п/2] — 1, а в другой — по индексам )с = [п/2],...,и — 1.) 7.4.
Глубина стека быстрой сортировки Алгоритм 1 Ц11СКЗОКт из раздела 7.1 содержит два рекурсивных вызова самого себя. После того как процедура Ягпскзокт вызывает процедуру Рлкт1т1о1ч, она рекурсивно сортирует левый подмассив, а затем так же рекурсивно сортирует правый подмассив. Второй рекурсивный вызов в Яц1скзОкт в действительности не является необходимым; его можно избежать с помощью итеративной управляющей структуры. Этот метод, получивший название оконечной рекурсии (пй1 гесцгз1оп), автоматически применяется хорошими компиляторами.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
