AOP_Tom3 (1021738), страница 48
Текст из файла (страница 48)
(15) Следовательно, суммарное время реализации алгоритма составляет 24А + 11В + 4С+ ЗВ + 8Е + 7К + 95 машинных тактов, где число итераций разбиения; число взаимных обменов на шаге ()б; число сравнений, выполненных во время разбиения; число случаев, когда К, ! > К! в ходе выполнения сортировки методом простых вставок (шаг (49); количество инверсий, удаленных в процессе простых вставок; количество случаев, когда происходит запись в стек. А— В— С— В— (16) 40 4! 48 45 44 45 ЗН 46 47 ВН 48 49 50 5! 9Н 58 2Н 58 54 55 ЗН 56 4Н 57 58 59 60 б! 5Н 68 6Н 68 51ИР 4В 1МС6 1 ЗТЗ ЯТАСК,6(В) ЕИТА 1,5 ЯТА ЯТАСК,6(А) ЕИТЗ -1,5 ЛМР 2В 192 ЗТАСК,б(А) 1РЗ БТАСК,6(В) РЕС6 1 56ИИ 2В ЕИТ5 2-И 1.РА 1МРОТ+И,б СМРА 1ИРОТ+И-1„5 ЗСЕ 6Г ЕМТ4 М-1,5 ЮХ 1ИРУТ,4 ЯТХ 1ИРУТ+1,4 РЕС4 1 СИРА 1ИРУТ,4 48 БТА 1ИРОТч1,4 1ИС5 1 35ИР 28 5 — 5'+ Ал' 5 — 5' 5 — 5' 5 — 5' 5 — 5' 5 — 5'+ А" 5 — 5'+ А" 5+1 5+1 5+1 5+1 1 )7 — 1 !9 — 1 Х вЂ” 1 В Е Е Е Е Е В й! — 1 Д! — 1 (1,7-1) ~ стек.
!+-у+1. Перейти к шагу Я2. Перейти к шагу ()8, если М > т — ! > > ! — !. Переход, если т — ! > М > ! — !. (Сейчас т — ! >,! — ! > М.) (1, т) ~ стек. Перейти к шагу Я2, если стек не пуст. Яб. Со тн евка мего ом п остыл вставок. ! е- 2. К е- К„Н е- Н,. (В атом цикле г15 и !' — АА) Переход, если К > К! 1 е- ! — 1. Проанализировав эти шесть параметров, можно сделать обоснованный выбор значения параметра М, которым определяется "граница" между сортировкой методом простых вставок и методом разделения.
Сам по себе анализ также весьма поучителен, поскольку алгоритм довольно сложен. В процессе анализа будут испольюваться важные методики, которые читатели, освоившие их, смогут в дальнейшем применять самостоятельно. (Те же, кто пе склонны к 'разгребанию математических завалов", могут спокойно перевернуть страницы вплоть до формул (25).) Как и при анализе большинства алгоритмов в этой главе, будем предполагать, что сортируемые ключи различны.
В упр. 18 показано, что наличие равных ключей существенно не снижает эффективность алгоритма (); в действительности присутствие равных ключей, гю-видимому, даже способствует ее увеличению. Поскольку метод зависит только от относительного расположения ключей, можно предполагать также, что это просто числа ( 1. 2,..., Л'), расположенные в некотором порядке. Справиться с проблемой попробуем, рассмотрев первую же итерацию разбиения, с которой мы впервые всзречаемся на шаге Я7. Когда мы доберемся до этой операции, подмасспвыЛ~...
Л. ~ и Л.+~... Лм будут содержать записка случайном порядке, если и в исходной последовательности они располагались в г зучайном порядке, поскольку относительное положение записей в подмассивах никак не влияет на алгоритм разделения. Таким образом, комбинация последовательных разбиений может быть проанализирована посредством индукции по Х. (Это важное замечание, поскольку альтернативные а:поритмы, которые не обладают этим свойством, оказываются, в конце концов, существенно более медленными; см. СотриЛп8 Внггеуз 6 (1974), 287 289.) Пусть в — значение первого ключа Км и предположим, что ровно 1 ключей Кы ..,, К, превосходят в.
(Напомню, что сортируемые в наших примерах ключи— целые числа 11, 2,, Ж).) Если в = 1, то нетрудно видеть, что произойдет во время первой итерации разделения. Шаг ЯЗ выполнится однократно, шаг Я4 . — Х раз, а шаг Я5 приведет нас к шагу ()7. Таким образом, "взнос" первой итерации в анализируемые параметры будет следуя>щим; А = 1, В = О, С = Х + 1. Аналогичные, но несколько более вьюжные рассуждения для случая г > 1 (см. упр. 21) показывают, что взнос первбй итерации в суммарное время выполнения в общем случае будет составлять (17) для 1 < в < й7.
А=1, В=1, С=%+1 К этому необходимо добавить вклады последующих итераций, во время которых упорядочиваются подмассивы из в — 1 и Х вЂ” в элементов соответственно. Если предположить, что в исходной последовательности запися располагались в случайном порядке, то можно выписать формулы, которыми определяются производящие функции для распределений вероятностей величин А, В,..., В (см. упр. 22). Но для простоты рассмотрим здесь только средние значения этих величин Ак, Вм,...,Як как функции от Х Рассмотрим, например, среднее числа сравнений Сл, выполненных в процессе разделения. Если Х < 5Х, то См = О. В противном случае, поскольку любое данное значение в встречается с вероятностью 1/Ю, получим Ж Сл = у ~~' (Ат-ь1+ С вЂ” +Си-.) в=т 2 = Ат+1+ —, ~~~ Сь для Ат > ВХ.
Ю (1В) айь<н Аналогичные форлтулы имеют место и для остальных величин Алт, В~, Рн, Ен, Ятт (см. упр. 23). Существует простой способ решения рекуррентных соотношений вида 2 х„= /ь+ — ~~~ хь для и > т. и е<ь<ч (19) Па первом шаге нужно освободиться от знака суммирования: поскольку (и+1)х„+т =(и+1)/„+т+2 ~~ хы о<в< их„= тт/„+ 2 ~~~ хы ой<я<и можно вычесть второе равенство из нервого, получив (и + 1) ха.ю — их„= д„+ 2х„, где ди = (и + 1)/» ы — иУ„.
Теперь рекуррентная зависимость принимает гораздо более простой вид: (и + 1) х„+т = (и + 2) х„+ д„для и > ти. (20) Любое рекуррентное соотношение общего вида а„х„+т — — Ь„х„+ д„ (21) аа...а„ ае...а„т д„+ — — д„+ с„, где д„= Ь Ь х„, с„= ' " д„.
(22) О ° ° и-т ЬО 1 ° ° ° л Для (20) суммирующий множитель равен просто и!/(и+2)! = 1/(и+1)(и+2). Таким образом, находим, что простое соотноптенне х„+т х„(и + 1)/и+т — и/„ + для и > т и + 2 и + 1 (и + 1)(и + 2) (23) является следствием соотношения (19).
Если, например, положить /„= 1/и, то получится неожиданный результат: х„/(и+ 1) = х /(та+ 1) при любом п > ти. Если положить /„= и+ 1, получится х„/(и+ 1) = 2/(и+ 1) + 2/и+ + 2/(ти+ 2) + х /(т+ 1) = 2(Н„„, — Н„,~т) +х /(т+1) можно свести к простой сумме, если умножить обе части на "'суммирующий множи- тель" ао ат... а„, /Ье Ь,...
Ь„. Получаем при любом и > пз. Таким образом получим решение для (18), подставив т = М+ 1 и х„= 0 при и < М:, искомая формула имеет вид См = (Н + 1) (2Нл~~ — 2Нм+т + 1) /Н+11 ю 2 (Ж + 1) 1п ~ — ~ для Н > М. 1,М+ 2,~ (24) В упр. 6.2.2-8 будет доказано, что при М = 1 стандартное отклонение величины Сч рб. * лн-2 )лК.В* р с (24). Остальные величины можно найти аналогичным способом (см. упр.
23); при Н > Л4 имеем Ал~ = 2 (Ю + 1)/(М + 2) — 1, 1 / 6 1 1 л = — (%+ 1)( 2Ну+~ — 2Нм+т+ 1 М 2 ) + 2' + Пл' = (Ж+ 1)(1 — 2Нм- ~/(М+ 2)) Ел = -' (ЛЛ + 1) М(Л1 — 1) /(М + 2); Яп = (Н+ 1)/(2М+3) — 1 для Ю > 2М+ 1. (25) Из приведенных выше соображений следует, что можно точно проанализировать среднее время выполнения весьма сложной программы, используя методы, которые мы ранее применяли в более простых случаях.
с1тобы определить наилучшее значение М для конкретного компьютера, можно воспользоваться формулами (24) н (25). При Н > 2М + 1 выполнение программы (4 на компьютере МХХ требует в среднем (35/3)(Н + 1)Нм,.~ + -'(Н + 1),((М) — 34.5 машинных циклов, где ДМ) = 8М вЂ” 70Нм~з 4 71 — 36 — ~- — + ', (26) Нм~~ 270 54 М+ 2 Л4+ 2 2М+3 >Келательно выбрать такое значение М, при котором функция 7'(М) достигает минимума. Несложные рассуждения приводят нас к такому результату: ЛХ = 9.
При этом для больших Ж среднее время выполнения программы 14 равно приблизительно 11.667(%1+) 1п Н вЂ” 1.74% — 18.74 машинных циклов. Таким образом, программа ц работает в среднем довольно быстро; гшедует, кроме того, учесть, чго она требует очень мало памяти. Высокая скорость определяется, в первую очередь, тем, что внутренний цикл — шаги (43 и Я4 — очень короток (см, строки 12 14 и 15 -17 текста программы).
Количество операций обмена записей в памяти на шаге Яб составляет всего около 1/6 количества сравнений на шагах ЯЗ н Я4; к тому же мы очень много экономим вследствие того, что отпала необходимость в сравнении 1 с 1 во внутреннем цикле. Но каков наихудший случай для алгоритма Я? Существуют ли какие-нибудь исходные файлы, обрабатывать которые с помощью этого алгоритма не эффективно? Ответ несколько обескураживает: если исходный файл уже упорядочен, а именно— К~ < Кз < . < Кл, то каждая операция "разделения" становится почти бесполезной, так как она уменьшает размер подмасснва всего лишь на один элемент! Значит, в этой ситуации (которая должна быть самой простой для сортировки) быстрая сортировка превращается в отнюдь не быструю. Время ее работы становится пропорциональным Мз, вне Х 18 Ю(см.
упр. 25). В отличие от других алгоритмов сортировки, которые нам встречались, алгоритм Я предпочитает неупорядоченные файлы! В упомянутой статье Хоара предложены два способа устранения этого недостатка. Они базируются на выборе лучшего значения проверяемого ключа К, который управляет разделением. Одна из его рекоменлаций состоит в том, чтобы в последней части шага Я2 выбрать случайное целое число д в диапазоне между 1 н г. На этом шаге можно заменить команды выполнения операций К +- К~ операциями (27) Ке-Кд, В<-йц, И,~-Нц Л~< — Н. (Последняя операция присваивания необходима, поскольку в противном случае на шаге Я4 произойдет прекращение цикла с сохранением 1 = 1 — 1, если К есть наименьший ключ в разделяемом подмассиве.) Согласно формулам (25) такие случайные целые числа придется вычислять в среднем лишь 2 (А'+ 1)/(М + 2) — 1 раз, так что дополнительные расходы несущественны, а случайный выбор — хорошая защита от возможности оказаться в наихудшей ситуации.
Даже "слабая" случайность в выборе д может служить достаточной защитой. В упр. 58 доказано, что при действительно случайном значении д появление более чем 20Х!пХ сравнений возможно с вероятностью, меныпей 10 ~. Второе предложение Хоара состоит в просмотре небольшого фрагмента сортируемой последовательности и нахождении медианы для этой совокупности данных. Такому подходу последовал Р. К. Синглтон [см.
В.. С. 81п81е1оп, САСМ 12 (1969), 185-187), который предложил в качестве Кэ брать медиану трех значений: (28) М К10ч-г)/21~ Процедура Синглтона сокращает число сравнений с 2%1п1У примерно до ~~%1п)У (см. упр. 29). Можно показать, что в этом случае В,ч асимптотически приближается к Сд/5, а не к Ск/6, так что метод медианы несколько увеличивает время, затрачиваемое на пересылку данных. В результате общее время работы сокращается примерно на 8Уо. (Подробный анализ приводится в упр. 56.) Время работы в наихудшем случае все еще составляет порядка Ю, однако с таким случаем вряд ли когда-либо придется сталкиваться на практике.
У. Д. Фрэйзер и А. Ч. МакКеллар (см. Ж. П. Егахег апс1 А. С. 54сКе1!аг, Х4СМ 17 (1970), 496-507] предложили рассматривать совокупность гораздо большего объема из 2" — 1 записей, где и выбирается так, чтобы 2" ьч Ж/1п Ф. Эту совокупность можно рассортировать обычным методом быстрой сортировки, после чего элементы расположить среди остальных записей за й просмотров всего массива (в результате массив записей будет разделен на 2ь подмассивов, ограниченных элементами выборки). На заключительном этапе сортируются полученные подмассивы. Если Ж находится в реальном диапазоне значений, то среднее число сравнений, выполняемых такой процедурой "сортировки выборки", примерно такое же, как и для метода медианы Синглтона, но при Ю -э оо оно асимптотически приближается к %18 %.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
