Следовательно, выполнение программы С занимает от + ION - 4 до 5.5N + 7.57V - 4 машинных циклов, а среднее время работы находится посередине между этими крайними значениями. Например, для данных табл. 1 имеем 7V = 16, Л = 120, В - 41, значит, программа С рассортирует их за время 1129и. Модификация программы С, обладающей несколько иными временными характеристиками, рассматривается в упр. 5.

Множитель iV, которым определяется время работы, свидетельствует о том, что алгоритм С неэффективен при большом 7V; при удвоении числа записей время увеличивается в четыре раза. Поскольку этот метод требует сравнения всех пар ключей {Ki,Kj), нет очевидного способа исключить зависимость от N. Тем не менее дальше в этой главе будет показано, что, используя другую методику, время сортировки для наихудшего случая можно уменьшить до порядка NlogN. Алгоритм С интересен для нас не эффективностью, а, главным образом, своей простотой; его описание служит примером того стиля, в котором 0удут описаны более сложные (и более эффективные) методы. Существует другая разновидность сортировки посредством подсчета, которая действительно весьма важна с точки зрения эффективности; она применима в основном в том случае, когда имеется много равных ключей и все они попадают в интервал и < Kj < v, ширина которого (v - и) невелика. Кажется, что эти ограничения весьма сужают область применения такой модификации, но на самом деле мы увидим немало приложений этой идеи. Например, если применить этот метод к старшим цифрам ключей, а не ко всем ключам целиком, то файл окажется частично рассортированным, и будет уже сравнительно просто довести дело до конца.

Чтобы понять этот принцип, предположим, что все ключи лежат между 1 и 100. При первом просмотре файла можно подсчитать, сколько имеется ключей, равных 1, 2, ..., 100, а при втором - расположить записи в соответствующих местах области вывода. В следующем алгоритме (рис. 9) все это описано более подробно.

Алгоритм D {Подсчет распределена). Этот алгоритм сортирует записи Ri,..., Rj\f, используя вспомогательную таблицу COUNT [и],..., COUNT [и] в предположении, что все ключи - целые числа в диапазоне и < Kj < v, 1 < j < N. На последнем этапе выполнения алгоритма все записи в требуемом порядке переносятся в область вывода Si,..., Sn.

Dl. [Сбросить счетчики.] Обнулить все счетчики COUNT [и]-COUNT [и].

D2. [Цикл по j.] Выполнить шаг D3 при I < j < N; затем перейти к шагу D4.

D3. [Увеличить COUNT [K ,].] Увеличить значение COUNT[К] на 1.

D4. [Накопление.] (К этому моменту значение COUNT [г] есть число ключей, равных г.) Присвоить COUNT [г] COUNT [г] -t- COUNT [г - 1] для i = и + 1, и + 2, ..., v.

D5. [Цикл по j.] (К этому моменту значение COUNT [г] есть число ключей, меньших или равных г, в частности COUNT [f] = TV.) Выполнить шаг D6 при j = N, N - 1, ..., 1 и завершить выполнение процедуры.

D6. [Вывод Rj.] Присвоить г -f- COUNT[К], 5г и COUNT[Kj] г - 1.

Пример использования этого алгоритма рассмотрен в упр. 6; программу для MIX можно найти в упр. 9. При сформулированных выше условиях, т. е. когда диапазон V - и мал, эта процедура сортировки работает очень быстро.

Dl. Очистить все COUNT

D2. Цикл по j

N>j>l

D3. Увеличить COUNT CKj]

j = 0

D4. Накопление

D5. Цикл по j

N>j>l

D6. Вывод Rj

j = 0

Рис. 9. Алгоритм D: подсчет распределения.

Сортировка посредством сравнения и подсчета, как в алгоритме С, впервые упоминается в работе Е. Н. Friend, JACM 3 (1956), 152, хотя ее автор и не утверждает, что это его собственное изобретение. Подсчет с распределением, как в алгоритме D, впервые разработан X. Сьювордом в 1954 году и использован при поразрядной сортировке, которую мы обсудим позже (см. раздел 5.2.5); этот метод также был опубликован под названием "Mathsort" в работе W. Feurzeig, САСМ 3 (1960), 601.

УПРАЖНЕНИЯ

1. [15] Будет ли работать алгоритм С, если на шаге С2 значение i будет изменяться от 2 до Л, а не от Л до 2? Что произойдет, если на шаге СЗ значение j будет изменяться от 1 до г - 1?

2. [21] Покажите, что алгоритм С работает правильно и при наличии одинаковых ключей. Если Kj = Кг к j < г, то где, в конце концов, окажется Rj: до или после Дг?

