Время работы программы обменной поразрядной сортировки зависит от следующих показателей:

А - число итераций, в которых I < г;

В - число операций обмена записей;

С = С + С" - число проверок разрядов;

G - число случаев, когда Ь > m на шаге R8;

К - число случаев, когда b < т, j = I на. шаге R8; (29)

L - число случаев, когда b < т, j < I на шаге R8; R - число случаев, когда b < т, j = г на шаге R8; S - число случаев, когда что-либо помещается в стек;

X - число случаев, когда j < i на шаге R6.

По закону Кирхгофа 5 = A-G-K-L-R, так что общее время выполнения равно 27А + 8В + 8С - 23G - UK - 17L - 19R - X + 13 машинных циклов. За счет усложнения программы можно несколько ускорить циклы проверки разрядов (см. упр. 34). Обменную поразрядную сортировку можно также ускорить, если при достаточно малых значениях разности г - I применять простые вставки, как это сделано в алгоритме Q, но мы не будем задерживаться на таких усовершенствованиях. Проанализируем время выполнения обменной поразрядной сортировки в двух случаях, которым соответствуют разные наборы условий.

i) Пусть 7V = 2™ и ключи, которые следует рассортировать, - просто числа О, 1, 2, ..., 2™ - 1, расположенные в случайном порядке.

ii) Пусть m = оо (неограниченная точность) и ключи, которые необходимо рассортировать, - независимые, равномерно распределенные в промежутке [О.. 1) действительные числа.

Анализ случая (i) относительно прост, поэтому он оставлен читателю в качестве упражнения (см. упр. 35). Случай (ii) более сложен, но его мы также оставили для упражнений. В следующей таблице приведены грубые оценки результатов анализа в том и другом случаях.

(30)

Здесь a = 1/1п2 и 1.4427. Заметим, что среднее число обменов, проверок разрядов и обращений к стеку, по существу, одинаково в обоих случаях, несмотря даже на то, что в случае (ii) число итераций на 44% больше. На сортировку N элементов в случае (ii) наша MIX-программа затратит в среднем приблизительно lAANlnN машинных циклов. Это число можно сократить примерно до ll.STVlniV, если воспользоваться предложением из упр. 34. Соответствующая величина для программы Q равна 11.7 7Vln7V, но и ее можно уменьшить до lO.GTVlnTV, если воспользоваться предложением Синглтона и выбрать медиану из трех ключей.

В случае равномерного распределения данных обменная поразрядная сортировка отнимает в среднем примерно столько же времени, сколько и быстрая сортировка; на некоторых компьютерах она выполняется немного быстрее, чем быстрая сортировка. В упр. 53 показано, в какой мере замедляется этот процесс при неравномерном распределении. Важно отметить, что весь наш анализ основан на предположении о том, что все ключи различны. Обменная поразрядная сортировка в таком виде, как описано выше, не очень эффективна, если имеются одинаковые ключи, поскольку она проходит через несколько итераций, каждая из которых требует определенного времени для разделения множества одинаковых ключей до тех пор, пока b не станет > т. Один приемлемый способ исправления этого недостатка предложен в ответе к упр. 40.

Как обменная поразрядная сортировка, так и быстрая сортировка основаны на идее разбиения. Записи меняются местами до тех пор, пока массив не будет разбит на две части: левый подмассив, в котором все ключи < К при определенном К, и правый подмассив, в котором все ключи > К. При быстрой сортировке в качестве К выбирается реальный ключ из массива, в то время как при обменной поразрядной сортировке, по существу, выбирается некоторый искусственный ключ на основе двоичных представлений. Что касается исторической стороны дела, то обменную поразрядную сортировку открыли П. Хильдебрандт, Г. Исбитц, X. Райзинг и Ж. Шварц [см. Р. Hildebrandt, Н. Isbitz, Н. Rising, J. Schwartz, JACM 6 (1959), 156-163] примерно за год до изобретения быстрой сортировки. Существуют и другие схемы разделения; например, Джон Мак-Карти (John McCarthy) предложил выбирать К и {u+v), если известно, что все ключи находятся в диапазоне между и и v.

Еще одну стратегию разделения предложил М. X. ван Эмден (М. Н. van Emden) [САСМ 13 (1970), 563-567]: вместо того чтобы выбирать К заранее, мы "узнаем"

каким может быть хорошее значение К, отслеживая в процессе разделения изменение величин К = max.{Ki,Ki) и К" = min{Kj,Кг). Можно увеличивать г до тех пор, пока не встретится ключ, больший К, а затем начать уменьшать j, пока не встретится ключ, меньший К", после чего поменять их местами и/или уточнить значения К и К". Эмпирические тесты этой "интервальной сортировки с обменом" показывают, что она осуществляется несколько медленнее, чем быстрая, а теоретический анализ выполнить очень сложно. В значительной мере затруднение во время анализа вызывает тот факт, что записи в подмассивах после разделения уже нельзя считать размещенными в случайном порядке. Это единственный метод, обсуждаемый в данной книге, для поведения которого еще не найдено адекватного теоретического объяснения.

Обобщение обменной поразрядной сортировки для системы счисления с основанием, большим 2, обсуждается в разделе 5.2.5.

♦Асимптотические методы. Анализ алгоритмов обменной сортировки приводит к некоторым особенно поучительным математическим задачам, которые позволяют больше узнать о способах определения асимптотического поведения функции. Например, при анализе метода пузырька [формула (9)] мы столкнулись с функцией

- = h

0<r<s<n

Какой вид имеет асимптотическое выражение для этой функции?

Можно действовать так же, как при исследовании числа инволюций [формула 5.1.4-(41)]. Поэтому, прежде чем двигаться дальше, полезно еще раз просмотреть материал, изложенный в конце раздела 5.1.4. Исследование формулы (31) показывает, что вклад при s = п больше, чем вклад при s = п - 1 и т. д. Это наводит на мысль о замене s на п - s. Мы скоро увидим, что на самом деле удобнее всего применить подстановки t = n- s + l,m = n+l,B результате которых формула (31) примет вид

>- = ii е (m-ty. е г-- (32)

1<«т 0<r<m-t

Для внутренней суммы существует хорошо известный асимптотический ряд, полученный из формулы суммирования Эйлера:

= 7 е (*) Л- - Stj) + 0(7V-=) (33)

(см. упр. 1.2.11.2-4). Следовательно, наша задача сводится к анализу сумм вида

л У" (m-t)!(m-t)t fc>-l. (34)

1<«т

Как и в разделе 5.1.4, можно показать, что при значениях t, больших т/+, члены суммы пренебрежимо малы: 0(ехр(-п)). Значит, можно положить t = 0(m/+) и заменить факториалы по формуле Стирлинга: