Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 33
Текст из файла (страница 33)
(Те же, кто не склонны к "разгребанию математических завалов", могут спокойно перевернуть страницы вплоть до формул (25).) Как и при анализе болыпинства алгоритмов в этой главе., будем предполагать, что сортирусмыг ключи различны, В упр. 18 показано, что наличие равных ключей существенно не снижает эффективность алгоритма (4; в действительности присутствие равных ключей, по-видимому, даже способствует ее увеличению. Поскольку метод зависит только от относительного расположения ключей, можно предполагать также, что это просто числа (1, 2,..., Х), расположенные в некотором порядке.
Справиться с проблемой попробуем, рассмотрев первую же итерацию разбиения, с которой мы впервые встречаемся на шаге Я7. Когда мы доберемся до этой операции, подмасснвы Й~ ... Й. ~ и Ву, ~ ... Вч будут содержать записи в случайном порядке, если н и исходной последовательности они располывлнсь в случайном порядке, поскольку относительное положение записей в подмассивах никак не влияет на алгоритм разделения. Таким образом, комбинация последовательных разбиений может быть проанализирована посредством индукции по Ф.
(Это важное замечание, поскольку альтернатзшные алгоритмы, которые не обладают этим свойством, оказываются, в конце концов, существенно более медленными; см. СошрпИпй Япгиеуз 6 (1974), 28 --289.) Пусть в — значение первого ключа Км н предположим, что ровно 1 ключей Км..., К„превосходят э. (Напомню, что сортируемые в наших примерах ключи— целые числа (1,2,...,Ю).) Если э = 1, то нетрудно видеть, что произойдет во время первой итерации разделения.
Шаг ЯЗ вьшолннтся однократно, шаг Я4 -- Х раз, а шаг цб приведет нас к шагу Я7. Таким образом, "взнос" первой итерации в анализируемые параметры будет следующим: А = 1, В = О, С = Х + 1. Аналогичные, но несколько более сложные рассуждения для случая э > 1 (см. упр. 21) показывают, что взнос первой итерации в суммарное время выполнения в общем случае будет составлять (17) А = 1, В = Х, С = Х+ 1 для 1 < э < Ю К этому необходимо добавить вклады последующих итераций, во время которых упорядочиваютсл подмассивы из э — 1 и Х вЂ” э элементов соответственно.
Если предположить, .что в исходной последовательности записи располагались в случайном порядке, то можно выписать формулы, которыми определяются производящие функции для распределений вероятностей величин А, В,...,5 (см. упр. 22). Но для простоты рассмотрим здесь только средние значения этих величин Ач, Вл,..., Ял как функции от Х Рассмотрим, например, среднее число сравнений Стб выполненпьгх в процессе разделения. Если Х ( ЛХ, то Сл = О.
В противном случае, поскольку любое данное значение в встречается с вероятностью 1/Ф, получим М Сл = — ~~~ (У+1+С ~+Си ) в=1 = И+1+ — ~~> Сь для Ю > М. 2 Н (1В) О«я<И Аналогичные формулы имеют место и для остальнык величин Ал, Ву, .Увь Е~д, Бм (см. упр. 23). Существует простой способ решения рекуррентнык соотношений вида 2 х„= у„+ — у хь для и > та.
н е<ь< (19) Ка первом шаге нужно освободиться от знака суммирования: поскольку (и+1)х„+~ =(и+1)У„~~+2 ~Ч~ хю в<в<в пх„= пУ„+ 2 "~, хь, ебь<ч можно вычесть второе равенство из первого, получив (и + 1)хп+1 — нхь = дв + 2хь~ где дв = (н+ 1)Уи+1 — п~л. Теперь рекуррентная зависимость принимает гораздо более простой вид: (и+ 1)х„„= (и+ 2) х„+ д„д и > Любое рекуррентное соотношение общего вида а„х„ь~ =6„х„+д„ можно свести к простой сумме, если умножить обе части на "суммирующий множи- тель" аз а~...а . ~/Ьв6г...6„.
Получаем оо."а~-~ оо-- о -~ у„.ь~ = д„+ с„, где у„= — х„, с„= д„. (22) 6..6„, ' 6,6,...6„"' х„~.~ х„(п + 1)~„.ь~ — п~„ — — — + для и > гп и+2 и+1 (и+1)(и+2) (2З) является следствием соотношения (19). Если, например, положить у„= 1/н, то получится неожиданный результат: х„/(и + Х) = х,„Дгп + 1) при любом н > ш. Если положить у„= н + 1, получится х„/(и+1) = 2/(н+ Ц+ 2/и+- + 2/(гп+ 2) +х„,/(гп+ 1) = 2(Н .ь~ — Н .ьг) +х /(гп+1) Для (20) суммирующий множитель равен просто нфя+2)! = 1/(о+1)(и+2).
Таким образом, находим, что простое соотношение при любом и > гп. Таким образом получим решение для (18), подставив т = М + 1 и х„= 0 при и < М; искомая формула имеет вид Сл = (Ю + 1) (2ни+1 — 2нм ~э + 1) ш 2(Я+1) (п1 — ) /Л'+11 1,М+ 2) (24) В упр. 6.'2.2-8 будет доказано, что при М = 1 стандартное отклонение величины Сл р~ ° ди-'ь~узю. э ~ * е * с (24). Остальные величины можно найти аналогичным способом (см. упр. 23); при Ф > М имеем Аи =2(Н+ 1)/(М+2) — 1, / 6 '1 1 В, = - (Н+ Ц ~2Н .„- 2Н +, + 1 — — ~ + -, 6 М+ 2) 2' Вь = (Х + 1) (1 — 2Нмэп/(М + 2)), в.
= -'. ( + ) (м - )/(м+ ); В„= (Л'+ 1)/(2М+ 3) — 1 д Л' > 2М+1. (25) Из приведенных выше соображений следует, что можно точно проанализировать среднее время выполнения весьма сложной программы, используя методы, которые мы ранее применяли в более простых случаях. Чтобы определить наилучшее значение М для конкретного компьютера, можно воспользоваться формулами (24) н (25). При Ф > 2М+ 1 выполнение программы Я на компьютере И11 требует в среднем (35/3)(Ф + 1)Ни ы + ф(Ю+ 1)/(М) — 34.5 машинных циклов, где /(М) = 8М вЂ” 70Нмьт + 71 — 36 — + — + . (26) Нм+1 270 54 М+2 М+2 2М+3' Желательно выбрать такое значение М, при котором функция /(М) достигает минимума. Несложные рассуждения приводят нас к такому результату: М = 9.
При этом для больших Ю среднее время выполнения программы Я равно приблизительно 11.667(Ю1+) )пХ вЂ” 1.74Н вЂ” 18.74 машинных циклов. Таким образом, программа Я работает в среднем довольно быстро; следует, кроме того, учесть, что она требует очень мало памяти. Высокая скорость определяется„в первую очередь, тем, что внутренний цикл — шаги ЯЗ и Я4 — очень короток (см.
строки 12-14 и 15-17 текста программы). Количество операций обмена записей в памяти на шаге Цб составляет всего около 1/6 количества сравнений на шагах ЯЗ и Я4; к тому же мы очень много экономим вследствие того, что отпала необходимость в сравнении 1 с у во внутреннем цикле. Но каков наихудший случай для алгоритма Я? Существуют ли какие-нибудь исходные файлы, обрабатывать которые с помощью этого алгоритма не эффективно? Ответ несколько обескураживает: если исходный файл уже упорядочен, а именно— Кг < из « Кл, то каждая операция "разделения" становится почти бесполезной, так как она уменьшает размер подмассива всего лишь на один элемент! Значит, в этой ситуации (которая должна быть самой простой для сортировки) быстрая сортировка превращается в отнюдь не быструю.
Время ее работы становится пропорциональным !э", а не К !8 А(см. упр. 25). В отличие от других алгоритмов сортировки, которые нам встречались, алгоритм !4 предпочитает неупорядоченные файлы! В упомянутой статье Хоара предложены два способа устранения этого недостатка. Они базируются на выборе лучшего значения проверяемого ключа К, который управляет разделением. Одна нз его рекомендаций состоит в том, чтобы в последней части шага ь)2 выбрать случайное целое число д в диапазоне между ! и г. На этом шаге можно заменить команды выполнения операций К ~- К~ операциями К +- К„Л +- Лю Лэ <- Ль Л~ ~- Л. (27) (Последняя операция присваивания необходима, поскольку в противном случае на шаге (44 произойдет прекращение цикла с сохранением у = ! — 1, если К есть наименьший ключ в разделяемом подмассиве.) Согласно формулам (25) такие случайные целые числа придется вычислять в среднем лишь 2 (Ю + 1)ДМ + 2) — 1 раз, так что дополнительные расходы несущественны, а случайный выбор — хорошая защита от возможности оказаться в наихудшей ситуации.
Даже "слабая"' случайность в выборе д может служить достаточной защитой. В упр. 58 доказано., что при действительно случайном значении д появление более чем 20А!!пЖ сравнений возможно с вероятностью, меньшей 10 э. Второе предложение Хоара состоит в просмотре небольшого фрагмента сортируемой последовательности н нахождении медианы для этой совокупности данных. Такому подходу последовал Р. К. Синглтон (см. В,. С. Бп 8!егоп, САСМ 12 (1969), 185-187), который предложил в качестве К, брать медиану трех значений: (28) Процедура Синглтона сокращает число сравнений с 2А' !и Х примерно до '~ У !и Ж (см. упр. 29).
Можно показать, что в этом случае Вл асимптотическн приближается к Слаб, а не к Сл /6, так что метод медианы несколько увеличивает время, затрачиваемое на пересылку данных. В результате общее время работы сокращается примерно на 8%. (Подробный анализ приводится в упр. 56.) Время работы в наихудшем случае все еще составляет порядка Ю~, однако с таким случаем вряд ли когда-либо придется сталкиваться на практике. У.
Д. Фрэйзер и А. Ч. МакКеллар (см. %. П. Ргахег апг! А. С. МсКейаг, Х4СМ 17 (1970), 496-507) предложили рассматривать совокупность гораздо большего объема из 2ь — 1 записей, где й выбирается так, чтобы 2ь я~ Ф/!пК. Эту совокупность можно рассортировать обычным методом быстрой сортировки, после чего элементы расположить среди остальных записей за Й просмотров всего массива (в результате массив записей будет разделен на 2ь подмассивов, ограниченных элементамн выборки). На заключительном этапе сортируютгл полученные подмассивы. г''спи Ю находится в реальном диапазоне значений, то среднее число сравнений, выполняемых такой процедурой "сортировки выборки", примерно такое же, как и для метода медианы Синглтона, но при Ю -+ оо оно асимптотически приближается к Ф !8 Ю. Метод, который даст абсолютную гарантию того, что в худшем случае время сортировки будет составлять порядка 0(К !оба) н одновременно будет обеспечена высокая скорость в среднем, можно получить, комбинируя метод быстрой сорти- ровки с некоторыми другими схемами.
Например, Д. Р. Муссер (см. В. Н. Мпээег Яоггн аге Ргасг1се Зг Ехрег. 27 (1997), 983-993) предложил ввести в каждый элемент стека быстрой сортировки еще и компонент "глубина разделения". Если найден подмасснв, который разделен более чем, скажем, 218Ф раз, предлагается прекратить выполнение алгоритма Ц н переключиться на алгоритм 5.2.3Н. В таком случае сохраняется то же время выполнения внутреннего цикла, а следовательно, и среднее время выполнения сортировки. Роберт Седгевик проанализировал множество оптимизированных вариантов быстрой сортировки в Асга 1югоггюабса 7 (1977), 327-356, и в САСМ 21 (1978), 847 — 857, 22 (1979), 368.
Версии быстрой сортировки, включенные в библиотеку программ 1ЛЧ1Х~, которая создавалась в течение 15 лет, описана в работе Л, 1,. Вепг1еу апб М. П. МсПгоу, Яойвиге Ргасг1се Зг Ехрег. 23 (1993), 1249-1265. Обменная поразридиаи сортировка. Рассмотрим метод, совершенно отличный от всех схем сортировки, которые описывались до сих пор. В нем используется двоичное иредсшаеление ключей, и потому он предназначен только для двоичных компьютеров. Вместо того чтобы сравнивать между собой два ключа, в этом методе проверяется, равны ли О или 1 отдельные разряды ключа.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
