граммы могут генерировать последовательности из Л элементов (в результате генерации случайно распределенных совокупностей элементов либо стандартного ввода), выполнять сортировку последовательности и отображать ее содержимое. Например, ATD в файле SEQ.cxx должен работать со следующим программным кодом:

#include Item.h

#include SEQ.cxx

main(int argc, char *argv[])

{ int N = atoi (argv[l] , sw = atoi (argv[2]) ;

if (sw) SEQrand(N) ; else SEQscan();

SEQsortO ;

SEQshowO ;

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

6.73. Расширить реализацию из упражнения 6.72 так, чтобы она стала ATD первого класса. Совет: рещение ищите в библиотеке стандартных шаблонов.

6.10. Метод распределяющего подсчета

Повышение эффективности некоторых алгоритмов сортировки достигается за счет использования специфических свойств ключей. Например, рассмотрим такую задачу: требуется выполнить сортировку файла из Л элементов, ключи которых принимают различные значения в диапазоне от О до Л - 1. Мы можем решить эту проблему сразу, используя с этой целью массив Ь, посредством оператора:

for (i = 0; i<N; i++) b [key (a [i]) ] = ati];

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

Если все ключи равны О, то сортировка тривиальна; теперь предположим, что два различных ключа принимают значения О и 1. Такого рода проблема сортировки может возникнуть, когда требуется выделить элементы файла, удовлетворяющие некоторым (возможно, достаточно сложным) проверочным критериям: допустим, мы считаем, что значение О ключа означает, что элемент принят , а значение 1 - что элемент отвергнут . Один из способов сортировки состоит в том, что сначала подсчи-тывается число О, затем выполняется второй подход по входному массиву а с целью размещения его элементов в массиве Ь, при этом предусматривается массив, состоящий из двух счетчиков, который используется следующим образом. Мы начинаем с того, что помещаем О в cnt[0], а количество нулевых ключей в файле - в cnt[l], с целью показать, что в рассматриваемом файле не существуют ключи, принимающие значения меньше О, но имеется cnt[l] ключей, значения которых меньше 1. Разумеется, мы можем заполнить массив b следующим образом: в начало массива записы-

ваются О (начиная с b[[cnt[0]] или Ь[0]) и 1, начиная с b[cnt[l]]. Таким образом, программный код

for (i = 0; i<N; i++) b[cnt[a[i]]++] = a[i];

переносит элементы из a в b. Опять-таки мы получаем быструю сортировку за счет использования ключей в качестве индексов (для выбора между cnt[0] и cnt[l]).

Такой подход очень просто обобщается. Более реалистичную задачу в том же духе можно сформулировать следующим образом: выполнить сортировку файла, состоящего из Л элементов, ключи которого принимают целые значения в диапазоне от О до М-\. Расширим базовый метод, описанный в предыдущем пара-фафе, до алгоритма, получившего название распределяющего подсчета, который эффективно решает эту задачу для не слишком больших М. Точно так же как и в случае двух ключей, идея состоит в том, чтобы подсчитать количество ключей с каждым конкретным значением, а затем использовать счетчики при перемещении в соответствующие позиции во время второго прохода по сортируемому файлу. Сначала подсчитывается число ключей для каждого значения, затем вычисляются частичные суммы, чтобы знать, сколько имеется ключей, меньших или равных каждому такому значению. Далее снова, аналогично случаю двух значений ключа, используем эти числа как индексы при распределении ключей. Для каждого ключа показания связанного с ним счетчика рассматриваются в качестве индекса, указывающего на конец блока ключей, принимающих одно и то же значение. Этот индекс используется при размещении ключей в массиве Ь, после чего производится переход к следующему элементу. Описанный процесс иллюстрируется на рис. 6.17. Реализация находится в программе 6.17.

о 1 2 3 4 S 6 7 а 9 10 11 12 13 14 033011030201120

4 10

О О О О

о о о о

о о о о

о о о о

о о о о о

РИСУНОК 6.17. СОРТИРОВКА МЕТОДОМ РАСПРЕДЕЛЯЮЩЕГО ПОДСЧЕТА

Сначала для каждого значения определяется, сколько имеется в файле ключей, принимающих это конкретное значение: в рассматриваемом примере имеется шесть ключей, принимающих значение О, семь значений 1, два значения 2 и три значения 3. Затем подсчитываются частичные суммы ключей, принимающих значения, меньшие значений конкретных ключей: О ключей меньше О, 6 ключей меньше 1, 10 ключей меньше 2 и 12 ключей меньше 3 (таблица в середине). Затем, помещая ключи в соответствующие позиции, частичные суммы рассматриваются в качестве индексов: О в начале файла помещается в ячейку 0; далее увеличивается на единицу значение указателя, соответствующего 0; в эту позицию пойдет следующий 0. Затем 3 из следующей позиции в файле слева помещается в ячейку 12 (поскольку в файле имеются 12 ключей со значением, меньшим 3), причем соответствующий счетчик увеличивается на 1 и т.д.

Программа 6.17. Распределяющий подсчет

Во время выполнения первого цикла for счетчики инициализируются значениями 0; во втором цикле for значение второго счетчика устанавливается равным количеству ключей О, значение третьего счетчика - количеству ключей, равных 1 и т.д. В третьем цикле for все эти числа складываются, в результате чего получаем количество ключей, меньших или равных ключу, соответствующему очередному счетчику. Эти числа теперь представляют собой индексы концов тех частей файлов, которым эти ключи принадлежат. Четвертый цикл for перемещает ключи во вспомогательный массив b в соответствии со значениями этих индексов, а на завершающем цикле отсортированный файл возвращается в файл а. Чтобы этот программный код работал, необходимо, чтобы ключи были целыми значениями, не превышающими М, хотя его можно легко модифицировать таким образом, чтобы ключи можно было извлекать из элементов с более сложной структурой (см. упражнение 6.77).

void distcount (int а[], int 1, int г) { int i, j , cnt[M]; static int b[maxN];

for (j = 0; j < M; j++) cnt[j] = 0;

for (i = 1; i <= r; i++) cnt [a [i]+1]++;

for (j = 1; j < M; j++) cnt[j] += cnt[j-l];

for (i = 1; i <= r; i++) b [cnt [a [i] ]++] = a[i];

for (i = 1; i <= r; i++) a[i] = b[i-l];

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

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

Если сортировке подвергается файл крупных размеров, то вспомогательный файл b может привести к проблемам в плане распределения памяти. Программу 6.17 можно изменить так, чтобы она совершала сортировку на месте (т.е., без необходимости построения вспомогательного файла), используя методы, подобные применяемым в программе 6.14. Эта операция тесно связана с базовыми методами, которые будут обсуждаться в главах 7 и 10, так что отложим ее изучение до упражнений 12.16 и 12.17 из раздела 12.3. Как станет ясно из главы 12, подобная экономия пространства памяти достигается ценой нарушения устойчивости алгоритма, из-за чего область применения этого алгоритма существенно сужается, поскольку приложения, использующие большое число дубликатов ключей, часто прибегают к помощи других связанных с ними ключей, относительный порядок которых должен быть сохранен. Исключительно важный пример такого рода исследуется в главе 10.