► 3. [21] Будет ли алгоритм С работать правильно, если на шаге С4 заменить проверку

Kг < Kj" ПрОВеркОЙ Kг < Kj?

4. [16] Напишите М1Х-программу, которая "завершит" сортировку, начатую программой С; ваша программа должна поместить ключи в ячейки OUTPUT+1-OUTPUT+N в порядке возрастания. Сколько времени потребуется на это вашей программе?

5. [22] Станет ли программа С лучше в результате следующих изменений? Ввести новую строку 08а: INCX 0,2

Измейить строку 10: JGE 5F Изменить строку 14: DECX 1 Удалить строку 15.

6. [18] Промоделируйте вручную работу алгоритма D, показывая промежуточные результаты, получающиеся при сортировке 16 записей 5Т, ОС, 5U, 00, 9., IN, 8S, 2R, 6А, 4А, 1G, 5L, 6Т, 61, 70, 7N. Здесь цифры - это ключи, а буквы - сопутствующая информация в записях.

7. [13] Обеспечивает ли алгоритм D устойчивую сортировку?

8. [15] Будет ли алгоритм D работать правильно, если на шаге D5 значение j будет изменяться от 1 до Л, а не от Л до 1?

9. [23] Напишите MIX-программу для алгоритма D, аналогичную программе С и упр. 4. Выразите время работы программы в виде функции от Л и {v - и).

10. [25] Предложите эффективный алгоритм, который бы заменял Л величин {Ri Rn) соответственно величинами (Др{1),...,Rp(n))j если даны значения Ri,...,Rn и перестановка р(1) .. .p(N) множества {1,..., Л}. Постарайтесь использовать как можно меньше

памяти. (Эта задача возникает, когда требуется перекомпоновать в памяти записи после сортировки таблицы адресов, не расходуя память на 2N записей.)

11. [М27] Напишите MIX-программу для алгоритма из упр. 10 и проанализируйте ее эффективность.

► 12. [25] Предложите эффективный алгоритм перекомпоновки в памяти записей Ri,..., Rn в рассортированном порядке после завершения сортировки списка (см. рис. 7). Постарайтесь использовать минимум памяти.

► 13. [27] Алгоритму D требуется память для 2N записей Ri,..., Rn и i,..., Sn- Покажите, что можно обойтись памятью для Л записей Ri,..., Rn, если вместо шагов D5 и D6 использовать другую процедуру расстановки. (Таким образом, задача состоит в том, чтобы разработать алгоритм, который бы перекомпоновывал записи Ri,... ,Rn, основываясь на значениях COUNT [и] , ..., COUNT [и] после выполнения шага D4, без использования дополнительной памяти; это, по существу, обобщение задачи, рассмотренной в упр. 10.)

5.2.1. Сортировка путем вставок

Упомянутый в начале раздела 5.2 способ, которым пользуются игроки в бридж, служит базовым для одного из важных семейств методов сортировки. Этот способ предполагает, что перед рассмотрением записи Rj предыдущие записи Ri,...,Rj-i уже упорядочены и Rj вставляется в соответствующее место. Приняв эту схему в качестве базовой, можно построить несколько .любопытных ее модификаций.

Метод простых вставок. Простейший метод сортировки посредством вставок можно считать наиболее очевидным. Пусть 1 < j < Л и записи Ri,... ,Rj-.i уже размещены так, что

Ki <К2 <-<Kj i.

(Напомним, что в этой главе через Kj обозначается ключ записи Rj.) Будем сравнивать по очереди Kj с Kj-i, Kj-2, • • • до тех пор, пока не обнаружим, что запись Rj следует вставить между Ri и Ri+i \ тогда подвинем записи iij+i,..., Rj-i на одну позицию вверх и поместим новую запись в позицию г -Ь 1. Удобно совмещать операции сравнения и перемещения, перемежая их между собой, как продемонстрировано в следующем алгоритме; поскольку запись Rj как бы "погружается" на положенный ей уровень, этот способ часто называют просеиванием или погружением (рис. 10).

S2. Установка i, К, R

>S3. Сравнение К: К?)

Рис. 10. Алгоритм S: сортировка методом простых вставок.

Алгоритм S {Сортировка методом простых вставок). Записи Ri,...,Rf переразмещаются на том же месте. После завершения сортировки их ключи будут упорядочены: Ki < • • • < Адг.

S1. [Цикл по j.] Выполнить шаги от S2 до S5 при j = 2,3,...,Л и после этого завершить выполнение процедуры.