52. [Установка i, К, R.] Присвоить г +- j - 1, К +- Kj, R Rj. (Ha последующих шагах будет предпринята попытка вставить запись R в нужное место, сравнивая К с Ki при убывающих значениях г.)

53. [Сравнение К : К.] Если К > Ki, то перейти к шагу S5. (Мы нашли искомое место для записи R.)

54. [Перемещение Ri, уменьшение г.] Присвоить Ri+i <- Ri, г i ~ 1. Если г > О, то вернуться к шагу S3. (Если г = О, то А" - наименьший из рассмотренных до сих пор ключей, а значит, запись R должна занять первую позицию.)

55. [Перенос R на место Ri+i.] Присвоить Ri+i R.

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

Таблица 1

ПРИМЕР СОРТИРОВКИ МЕТОДОМ ПРОСТЫХ ВСТАВОК 503 : 087

087 503:512 087 503 512:061 061 087 503 512:908 061 087 503 512 908:170

061 087 170 503 512 908:897

061 087 154 170 275 426 503 509 512 612 653 677 765 897 908:703 061 087 154 170 275 426 503 509 512 612 653 677 703 765 897 908

Программа S {Сортировка методом простых вставок). Адреса записей, которые надо рассортировать, - от INPUT+1 до INPUT+N; записи сортируются в той же области памяти по ключу, занимающему целиком одно слово. Здесь гП = j - N;

Время выполнения этой программы равно 9В-Ь lOiV-ЗЛ - 9 машинных циклов*, где N - число сортируемых записей, А - число случаев, когда на шаге S4 значение г убывает до О, а В - количество перемещений записей. Ясно, что А равно числу случаев, когда Kj < mm{Ki,..., Kj-i) при 1 < j < N,t. е. это число левосторонних минимумов - величина, которая была подробно проанализирована в разделе 1.2.10. Нетрудно прийти к выводу, что В тоже известно: число перемещений записей при фиксированном j равно числу инверсий ключа Kj, так что В равно числу инверсий перестановки К1К2 К. Следовательно, согласно формулам 1.2.10-(16), 5.1.1-(12) и 5.1.И13) имеем

А - (minO, ave Ядг - 1, max TV - 1, dev \JHn - Я),

В = (minO, ave (Л - Л)/4, max (Л дг)/2, dev N{N -\){N + 2.Ъ)1Ь),

a среднее время выполнения программы S в случае, если ключи различны и расположены в случайном порядке, равно (2.25TV -- 7.75TV - ЗЯдг - 6)w. В упр. 33 показано, как можно несколько повысить скорость.

Приведенные в качестве примера в табл. 1 данные содержат 16 элементов; в наборе имеется два левосторонних минимума, 087 и 061, и, как было показано в предыдущем разделе, 41 инверсия. Следовательно, TV = 16, Л = 2, Я = 41, а общее время сортировки равно 514м.

Бинарные и двухпутевые вставки. Когда при сортировке методом простых вставок обрабатывается j-я запись, ее ключ сравнивается в среднем примерно с /2 ранее рассортированных ключей; поэтому общее число сравнений равно приблизительно (1 -Ь 2 -Ь • • -Ь TV)/2 TV/4, а это очень много, даже если TV не так уж и велико. В разделе 6.2.1 будут проанализированы методы бинарного поиска, которые указывают, куда вставлять j-й элемент после приблизительно Ig j операций сравнения с соответствующим образом выбранными элементами сортируемого набора. Например, если вставляется 64-я запись, можно сначала сравнить ключ 64 с 32, а затем, если он меньше, сравнить его с Kie, если больше - с и т. д., так что место для Яб4 будет найдено после всего лишь шести сравнений. Общее число сравнений для TV вставляемых элементов равно приблизительно TV Ig TV, что существенно лучше, чем в разделе 6.2.1 показано, что соответствующая

программа не обязательно намного сложнее, чем программа для простых вставок. Этот метод называется методом бинарных вставок. Он упоминался Джоном Мочли (John Mauchly) еще в 1946 году, в первой публикации по машинной сортировке.

Неприятность состоит в том, что метод бинарных вставок позволяет решить задачу только наполовину: после того как найдено место, куда вставлять запись Rj, все равно нужно подвинуть примерно ранее рассортированных записей, чтобы освободить место для Rj, так что общее время выполнения остается, по существу, пропорциональным TV. В некоторых компьютерах (например, в IBM 705) используются процессоры, в наборе команд которых имеется и команда перемещения блока памяти, выполняемая аппаратно с большой скоростью. Но с ростом TV зависимость от TV, в конце концов, начинает преобладать. Например, анализ, проведенный

* В оригинале автор использует термин "unit" - единица, под которой подразумевается среднее время выполнения одной машинной команды (см. тОм 1). Это н есть не что иное, как длительность машинного цикла. - Прим. перев.

X. Нэглером [Н. Nagler, САСМ 3 (1960), 618-620], показывает, что метод бинарных вставок не рекомендуется использовать при сортировке более N = 128 записей по 80 символов на компьютере IBM 705. Методика анализа применима и к другим компьютерам.

Разумеется, изобретательный программист может придумать какие-нибудь способы, позволяющие сократить число необходимых переписей в памяти; первый такой прием, предложенный в начале 50-х годов, проиллюстрирован в табл. 2. Здесь первый элемент помещается в середину области вывода и место для последующих элементов освобождается при помощи сдвигов влево или вправо, туда, куда удобнее. Таким образом удается сэкономить примерно половину времени работы по сравнению с использованием метода простых вставок за счет некоторого усложнения программы. Можно применять этот метод, используя не больше памяти, чем требуется для N записей (см. упр. 6), но мы не станем дольше задерживаться на таких "двухпутевых" вставках, так как разработаны и гораздо более интересные методы.

Таблица 2

ПРОЦЕСС СОРТИРОВКИ МЕТОДОМ ДВУХПУТЕВЫХ ВСТАВОК

087 503 087 503 512 061 087 503 512 061 087 503 512 908

061 087 170 503 512 908

061 087 170503 512 897 908 061 087 170 275 503 512 897 908

Метод Шелла. Для алгоритма сортировки, который каждый раз перемещает запись только на одну позицию, среднее время выполнения будет в лучшем случае пропорционально Л, потому что в процессе сортировки каждая запись должна пройти в среднем через iV позиций (см. упр. 7). Поэтому, если желательно получить метод, существенно превосходящий по скорости метод простых вставок, необходим механизм, с помощью которого записи могли бы перемещаться большими скачками, а не короткими шажками.

Такой метод предложен в 1959 году Дональдом Л. Шеллом [Donald L. Shell, САСМ 2,7 (July, 1959), 30-32] и известен во всем мире под именем своего автора. В табл. 3 проиллюстрирована общая идея, которая лежит в его основе. Сначала делим 16 записей на 8 групп по две записи в каждой группе: {Ri,Rg), {R2,Rio), (RsjRu). в результате сортировки каждой группы записей по отдельности приходим ко второй строке табл. 3. Этот процесс называется первым проходом. Обратите внимание на то, что элементы 154 и 512 поменялись местами, а 908 и 897 переместились вправо. Разделим теперь записи на четыре группы по четыре в каждой: {Ri, R5, Rg, Ris),..., {Ri,Rs, Ri2,Ru)- Затем опять рассортируем каждую группу в отдельности; результат этого второго прохода показан в третьей строке таблицы. На