при любом п > т. Таким образом получим решение для (18), подставив ш = М + 1 и а;„ = О при п < М; искомая формула имеет вид

Cn = {N + 1) {2Hn+i - 2Нм+2 + 1)

« 2 (iV + 1) In () для N>M. (24)

В упр. 6.2.2-8 будет доказано, что при М = 1 стандартное отклонение величины Cjv асимптотически приближается к у(21 - 2ir)/3N. Это довольно мало по сравнению с (24).

Остальные величины можно найти аналогичным способом (см. упр. 23); при N > М имеем

Л = 2(ЛГ+1)/(М + 2)-1,

Bn = \{N + 1) (2Нм+, - 2Нм+2 + 1 - + i,

dn = iN + l){l-2HM+i/{M + 2)), En = 1{N + 1)М{М - 1)/{М + 2);

Sn = {N+ 1)/{2М+ 3)-I дляЛГ>2М + 1. (25)

Из приведенных выше соображений следует, что можно точно проанализировать среднее время выполнения весьма сложной программы, используя методы, которые мы ранее применяли в более простых случаях.

Чтобы определить наилучшее значение М для конкретного компьютера, можно воспользоваться формулами (24) и (25). При N > 2М + 1 выполнение программы Q на компьютере MIX требует в среднем (35/3)(iV -t- 1)Hn+i + (- + - 34.5

машинных циклов, где

/М=Ш-70Я„«н.71-36§ + +51:з. (26)

Желательно выбрать такое значение М, при котором функция /(М) достигает минимума. Несложные рассуждения приводят нас к такому результату: М = 9. При этом для больших N среднее время выполнения программы Q равно приблизительно 11.667(iVl--) IniV - 1.74iV - 18.74 машинных циклов.

Таким образом, программа Q работает в среднем довольно быстро; следует, кроме того, учесть, что она требует очень мало памяти. Высокая скорость определяется, в первую очередь, тем, что внутренний цикл - шаги Q3 и Q4 - очень короток (см. строки 12-14 и 15-17 текста программы). Количество операций обмена записей в памяти на шаге Q6 составляет всего около 1/6 количества сравнений на шагах Q3 и Q4; к тому же мы очень много экономим вследствие того, что отпала необходимость в сравнении г с j во внутреннем цикле.

Но каков наихудший случай для алгоритма Q? Существуют ли какие-нибудь исходные файлы, обрабатывать которые с помощью этого алгоритма не эффективно? Ответ несколько обескураживает: если исходный файл уже упорядочен, а именно - Ki < К2 < • < Kn, то каждая операция "разделения" становится почти бесполезной, так как она уменьшает размер подмассива всего лишь на один элемент! Значит,

в этой ситуации (которая должна быть самой простой для сортировки) быстрая сортировка превращается в отнюдь не быструю. Время ее работы становится пропорциональным N, а не NlgN (см. упр. 25). В отличие от других алгоритмов сортировки, которые нам встречались, алгоритм Q предпочитает неупорядоченные файлы!

В упомянутой статье Хоара предложены два способа устранения этого недостатка. Они базируются на выборе лучшего значения проверяемого ключа К, который управляет разделением. Одна из его рекомендаций состоит в том, чтобы в последней части шага Q2 выбрать случайное целое число q в диапазоне между I и г. На этом шаге можно заменить команды выполнения операций К <- Ki операциями

К i-Kg, RRq, RqRi, Ri-R. (27)

(Последняя операция присваивания необходима, поскольку в противном случае на шаге Q4 произойдет прекращение цик.ла с сохранением j = I - I, если К есть наименьший ключ в разделяемом подмассиве.) Согласно формулам (25) такие случайные целые числа придется вычислять в среднем лишь 2{N +1)1 {М -ь 2) - 1 раз, так что дополнительные расходы несущественны, а случайный выбор - хорошая защита от возможности оказаться в наихудшей ситуации. Даже "слабая" случайность в выборе q может служить достаточной защитой. В упр. 58 доказано, что при действительно случайном значении q появление более чем 20iVlniV сравнений возможно с вероятностью, меньшей 10~.

Второе предложение Хоара состоит в просмотре небольшого фрагмента сортируемой последовательности и нахождении медианы для этой совокупности данных. Такому подходу последовал Р. К. Синглтон [см. R. С. Singleton, САСМ 12 (1969), 185-187], который предложил в качестве Kq брать медиану трех значений:

Ki, A(,+,)/2j, Кг. (28)

Процедура Синглтона сокращает число сравнений с 2N\nN примерно до iVlniV (см. упр. 29). Можно показать, что в этом случае асимптотически приближается к Civ/5, а не к Сдг/б, так что метод медианы несколько увеличивает время, затрачиваемое на пересылку данных. В результате общее время работы сокращается примерно на 8%. (Подробный анализ приводится в упр. 56.) Время работы в наихудшем случае все еще составляет порядка №, однако с таким случаем вряд ли когда-либо придется сталкиваться на практике. У. Д. Фрэйзер и А. Ч. Мак-Келлар [см. W. D. Frazer and А. С. McKellar, JACM 17 (1970), 496-507] предложили рассматривать совокупность гораздо большего объема из 2* - 1 записей, где к выбирается так, чтобы 2* и N/ In N. Эту совокупность можно рассортировать обычным методом быстрой сортировки, после чего элементы расположить среди остальных записей за к просмотров всего массива (в результате массив записей будет разделен на 2* подмассивов, ограниченных элементами выборки). На заключительном этапе сортируются полученные подмассивы. Если N находится в реальном диапазоне значений, то среднее число сравнений, выполняемых такой процедурой "сортировки выборки" примерно такое же, как и для метода медианы Синглтона, но при N оо оно асимптотически приближается к NlgN.

Метод, который даст абсолютную гарантию того, что в худшем случае время сортировки будет составлять порядка О {NlogN) и одновременно будет обеспечена высокая скорость в среднем, можно получить, комбинируя метод быстрой сорти-

ровки с некоторыми другими схемами. Например, Д. Р. Муссер [см. D. R. Musser Software Practice &: Exper. 27 (1997), 983-993] предложил ввести в каждый элемент стека быстрой сортировки еще и компонент "глубина разделения" Если найден подмассив, который разделен более чем, скажем, 21giV раз, предлагается прекратить выполнение алгоритма Q и переключиться на алгоритм 5.2.3Н. В таком случае сохраняется то же время выполнения внутреннего цикла, а следовательно, и среднее время выполнения сортировки.

Роберт Седгевик проанализировал множество оптимизированных вариантов быстрой сортировки в Acta Jnformatica 7 (1977), 327-356, и в САСМ 21 (1978), 847-857, 22 (1979), 368. Версии быстрой сортировки, включенные в библиотеку программ UNIX®, которая создавалась в течение 15 лет, описана в работе J. L. Bentley and М. D. Mcllroy, Software Practice & Exper. 23 (1993), 1249-1265.

Обменная поразрядная сортировка. Рассмотрим метод, совершенно отличный от всех схем сортировки, которые описывались до сих пор. В нем используется двоичное представление ключей, и потому он предназначен только для двоичных компьютеров. Вместо того чтобы сравнивать между собой два ключа, в этом методе проверяется, равны ли О или 1 отдельные разряды ключа. В других отношениях он обладает характеристиками обменной сортировки и на самом деле очень напоминает быструю сортировку. Так как метод использует разряды ключа, представленного в двоичной системе счисления, назовем его обменной поразрядной сортировкой. В общих чертах этот алгоритм можно описать следующим образом.

i) Последовательность сортируется по старшему значащему двоичному разряду так, чтобы все ключи, начинающиеся с О, оказались перед всеми ключами, начинающимися с 1. Для этого необходимо найти крайний слева ключ Ki, начинающийся с 1, и крайний справа ключ Kj, начинающийся с О, после чего Ri и Rj поменяются местами, и процесс будет повторяться, пока не получится i > j.

