Записи

Дополнительная таблица

Ключ

Сопутствующая информащ1я

До сортировки После сортировки

Рис. 6. Сортировка таблицы адресных ссылок. Ri

Ключ

Сопутствующая информация Поле связи (после сортировки)

Голова списка

Рис. 7. Сортировка списка,

обязательно перемещать записи, так как поля связи, как правило, вполне приемлемы для всех послед>ющих операций обработки.

Все методы сортировки, которые мы исследуем "досконально", будут проиллюстрированы четырьмя способами: посредством

a) словесного описания алгоритма,

b) блок-схемы,

c) программы для машины MIX,

d) примера применения этого метода сортировки к некоторому множеству из 16 чисел.

Программы для компьютера MIX будут, как правило, написаны в предположении, что ключ - числовой и что он помещается в одном слове; иногда мы даже будем ограничивать значения ключей так, чтобы они занимали лишь часть слова. Отношением порядка < будет обычное арифметическое отношение порядка, а записи будут состоять из одного ключа, без сопутствующей информации. Эти предположения позволяют сделать программы более короткими и простыми для понимания, и не составляет труда распространить их на общий случай (например, применяя сортировку таблиц адресов). Вместе с программами для MIX приводится анализ времени выполнения соответствующего алгоритма сортировки.

Сортировка посредством подсчета. Чтобы проиллюстрировать, как мы будем анализировать методы внутренней сортировки, рассмотрим идею "подсчета" упомянутую в начале данного раздела. Этот простой метод основан на том, что j-й ключ в окончательно упорядоченной последовательности превышает ровно j - 1 остальных ключей. Иначе говоря, если известно, что некоторый ключ превышает ровно 27 дру-

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

((сравнить Kj с Ki) при 1 < j < N) при 1 < г < iV;

но нетрудно заметить, что более половины этих операций излишни, поскольку не нужно сравнивать ключ сам с собой и после сравнения Ка с Кь уже не надо сравнивать Кь с Ка- Поэтому достаточно

((сравнить Kj с Ki) при 1 < j < i) при 1 <i < N.

Итак, получаем следующий алгоритм.

Алгоритм С {Подсчет сравнений). Этот алгоритм (рис. 8) сортирует записи Ri,...,Rn по ключам Ki,..., К]\!, используя вспомогательную таблицу COUNT [1], COUNT[Л] для подсчета числа ключей, меньших данного. После завершения алгоритма величина COUNT [j] -t-1 определяет окончательное положение записи Rj.

С1. [Сбросить счетчики COUNT.] Установить в счетчиках COUNT [ 1]-COUNT [iV] нули.

С2. [Цикл по г.] Выполнить шаг СЗ при г - N, N-1, 2; затем завершить выполнение процедуры.

СЗ. [Цикл по j.] Выполнить шаг С4 при j = i-2, 1.

С4. [Сравнить Ki : Kj.] Если Ki < Kj, то увеличить COUNT[j] на 1; в противном случае увеличить COUNT [i] на 1.

Обратите внимание на то, что в данном алгоритме записи не перемещаются. Он аналогичен алгоритму сортировки таблицы адресов, поскольку таблица COUNT определяет конечное положение записей; но эти методы несколько различаются, потому что COUNT указывает, куда нужно переслать запись Rj, а не запись, которую надо переслать на место Rj. (Таким образом, таблица COUNT определяет перестановку, обратную перестановке р{1).. -piN); см. раздел 5.1.1.)

В табл. 1 проиллюстрирован типичный ход событий при подсчете сравнений. Использован пример с 16 случайными числами, которые были выбраны автором еще 19 марта 1963 года.Те же самые 16 чисел будут использованы в примерах, иллюстрирующих и другие методы, анализ которых еще впереди.

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

Программа С {Подсчет сравнений). Ниже приведена программа для MIX, реализующая алгоритм С в предположении, что Rj хранятся по адресу INPUT -t- j, а COUNTER] - по адресу COUNT -t- j, где 1 < j < Л; состояние регистров следующее: г11 = г, г12 = j, rk = Ki= Ri, гХ = COUNT [г].

01 START ENTl N 1 CI. Очистки COUNT.

02 STZ COUNT, 1 N COUNT[i] 0.

Таблица 1

СОРТИРОВКА ПОСРЕДСТВОМ ПОДСЧЕТА (АЛГОРИТМ С)

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

C2. Цикл no г

N>i>l

j = 0

C3. Цикл no j

i>j>l

<-

C4. Сравнить Ki-.Kj

Рис. 8. Алгоритм С: подсчет сравнений.

Время работы этой программы равно 13Л + 6а + 5в - 4 машинных циклов, где N - число записей, А - число способов выбрать 2 предмета из iV, т. е. (2) = (TV - N)/2, & В - число пар индексов, таких, что j < i и Kj > К. Значит, В - число инверсий перестановки Ki ... Км; эта величина подробно анализировалась в разделе 5.1.1 (формулы 5.1.1-(12) и 5.1.1-(13)), в котором было найдено, что для неравных ключей, расположенных в случайном порядке.

В = (min О, ave (TV - 7V)/4, max (TV - 7V)/2, dev V7V(7V - 1)(7V + 2.5)/б).