вод и 9.6 с на вычисления. Оптимизация программы сортировки с помощью принципов, изложенных в гл. 8, сокращает время работы до 14 с: 12.3 на ввод-вывод и 1.7 на вычисления.
(См. гл. И, особенно задачу 7.) В нижеприведенной программе предполагается, что выходом функции Randlnt (А, В) является случайное пелое число от А до В.
for I := 1 to К do
XCI] := I for I := 1 to К do
Swap(Xm, XHtandlntd,!])
print ХП]
Функция Randlnt обсуждается в разд. 10.2.
Если каждое пелое число появляется максимально 10 раз, мы можем отвести под счетчик количества его появлений половину байта, т. е. 4 бита. Применяя это решение к задаче 1, мы можем упорядочить весь файл за один проход, использовав 27 000/2 байтов, или за К проходов, использовав 27 000/2К байтов.
Информация о курсе может быть представлена 27 000 байтами в ОЗУ, если для каждого из всех возможных номеров курсов хранить число имеющихся мест в виде двух байтов. Если число из четырех цифр не является правильным номером курса, то в таблице из 10 000 элементов в его позиции запоминается специальное значение (например, — 1). Такое изменение сокращает время работы предложенной программы с нескольких часов до нескольких минут.
Эффект от установки начальных значений вектора Data [1.. .N] может быть достигнут с помощью сигнатуры, содержащейся в двух дополнительных векторах From и То из N элементов и в целой переменной Тор. Если задано начальное значение элемента Data [I], то From [I] < Тор и То [From [I] ] = I. Таким образом, From - простая сигнатура, а с помощью векторов То и Тор гарантируется, что в ячейку From не попадет случайная сигнатура, обусловленная произвольным содержимым памяти. Пустые элементы в векторе Data теряют свои начальные значения, как показано на рисунке
