на основе аналогичных предположений (программы 5.2.1М и 5.2.4L), говорит явно в пользу программы R. Время выполнения р-проходного варианта программы R равно {lip - 1)N + 0{рМ) машинных циклов; критический фактор, влияющий на время выполнения, - внутренний цикл, который содержит пять обращений к памяти и один переход. Для типичного компьютера М = Ь ир- [</г], где t - число цифр в ключах, представленных в системе счисления с основанием Ь. С ростом г убывает р, так что можно воспользоваться нашими формулами для определения "наилучшего" значения г.

Единственная переменная величина в формуле для времени выполнения - это Е (число пустых стопок, обнаруженных на шаге Н4). Предположим, что все последовательностей цифр М-ичной системы счисления равновероятны. При анализе "покер-теста" в разделе 3.3.2D было показано, как вычислять вероятность того, что при каждом просмотре встретится ровно М - г пустых стопок. На каждом проходе она равна

М(М-1) ... {M-r + l)(N\

--Irl

где {} - число Стирлинга второго рода. Согласно упр. 5

Е= min max(M - iV, 0)р, ave -(l"]) ™ -)P

В последние годы появляется все больше компьютеров с конвейерной (pipeline) и магистральной (number-crunching) архитектурами. Эти машины имеют несколько арифметических устройств и схему "опережения" так что обращения к памяти и вычисления могут в значительной степени совмещаться во времени. Но эффективность таких компьютеров заметно снижается при наличии условных переходов, если только эти переходы не происходят почти всегда в одном и том же направлении. Внутренний цикл поразрядной сортировки хорошо приспособлен для таких машин, поскольку это простое итеративное вычисление - типичное "пережевывание чисел" Поэтому для компьютеров с магистральной архитектурой метод поразрядной сортировки обычно является наиболее эффективным из всех известных методов внутренней сортировки при условии, что N не слишком мало и ключи не слишком длинные.

Разумеется, если ключи уж очень длинные, поразрядная сортировка не так эффективна. Представьте себе, например, что нужно рассортировать бО-разрядные десятичные числа за 20 проходов поразрядной сортировки, используя М = 10. Очень мало пар чисел будет иметь одинаковые ключи в первых 9 разрядах, так что первые 17 проходов выполнятся почти впустую. При анализе обменной поразрядной сортировки мы обнаружили, что вовсе необязательно проверять много битов ключей, если просматривать их не справа налево, а слева направо. Поэтому давайте возвратимся к поразрядной сортировке, при которой ключи просматриваются, начиная со старших цифр (СЦ), а не с младших цифр (МЦ).

Мы уже отмечали, что идея СЦ-поразрядной сортировки приходит в голову естественным образом. В самом деле, нетрудно понять, почему при сортировке почты в отделениях связи пользуются именно этим методом. Большое количество писем можно рассортировать по отдельным мешкам, соответствующим географическим областям. Теперь в каждом мешке содержится меньше писем, которые

можно независимо рассортировать по другим мешкам, соответствующим все более мелким районам. (Разумеется, прежде чем продолжить сортировку писем, их можно переправить поближе к месту назначения.) Принцип "разделяй и властвуй" весьма привлекателен, и единственная причина его непригодности для сортировки перфокарт состоит в том, что большое количество стопок приводит к путанице. Этим же явлением объясняется относительная эффективность алгоритма R (хотя здесь предпочтение отдается анализу, начатому с младших разрядов), потому что никогда не приходится работать более чем с М стопками и стопки приходится сцеплять всего р раз. С другой стороны, нетрудно построить СЦ-поразрядный метод с помощью связного распределения памяти с отрицательными связями для обозначения границ между стопками, как в алгоритме 5.2.4L (см. упр. 10). Пожалуй, наилучший компромиссный выход указал М. Д. Мак-Ларен (М. D. MacLaren) [JACM 13 (1966), 404-411], который предложил использовать МЦ-сортировку, как в алгоритме R, но в применении к старшим разрядам. Это не будет полной сортировкой массива, но в результате массив станет почти упорядоченным, т. е. в нем останется очень мало инверсий, так что для завершения сортировки можно будет воспользоваться методом простых вставок. Наш анализ программы 5.2.1М применим и к этой ситуации; если ключи распределены равномерно, то после сортировки массива по старшим р цифрам в нем останется в средне.м \N{N - 1)М~ инверсий [см. формулу 5.2.1-(17) и упр. 5.2.1-38]. Мак-Ларен вычислил среднее число обращений к памяти, приходящихся на один обрабатываемый элемент, и оказалось, что оптимальный выбор значений М и р (в предположении, что М - степень двойки, ключи равномерно распределены и N/M < 0.1, так что отклонения от равномерного распределения приемлемы) описывается следующей таблицей.

Здесь P{N) - среднее число обращений к памяти на один сортируемый элемент

эта величина ограничена при -> оо, если взять р = 2 я М > \/]V, так что среднее время сортировки - 0{N), а не NlogN. Данный метод является усовершенствованным вариантом метода вставок в несколько списков (программа 5.2.1М), который, по существу, представляет собой случай р = 1. В упр. 12 приводится интересная процедура Мак-Ларена для окончательной перекомпоновки записей после частичной сортировки массива с помощью списков.

Если воспользоваться методами из алгоритма 5.2D и упр. 5.2-13, то можно обойтись без полей связи; при этом в дополнение к памяти, занятой самими записями, потребуется всего 0(\/]v) ячеек. Если исходные данные распределены равномерно, то среднее время сортировки пропорционально N.