ii) Пусть Fo - множество э.леменгов, начинающихся с О, а fi - множество всех остальных элементов. Будем применять к Fq поразрядную сортировку (начав теперь со второго бита слева, а не со старшего) до тех пор, пока множество Fq полностью не рассортируется. Затем проделаем то же самое с Fi.

Например, в табл. 3 по1сазано, как действует обменная поразрядная сортировка на наши 16 случайных чисел, записанных теперь в восьмеричной системе счисления. В строке итерации 1 показан исходный массив; после обменов по первому биту приходим ко второй итерации. На второй итерации сортируется первая группа по второму биту, на третьей - по третьему биту. (Читатель должен мысленно преобразовать восьмеричные числа в 10-разрядные двоичные. Например, 0232 в двоичном коде будет равно (0 010 011010)2.) Достигнув после сортировки по четвертому биту пятой итерации, обнаруживаем, что в каждой из оставшихся групп содержится всего по одно.му элементу, так что эту часть массива можно больше не рассматривать. Запись "Ч0232 0252] означает, что подмассив 0232 0252 еще предстоит сортировать по четвертому биту слева. В этом конкретном случае сортировка по четвертому биту не дает ничего нового; чтобы разделить элементы, необходимб добраться до пятого бита.

Весь процесс сортировки, показанный в табл. 3, выполняется за 22 итерации; это несколько больше соответствующего значения при быстрой сортировке (см. табл. 2).