Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 42
Текст из файла (страница 42)
Сортировка и порядковая статистика 212 раза, полное юличество сравнений, выполняемых на протяжении работы алго- ритма, легко выразить следующим образом: Применяя к обеим частям этого выражения операцию вычисления математиче- ского ожидания и используя свойство ее линейности и лемму 5.1, получим: Е[Х] =Е и — 1 и ч.
Е Ху 1=1 1=1+1 и-1 и — Е[Х;]= 1=1 1=1-~-1 и-1 и ,'> Рг(«; сравнивается с «). 17.2) 1=1 1=1+1 Осталось вычислить величину Рг(«; сравнивается с « ). Предполагается, что опорные элементы выбираются случайным образом, причем независимо друг от друга. Полезно поразмышлять о том, когда два элемента не сравниваются. Рассмотрим в качестве входных данных для алгоритма быстрой сортировки множество, состоящее из целых чисел от 1 до 10 (в произвольном порядке), и предположим, что в качестве первого опорного элемента выбрано число 7. Тогда в результате первого вызова процедуры РАнт1т1ои все числа разбиваются на два множества: (1,2,3,4,5,6) и (8,9,10). При этом элемент 7 сравнивается со всеми остальными.
Очевидно, что ни одно из чисел, попавшее в первое подмножество (например, 2), больше не будет сравниваться ни с одним элементом второго подмножества (например, с 9). В общем случае ситуация такая. Поскольку предполагается, что значения всех элементов различаются, то при выборе х в качестве опорного элемента впоследствии не будут сравниваться никакие «; и «, для которых «; < х < «у. С другой стороны, если в качестве опорного выбран элемент «„то он будет сравниваться с каждым элементом множества Е,~, кроме себя самого. Аналогичное утверждение можно сделать по поводу элемента «;.
В рассматриваемом примере значения 7 и 9 сравниваются, поскольку элемент 7 — первый из множества Ят э, выбранный в роли опорного. По той же причине (посюльку элемент 7 — первый из множества Яз э, выбранный в роли опорного) элементы 2 и 9 сравниваться не будут. Таким образом, элементы «; и «у сравниваются тогда и только тогда, когда первым в роли опорного в множестве Л1 выбран один из них. Глава 7.
Быстрая сортировка 213 Рг (я1 сравнивается с я ) = = Рг(Первым опорным элементом выбран г, или -.3) = Рг (Первым опорным элементом выбран я1] + + Рг (Первым опорным элементом выбран з,) = 1 1 2 + 3 †и 7 — г+1 1 †и (7.3) Сумма вероятностей в приведенной выше цепочке равенств следует из того, что рассматриваемые события взаимоисключающие. Сопоставляя уравнения (7.2) и (7.3), получаем: Е[Х] = ,'1 1=1 уии+1 Эту сумму можно оценить, воспользовавшись заменой переменных (Й = 1 — 1) и границей для гармонического ряда (уравнение (А.7)): 2 з з 2 и — 1 и-1 < и-1 = ,'1 0(1бт1) = 0(п1я11).
и-1 и Е[Х] = ,'1 1=1 3=1+1 (7.4) Таким образом, можно сделать вывод, что при использовании процедуры Клы00м!ве0 РАкт1т101ч математическое ожидание времени работы алгоритма быстрой сортировки различающихся по величине элементов равно 0 (и 1к и). Упражнения 7.4-1. Покажите, что в рекуррентном соотношении Т(п) = 1пах (Т(д) + Т(п — д — 1)) + 9(п), с<я<и-1 Т (и) = й (т1 ) . Теперь вычислим вероятность этого события. Перед тем как в множестве Уц будет выбран опорный элемент, все это множество является не разделенным, и любой его элемент с одинаковой вероятностью может стать опорным.
Поскольку всего в этом множестве 1 — г + 1 элемент, а опорные элементы выбираются случайным образом и независимо друг от друга, вероятность того, что какой- либо фиксированный элемент первым будет выбран в качестве опорного, равна 1Я вЂ” г + 1). Таким образом, выполняется следующее соотношение: Часть !!.
Сортировка и порядковая статистика 214 7.4-2. Покажите, что в самом благоприятном случае время работы алгоритма быстрой сортировки равно П 1н !я и). 7.4-3. Покажите, что функция»?з+(и — »7 — 1) на множестве»! = О, 1,...,п — 1 достигает максимума при»7 = О или д = п — 1. 7.4-4. Покажите, что математическое ожидание времени работы процедуры КАноом1гео Яяскзонт равно П 1н1ки). 7.4-5. На практике время работы алгоритма быстрой сортировки можно улучшить, воспользовавшись тем, что алгоритм сортировки по методу вставок быстро работает для "почти" отсортированных входных последовательностей. Для этого можно поступить следующим образом. Когда процедура быстрой сортировки начнет рекурсивно вызываться для обработки подмассивов, содержащих менее й элементов, в ней не будет производиться никаких действий, кроме выхода из процедуры.
После возврата нз процедуры быстрой сортировки, вызванной на самом высоком уровне, запускается алгоритм сортировки по методу вставок, на вход которого подается весь обрабатываемый массив. На этом процесс сортировки завершается. Докажите, что математическое ожидание времени работы такого алгоритма сортировки равно О 1тй + и 1я (и/1с) ). Как следует выбирать значение 1с, исходя из теоретических и практических соображений? * 7.4-6. Рассмотрим модификацию процедуры РАнт1т1он путем случайного выбора трех элементов массива А и разбиения массива по медиане выбранных элементов (т.е. по среднему из этих трех элементов). Найдите приближенную величину вероятности того, что в худшем случае разбиение будет произведено в отношении а к 11 — »з), как функцию от а в диапазоне О < »з < 1.
Задачи 7-1. Корректность разбиения по Хоару Представленная в этой главе версия процедуры РАкт1т1он не является реализацией первоначально предложенного алгоритма. Ниже приведен исходный алгоритм разбиения, разработанный Хоаром (С.А.К. Ноаге): НоАкн РАнт!т1ом1А, р, г) 1 я -А[р) 2 㻠— р — 1 3 з -г+1 4 н 'и!!е ткал 5 бо гереаг з + — 7' — 1 Глава 7. Быстрая сортировка 218 нп61 А[1] < х гереаФ 1 — 1+ 1 пп61 А[1] > х !11< 7 Феп Обменять А[а] + А[з] е1ве ге1игп 7' б 7 8 9 10 11 а) Продемонстрируйте, как работает процедура Нолкн Рлкт~тюн с входным массивом А = (13,19,9,5,12,8,7,4, П,2,6,21). Для этого укажите, чему будут равны значения элементов массива и значения вспомогательных переменных после каждой итерации цикла ий11е в строках 4 — 11. В следующих трех заданиях предлагается привести аргументы в пользу корректности процедуры Нолкв Рлкт~тюн.
Докажите следующие утвер- ждения. б) Индексы г и 7' принимают такие значения, что обращение к элементам массива А, находящимся за пределами подмассива А [р..т], никогда не произойдет. в) По завершении процедуры Нолкв Рлкт~т1он возвращается значение 1, такое что р < 7' < т. г) По завершении процедуры Нолкв Рлкт~тюн каждый элемент подмассива А [р..Я не превышает значений каждого элемента подмассива А [7'+ 1..т]. В описанной в разделе 7.1 процедуре Рлкт171он опорный элемент (которым изначально является элемент А [т]) отделяется от двух образованных с его помощью подмассивов. В процедуре же Нолке Рлкт~т10н, напротив, опорный элемент (которым изначально является элемент А [р]) всегда помещается в один из двух полученных подмассивов: А [р..7] илн А [7' + 1..т]. Поскольку р < 7' < т, это разбиение всегда нетривиально.
д) Перепишите процедуру Яоюкзокт таким образом, чтобы в ней использовалась процедура Нолке Рлкт1т10х. 7-2. Альтернативный анализ быстрой сортировки Можно предложить альтернативный анализ рандомнзнрованной быстрой сортировки, в ходе которого внимание сосредотачивается на математическом ожидании времени, которое требуется для выполнения каждого рекурсивного вызова процедуры Яи!скзокт, а не на количестве производимых сравнений. Часть П. Сортировка и порядковая статистика 216 а) Докажите, что вероятность того, что какой-либо заданный элемент и-элементного массива будет выбран в качестве опорного, равна 1/и. Опираясь на этот факт, определите индикаторную случайную величину Х; = 1(1-й в порядке возрастания элемент выбран опорным) .
Какой смысл имеет величина Е [Х;]? б) Пусть Т(п) — случайная величина, обозначающая время работы алгоритма быстрой сортировки и-элементного массива. Докажите, что Е[Т(п)] = Е ~~) Хд(Т(д — 1) + Т (и — д) + О (и)) д=з (7.5) в) Покажите, что уравнение (7.5) можно представить в виде 2 и-1 Е [Т (и)) = — ~ Е [Т (д)) + О (и) . 4=2 (7.6) г) Покажите, что 3 1 2 ~~> Й18Й < — и 18и — — и . 2 8 (7.7) (Указание: разбейте сумму на две части, в одной из которых суммированиепроводитсяпоиндекса)с = 2,3,..., )п(2[ — 1,авдругой— по индексам /с = [п/2],..., и — 1.) д) Покажите с помощью неравенства (7.7), что решение рекуррентного соотношения (7.6) имеет вид Е [Т(п)) = 9 (п18 и).
(Указание: с помощью подстановки покажите, что Е [Т(п)] < оп 18п для достаточно больших п и некоторой положительной константы а.) 7-3. Блуждающая сортировка Два профессора предложили "элегантный" алгоритм сортировки, который выглядит следующим образом: 8тооан 8окт(А, г,у) 1 Ы А[1) > А[7] 2 гйеп Обменять А[1] А[7] 3 Ыг+1>7' 4 1пеп гегпгп 5 )с ~ — [(з — 1+ 1)/3] с Округление в меньшую сторону 6 8тооон 8онт(А, г, з — )с) ь Первые две трети 7 8тооон 8окт(А,1+ )с, 1) с> Последние две трети 8 8тооон 8окт(А, г,у — )с) с> Снова первые две трети Глава 7.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
