53. [НМ42] Проанализируйте число проверок разрядов и число обменов, выполняемых при обменной поразрядной сортировке, если исходными данными служат двоичные числа с бесконечной точностью в диапазоне [О .. 1), каждый разряд которых независимо принимает значение 1 с вероятностью р. (В основном тексте раздела обсуждался лишь случай, когда р = ; применявшиеся методы можно обобш;ить для произвольного р.) Рассмотрите особо случай, когда р = 1/ф - .61803 ....

54. [НМ24] (С. О. Райе (S. О. Rice).) Покажите, что U„ можно записать в виде

dz 1

Тс z(z-l)...(z-n) 2-1-1

где С - замкнутая кривая, охватывающая область около точек 2,3,... ,7г. В результате замены С произвольно большой окружностью с центром в начале координат получаем сходящийся ряд

= ПЙ - i + 2 + 1i2 е » (-("+1-

т>1

где 6 = 27г/1п2 и В{п+1, -1+гЬт) = Г(71+1)Г(-1+гб77г)/Г(п+гб77г) = п\/Uoi-l+ibm).

► 55. [22] Покажите, как нужно изменить программу Q, чтобы в качестве разделяющего элемента выбиралась медиана из трех ключей (28), полагая М > 1.

56. [Af.5] Проанализируйте поведение в среднем параметров, от которых зависит время работы программы Q, если программа изменена так, что она выбирает медиану из трех элементов, как в упр. 55 (см. упр. 29).

5.2.3. Сортировка посредством выбора

Еще одно важное семейство методов сортировки основано на идее многократного выбора. Вероятно, простейшая сортировка посредством выбора сводится к следующему.

i) Найти наименьший ключ, переслать соответствуюшую запись в область вывода и заменить ключ значением оо (которое по предположению больше любого реального ключа).

ii) Повторить шаг (i). На этот раз будет выбран ключ, наименьший из оставшихся, так как ранее наименьший ключ был заменен значением оо.

Ш) Повторять шаг (i) до тех пор, пока не будут выбраны N записей.

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

На шаге (i) требуется выполнить N-1 сравнений каждый раз, когда выбирается очередная запись. Также необходимо выделить в памяти отдельную область для накопления результата. Имеется очевидный способ несколько поправить ситуацию: выбранное значение записать в соответствующую окончательную позицию, а запись, которая ее занимала, перенести на место выбранной. Тогда эту позицию не нужно будет рассматривать вновь при последующих выборах и не придется иметь дело с ключом бесконечно большой величины. На этой идее основан наш первый алгоритм сортировки посредством выбора.

SI. Цикл по j

N>j>2

S2. Найти max{Ki,...,Kj)

S3. Обмен с Ri

Рис. 21. Сортировка посредством простого выбора.

Алгоритм S {Сортировка посредством простого выбора). Записи Ri,..., Rm перекомпоновываются в пределах того же фрагмента памяти. После завершения сортировки их ключи будут упорядочены: Ki < < К. Сортировка базируется на описанном выше методе, если не считать того, что более удобно, оказывается, сначала выбирать наибольший элемент, затем - второй по величине и т. д. (рис. 21).

51. [Цикл по j.] Вьшолнить шаги S2 и S3 при j = N,N - 1,... ,2.

52. [Найти max(iii,...,Kj).] Найти наибольший из ключей Kj,Kj-i,. ..,Ki; пусть это будет Ki, где г выбирается как можно большим.

53. [Поменять.местами с Rj.] Взаимно переставить записи Ri i+ Rj. (Теперь записи Rj,..., Rn занимают свои окончательные позиции.)

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

Таблица 1

СОРТИРОВКА ПОСРЕДСТВОМ ПРОСТОГО ВЫБОРА

503 087 512 061

503 087 512 061

503 087 512 061

503 087 512 061

503 087 512 061

503 087 512 061

908 170 897 275 653 426 154 509 612 677 765 703

703 170 897 275 653 426 154 509 612 677 765908

703 170 765 275 653 426 154 509 612 677897 908

703 170 677 275 653 426 154 509 612765 897 908

612 170 677 275 653 426 154 509[703 765 897 908

612 170 509 275 653 426 154677 703 765 897 908

0611087 154 170 275 426 503 509 512 612 653 677 703 765 897 908

Соответствующая MIX-программа довольно проста.

Программа S {Сортировка посредством простого выбора). Как и в предыдущих программах из этой главы, записи, находящиеся в ячейках от INPUT+1 до INPUT+N, сортируются в пределах того же фрагмента памяти по ключу, который занимает полное слово. Значения регистров таковы: гА = текущий максимум, гП = j - 1, г12 = к (индекс при поиске), г13 = г. Предполагается, что N >2.

01 START ENT1 N-1 1 Si. Яикл по .? +- N.

02 2Н ENT2 0,1 N-1 S2. Найти maxfX,.....Kj). k<-i-l.

03 ENT3 1,1 N-1 iij.

04 LDA INPUT,3 N-1 lA i-Ki.

Переход, если Ki> Кк-Иначе -- установить igetsk,

гА <- Ki. к<-к-1.

Повторить, если А; > 0. S3. Поменять местами с Ri. RiRj. Rj гА.

N>j>2. I

Время работы этой программы зависит от числа элементов ЛГ, числа сравнений А и числа правосторонних максимумов В. Нетрудно видеть, что независимо от значений исходных ключей

a=[) = In{n-i). (1)

Следовательно, переменной является только величина В. Несмотря на всю безыс-кусность простого выбора, не так-то легко выполнить точный анализ величины В. В упр. 3-6 показано, что

В = (min О, ave {N + 1)Hn- 2N, max [N4]). (2)

В этом случае особенно интересным оказывается максимальное значение. Стандартное отклонение величины В имеет порядок N/ (см. упр. 7).

Таким образом, среднее время работы программы S равно 2.5N -ь 3(iV-- 1)Ялг + 3.5N - 11 машинных циклов, т. е. данная программа работает лишь немногим медленнее програ.ммы, реализующей метод простых вставок (программа 5.2.IS). Интересно сравнить алгоритм S с сортировкой методом пузырька (алгоритм 5.2.2В), поскольку метод пузырька можно рассматривать как алгоритм выбора, в котором за один раз иногда выбирается более одного элемента. По этой причине при сортировке методом пузырька выполняется меньше сравнений, чем при простом выборе, и она, как может показаться, предпочтительнее. Но в действительности программа 5.2.2В работает более чем вдвое медленнее программы S! Сортировка методом пузырька проигрывает йз-за того, что выполняется слишком много обменов, в то время как при сортировке посредством простого выбора пересылается очень мало данных.

Усовершенствования простого выбора. Существует ли какой-нибудь способ улучшения метода выбора, используемого в алгоритме S? Возьмем, к примеру, поиск максимума на шаге S2: возможен ли существенно более быстрый способ нахождения максимума? Ответ на этот вопрос - мет!

Лемма М. В любом алгоритме нахождения максимума среди п элементов, основанном на сравнении пар элементов, необходимо выполнить, по крайней мере, п - 1 сравнений.

Доказательство. Если выполнено менее п-1 сравнений, то найдутся хотя бы два элемента, для которых не было обнаружено ни одного элемента, превосходящего их по величине. Следовательно, мы так и не узнаем, какой из этих двух элементов больше, а значит, не сможем определить максимум.