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

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

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

i?i,i?2, • • ,J?jv.

Назовем их записями, а всю совокупность N записей назовем файлом. Каждая запись Rj имеет ключ, Kj, который и управляет процессом сортировки. Помимо ключа, запись может содержать дополнительную "сопутствующую информацию", которая не влияет на сортировку, но всегда остается в этой записи.

Отношение порядка "<" на множестве ключей вводится таким образом, чтобы для любых трех значений ключей а, Ь, с выполнялись следующие условия:

i) справедливо одно и только одно из соотношений а<Ь, а-=Ь, Ь<а (закон трихотомии);

ii) еати а<6и6< с, то а<с (закон транзитивности).

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

Задача сортировки - найти такую перестановку записей р{1)р{2).. .p{N) с индексами {1,2,..., N}, после которой ключи расположились бы в порядке неубывания:

Крг) < Кр2) < < KpN)- (1)

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

Р() < pU) для любых Kpi) = Kp(j) и i< j. (2)

В одних случаях придется физически перемещать записи в памяти так, чтобы их ключи были упорядочены; в других случаях достаточно создать вспомогательную таблицу, которая некоторым образом описывает перестановку и обеспечивает доступ к записям в соответствии с порядком их ключей.

Некоторые методы сортировки предполагают существование величин "со" и "-оо" или одной из них. Величина "оо" считается больше, а величина "-со" меньше любого ключа:

-00 < Kj <оо для 1 <j <N. (3)

Эти величины используются в качестве искусственных ключей, а также граничных признаков. Равенство в (3), вообще говоря, исключено. Если же оно, тем не менее, допускается, алгоритмы можно модифицировать так, чтобы они все-таки работали, хотя нередко при этом их изящество и эффективность отчасти утрачиваются.

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

Достаточно хороший общий алгоритм затрачивает на сортировку N записей время пропорционально N log N; при этом требуется около log N "проходов" по данным. Как мы увидим в разделе 5.3.1, это минимальное время, если записи расположены в произвольном порядке и сортировка выполняется попарным сравнением ключей. Так, если удвоить число записей, то и время при прочих равных условиях возрастет немногим более чем вдвое. (На самом деле, когда N неограниченно возрастает, время сортировки растет как 7V(log7V), если все ключи различны, поскольку и размеры ключей увеличиваются, как минимум, пропорционально log N с ростом Л; но практически N всегда остается ограниченным.)

С другой стороны, если известно, что ключи являются случайными величинами с некоторым непрерывным распределением, то, как мы увидим ниже, сортировка может быть выполнена в среднем за 0{N) шагов.

УПРАЖНЕНИЯ (часть 1)

1. [М20] Докажите, что из законов трихотомии и транзитивности вытекает единственность перестановки р(1)р(2).. .p(N), если сортировка устойчива.

2. [21] Пусть каждая запись Rj некоторого файла имеет два ключа: "большой ключ" Kj и "малый ключ" kj, причем оба множества ключей линейно упорядочены. Тогда можно обычным способом ввести лексикографический порядок на множестве пар ключей {К, к):

{Ki,ki) < {Kj,kj), если Ki < К, или Ki = Kj и ki<kj.

Алиса рассортировала этот файл сначала по большим ключам, получив п групп записей с одинаковыми большими ключами в каждой группе:

Кр(1) = = Kpif < Kp(ii+i) = • • = ivp(i2) < • • • < ivp(i„ i+i) = • • • = ivp(i„),

где i„ = N. Затем она рассортировала каждую из п групп Hp(i. j+i),..., Др(;.) по собственным малым ключам.

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

Взяв тот же исходный файл, КрИс рассортировал его один раз в лексикографическом порядке. Пользуясь парами ключей {Kj,kj).

Получилось ли у всех троих одно и то же?

3. [М25] Пусть на множестве Ki,..., Kn определено отношение "<", для которого закон Трихотомии выполняется, а закон транзитивности - нет. Докажите, что и в этом случае возможна устойчивая сортировка записей, т. е. сортировка, при которой выполняются условия (1) и (2). (На самом деле существует, по крайней мере, три расположения записей, удовлетворяющих этим условиям!)

► 4. [21 ] Составители словарей фактически не следуют жестко лексикографическому порядку, так как прописные и строчные буквы у них перемежаются. В частности, используется такой порядок:

а < Ajaa < АЛ < АА.А < Aachen < aah < • • • < zzz < ZZZ.

Поясните, как реализовать подобный словарный порядок сортировки.

► 5. [М28] Разработайте двоичный код для всех неотрицательных целых чисел, такой, что, если п закодировано в виде строки р{п), то т < п тогда и только тогда, когда р(т) меньше в лексикографическом смысле, чем р(п). Более того, р(т) не должно быть префиксом р{п) для любого тфп. По возможности длина р(;п) должна быть по крайней мере \gn + 0(log log п) для всех больших п. (Такой способ кодирования очень удобен, если приходится Сортировать текст, состоящий из чисел и слов, или если желательно отобразить довольно большие текстовые последовательности на двоичные коды.)

6. \15\ Программисту на MIX B.C. Даллу потребовалось выяснить, находится ли в ячейке А число, большее числа из ячейки В, меньшее или же равное ему. Он написал в программе "LDA А: SUB В, а потом проверил, какой результат получился в регистре А: положительный, отрицательный или нуль. Какую серьезную ошибку он допустил и как должен был поступить?

7. [i 7] Напишите подпрограмму для компьютера MIX для сравнения ключей с увеличенной точностью, исходя из следующих условий.

Вызов: JMP COMPARE

Состояние при входе: гП = п\ CONTENTS (А + fc) = а*, и CONTENTS (В + fc) = 6*,

для 1 < fc < п; полагается, что гг > 1.

Состояние при выходе: CI = GREATER, если (а„,..,, ai) > (Ь„,..., bi);

CI = EQUAL, если (a„,...,ai) = (b„,,..,bi);

CI = LESS, если (a„,... ,ai) < (b„,... ,bi);

rX и rll, возможно, изменились. Здесь отношение (a„,..,,ai) < (b„,...,bi) обозначает лексикографическое упорядочение слева направо, т. е. существует индекс такой, что а*, = 6*, для п > fc > j, но ay < by.

► 8. [50] В ячейках А и В содержатся соответственно числа а и 6. Покажите, что можно написать программу для MIX, которая вычисляла бы min(a, 6) и записывала результат в ячейку С, не пользуясь командами перехода. (Предостережение. Поскольку арифметическое переполнение невозможно обнаружить без операторов перехода, разумно так построить программу, чтобы переполнение не могло возникнуть ни при каких значениях а и Ь.)

9. [М27] Какова вероятность того, что после сортировки в порядке неубывания п независимых равномерно распределенных на отрезке [О, 1] случайных величин г-е от начала число окажется < х?

УПРАЖНЕНИЯ (часть 2)

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

10. [15] Имеется лента, на которой записан миллион слов данных. Как определить, сколько на этой ленте различных слов?