AOP_Tom3 (1021738), страница 176
Текст из файла (страница 176)
Ка проверяется на шаге (19, когда минимум слева направо погружается до позиции Яь 18. На шагах 143 и Я4 до перехода к 145 выполняется единственная замена 1 на 1) процесс РазделениЯ подмассива Яю .. И„заканчиваетсв пРи У' = ((1+ г)/2) на шаге ь47, т. е. подмассив разделяется по возможности точно пополам. (Количественно это выражается в том, что формулы (17) заменяются формулами А = 1, В = ((Х вЂ” 1)/2), С = Х+ (Х шод 2), это, по существу, наилучший случай для алгоритма (см также упр. 27, приведенное ниже), за исключением того, что  — -„' С. Если на шагах ь43 и 414 заменить знаки "<" знаками "<", то алгоритм вообще не будет сортировать данные.
Даже если предполагать, что в (13) стоят знаки "<2 все равно наш алгоритм поменяет местами Ве с Ви затем в третьей фазе разделения переместит исходную запись Вс в позицию Еэ и т д. Настоящая катастрофа! 19. Да, подмассивы можно обрабатывать в любом порядке. Но в очереди будет й(Х/ /~/Гоб Л7) элементов, если каждая очередная итерация будет разбивать массив ровно пополам, в то время как стек гарантированно остается меньшим по объему (см. следующее упражнение). 20. шах(0, ($8(Я+2)/(М+2Ц). (Самый плохой случай — — это когда Лг = 2~(М + 2) — 1 и все подмассивы разделяются точно пополам.) 21. На шаге Яб точно г записей перемещается в область Я,+~ Кл, поскольку В = й Когда фаза разбиения завершается, то У = в.
Следовательно, С вЂ” С' = Ю+ 1 — в есть количество вычитаний 1 из у. На шаге Ц7 мы должны получить 1 = в+ 1, если ключи различны, поскольку 1 = / влечет за собой К, = К. Таким образом, С' = в. 22. Указанное соотношение для Ал(х) легко вывести, поскольку А,-~(х)Ал,(в) — производящая функция для величины А после независимой сортировки случайных последовательностей длиной э — 1 и Х вЂ” в. Аналогичным образом получаем соотношения !и»«я-м)Е .=1 при Ж > М. Здесь Ь,»л — вероятность того, что э и 1 примут данные значения в последовательности длиной Х, а именно ~' ') (Е ') /' (" ) Последнее выражение равно произведению трех сомножителей: числа перестановок множества (1,..., в — Ц, числа перестановок множества (в+ 1,..., 07) и числа способов взаимной замены ! элементов из одного подмассива и 1 элементов из другого подмассива. Первый сомиожитель есть произведение (1/Х!) и (» — 1)!, второй сомножитель равен (Ж вЂ” в)!, а третий равен (', )(, ').
При 0 ( Х < М получим Вя(1) = Сл(г) = Ея(») = 1, Р (=) =П,"=,(( +(Ь-1) )/Ь) Е.() =й~'=,(( + + +"-')/ ) (Интересно проанализировать поведение этой производящей функции при большом Ж; последовательност»ь аналогичная Ся(э), но с г +, замененным на»~, как известно, я».! и-» сходится к распределению, отличному от нормального, что не позволяет проанализировать его полностью. (См. статью Р.
Неппес»шо, М. Небп!ег, 1~'. Нов!ег, ЕАЖО ТЬеогебса! 1п1оппабсэ впг! Аррбсвсюлэ 23 (1989), 317-333; 23 (1989), 335-343; 25 (1991), 85-100.)) 23. ПРи Х > М полУчаем АЯ = 1 + (2/Е) 2 о<»< „А»; Вл = Л о«<я Ьмм(1+ В~-~ + Вя,) = (1/Х) х ~ ((в-1)(Х вЂ” в)/(Х вЂ” 1)+В,-»+Вл —,) = (Х вЂ” 2)/6+(2/!»») с„об»<пВ» (см, упр. 22); Рх = (2/Х) Л э<»<лР»; Ел получается аналогично.
При Х > 2М+ 1 получаем Яь = (2/Лу) 2,' <»< Я» + (Š— 2М вЂ” 2)/Х. Каждое из этих рекуррентных соотношений имеет форму (20) при некоторой функции / . 24. Рекуррентное соотношение Ск = Х вЂ” 1+ (2/Лг) 2»<»<~ С» при Х > М имеет решение (%+1)(2Нл+» — 2Нм ь»+1 — 4/(Лу-»2)+2/(!»»+1)). (Таким образом, мы могли бы сэкономить около 4Х/М сравнений. Но для каждого сравнения потребуется больше времени, если за ним последует анализ» и /, В результате мы проиграем, если только потери при сравнении двух ключей не превысят в -'М!и Х раз потери от сравнения двух регигтров. Многие теоретические выводы относительно сортировки не удалось реализовать на практике, поскольку предлагаемые "усовершенствования" превращали быструю сортировку в существенно менее быструю!) 25.
(Многократно примените формулы (17), подставив е = 1.) А = !»» — М, В = О, С = ( ) ( ) Р— Š— Š— О. 26. Действительна, нет ничего хуже, чем сортировать 1 2 3 ... Х вЂ” М !»» Ю-1,. Ю вЂ” М+1. Часть этой последовательности Х М-1 М вЂ” 2 .. 1 М М+1 .. Ж-1 почти так же плоха. Но это лишь чуть-чуть хуже, чем в упр. 25, поскольку при таком наборе получим Р=М вЂ” 1,Е=(,). 27. 12 2 3 1 8 6 7 5 9 10 11 4 16 14 15 13 20 18 19 17 21 22 23; требует 546и. Можно показать, что наилучшим при Х = 3(М + 1)2 — 1 будет случай, когда подмассивы при каждом разбиении делятся пополам до тех пор, пока не достигнут размера 3М + 2. Затем нужно использовать деление на треть, чтобы избежать переполнения стека. Получим А = 3.2 — 1, С = (Ь+ э)(Х+ 1), Я = 2» — 1, В = Р = Е = О. (Найти лучший случай для любого М и Х вЂ” задача очень интересная, но и очень гложная.) 28.
Рекуррентное соотношение 2 С„= и+ 1+ — ~(1с — 1)(п — к)Сь ©= можна преобразовать в ( )С вЂ” 2( )С -г + ( )Со-г = 2(п — 1)(п — 2) +2(п — 2)С г. 29. В общем случае рассмотрим рекуррентное соотношение С п 2 ~ ~(1с — 1) (п — (с) С (,".) = которое возникает, когда разделение управляется медианой 21 + 1 элементов. Полагая С(е) = ~"„С„е", его можно преобразовать в (1 — е)'+'Ссг'+0(е)/(21+ 2)! = 1/(1 — е)'+ + СОО(э)/(1+1)!.
Пусть /(х) = СОО(1 — х); тогда рс(д)/(х) = (21+2)!/х +с где д - — оператор х(д/с(х) и рс(х) = (1 — х)'~' — (21+ 2)'х'. Общее решение уравнения: (д — а)д(х) = хо имеет вид д(х) = хо/(д — а) + Схо при а ф д н д(х) = хо(1пх + С) прн а = д Имеем рс(-1 — 2) = О, так что общее решение этого дифференциального уравнения таково: СП (е) = (21+ 2)!!п(1 — е)/ре( — С вЂ” 2)(1 — е)'ог + ~ сг(1 — е)о', где ао,, ас — корни уравнения рс(х) = О, а константы е„зависят от начальных значений Сс,..., Сго Удобное тождество „! ( 1 ) =Е(Н„, -Н )("+ ),", >О, о>о приводит к удивительна простому решению в зомкнделом виде Нгсог — Нсь~ п1 ' г=о из которого легко выводится асимптотическая формула.
(Главный член п )пи/ (Нгс+г— Нсос) выделил Ц. ван Эмден (см. М. Н. тап Ешдеп, САСМ 13 (1970), 563-567], используя теоретико-информационный подход. Действительно, предположим, что необходимо проанализировать произвольный процесс разделения, такой, что в левом подмасснве будет содеРжатьсЯ хЖ элементов с асимптотической веРсжтностью /о' /(х) дх пРи Лс -о ж, длЯ 0 < х < 1. Ван Эмден доказал, что среднее число сравнений, необходимых для полной сор- 1 тировки всего массива, имеет асимптотическое выражение а 'п1оп, где а = -1//о (/(х)+ /(1 — х)) х!их с(х. Эта формула применима к обменной поразрядной сортировке, а также к быстрой сортировке и другим методам.
См. также Н. Нагнйэ, САСМ 14 (1971), 99-102.) 30. Решение 1 (представляет., скорее всего, историческую ценность). Каждый подмассив можно описывать четырьмя величинами (1, г, (с, Х), где 1 и г -- границы (как н ранее), 1с указывает число слав в ключах, о которых известно, что они равны во всем подмассиве, а Х вЂ” нижняя граница (х+1)-х слов в ключах. В предположении, что ключи неотрицательны, имеем вначале (1, г, й, Х) = (1, Ю, 0,0). Прн разделении массива полагаем К равным (1с+ 1)-му слову проверяемого ключа Кс. Если К > Х, то прн разделении все ключи > К оказываются справа, а все ключи < К вЂ” слева (если смотреть каждый раэ только на (ге+ 1)-е слова ключа). Соответственно разделегсньсе подмассивы получают описания (1,1-1,/г,Х) и (Л,г,к,К).
Но если К = Х, та при разделении все ключи > К попадают вправо, а все ключи < К (фактически = К( — влево; разделенные подмассивы получают описания соответственно (1, Л, к+ 1, О) и (Л+ 1, г, й, К), В обоих случаях нельзя быть уверенным в том, что запись Я, заняла окончательное положение, поскольку мы не просмотрели (к+2)-о слова. Для правильной работы с граничными условиями необходимо внести другие очевидные изменения. Добавив в описание пятый компонент, "верхняя граница", можно сделать этот метод симметричным относителыю левой и правой частей массива.
Решение Я (ВепМеу, Беббеиб!с!г, ЯОПА 8 (1997), 360 — 369]. Пусть, как и в решении 1, К будет (!г+ 1)-ым словом в Кэ в падл1ассиве, описанном (1, г, й). Но далее используйте алгоритлг из упр. 41 для разделения подмассива на три части, (1,1 — 1, !г), (1,Л,)г + 1), (! + 1,г,й), для случаев <К, =К, >К.
Этот подход, который авторы назвали ти!!йеу ди!с!гзог! (быстрая сортировка по мультиключу), дает значительно лучшие результаты, чем решение 1, и является вполне достойным конкурентом самых быстрых методов сортировки символьных строк. 31. Выполните обычное разделение, и пусть В~ попадет в позицию В,. Если э = т, то на этом можно закончить. Если э < т, воспользуйтесь тем же методом для нахождения (т — э)-го наименыпего элемента в правом падмасснве. Если же э > гл, найдите т-й наименьший элемент в левом подмассиве.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