В. Добосевич (W. Dobosiewicz) получил хороший результат при использовании СЦ-сортировки в отношении массивов значительной длины. Процесс распределения был построен таким образом, что для первых М/2 стопок гарантировалось получе-

ние от 25 до 75% всех записей [см. Inf. Ргос. Letters 7 (1978), 1-6; 8 (1979), 170-172]. В результате среднее время сортировки равномерно распределенных ключей оказалось порядка 0{N), но для наихудшего случая время будет составлять порядка 0{N log N). Указанная статья побудила других исследователей разработать новые алгоритмы вычисления адресов, из которых наиболее удачной оказалась следующая двухуровневая схема, предложенная Маркку Тамминеном (Markka Tamminen) [J. Algorithnis 6 (1985), 138-144]. Предположим, что все ключи являются дробями из интервала [0..1). Сначала распределим N записей по [N/8\ хранилищам и поставим в соответствие ключу К хранилище [KN/8\. Далее предположим, что в хранилище к оказалось Nk записей. Если Nk < 16, можно использовать сортировку методом прямых вставок, в противном случае-- сортировать так же, как предлагал Мак-Ларен, но для хранилищ (стопок), где « lOiVfc. Тамминен доказал следующую весьма существенную теорему.

Теорема Т. Существует константа Т, такая, что описанный выше метод сортировки требует в среднем не более TN операций, если только ключи являются независимыми случайными числами с ограниченной и интегрируемой по Риману плотностью распределения f{x) при О < а; < 1. (Константа Т не зависит от вида функции /.)

Доказательство. (См. упр. 18.) Интуитивно ясно, что в результате выполнения первой фазы распределения между N/8 стопками будет найден интервал, на котором функция / является почти постоянной; на второй фазе ожидаемый размер стопки станет почти постоянным.

Некоторые версии поразрядной сортировки были доведены до совершенства при работе с большими массивами буквенных строк, что описано в весьма содержательной статье Р. М. МсПгоу, К. Bostic, М. D. МсПгоу, Computing Systems 6 (1993), 5-27.

УПРАЖНЕНИЯ

► 1. [20] Алгоритм из упр. 5.2-13 показывает, как можно вьшолнить распределяющую сортировку, имея объем памяти, достаточный для хранения всего N записей (и М полей счетчиков), а не 2N записей. Приводит ли эта идея к усовершенствованию алгоритма поразрядной сортировки, проиллюстрированного в табл. 1?

2. [13] Является ли алгоритм R алгоритмом устойчивой сортировки?

3. [15] Объясните, почему в алгоритме Н выходит так, что ВОТМ[0] указывает на первую запись в "объединенной" очереди даже в случае, если стопка О оказывается пустой.

► 4. [23] Во время выполнения алгоритма R все М стопок хранятся в виде связных очередей ("первым вошел - первым вышел"). Исследуйте идею связывания элементов стопок, как в стеке. (На рис. 33 стрелки будут указывать не вверх, а вниз и таблица ВОТМ станет не нужна.) Покажите, что если сцеплять стопки в соответствующем порядке, то может получиться работоспособный метод сортировки. Будет ли этот алгоритм более простым или более быстрым?

5. [20] Какие изменения необходимо внести в программу R, чтобы она выполняла сортировку не трехбайтовых ключей, а восьмибайтовых? Считается, что старшие байты ключа Ki хранятся по адресу KEY 4- «(1:5), а три младших байта, как и раньше, - по адресу INPUT + г (1:3). Каково время выполнения программы с этими изменениями?

6. [М24] Пусть дмы(г)= YlPMNkZ, где pm.iv*: - вероятность того, что после случайного просмотра поразрядной сортировки, разложившего N элементов на М стопок, получилось ровно fc пустых стопок.