для 2п-\, 3, 5, 7 и 9. Результаты счета по АЛГОЛ-цро-грамме-и по ручиой программе полностью совпали*.

Подтверждение к алгоритму 22

Б. Томас. (Thomas В. «САСМ», 1970, № 7) Эта процедура была переведена на язык ФОРТРАН IV и проверена ,на машине IBM 360/44 при использовании арифметики с удвоенной точностью (15 значащих десятичных цифр). В алгоритме была обнаружена одна ошибка. Предпоследний заголовок цикла

for к:= 1 step 1 until n do должен иметь вид

for к:= о step 1 until n do После этого исправления были подсчитаны значения Sk{x)/x и -Ck{x)lx и сравнены со значениями табл. 10.1, 10.2 и 10.5 в работе М. Абрамовича и И. Стетуна [81]. Результаты совпали по всем цифрам, данным в этих таблицах, для следующих значений х и k.

АЛГОРИТМ 236

Математическая сортировка [Ml]

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

* Далее в этом «Овидетельстве» следовала табл. 9, которая здесь не .приводится, как потерявшая документальное значение. Текст данного «Свидетельства» здесь несколько подредактирован. (Прим. ред.)

представлен k возможными значениями, пронумерованными О, 1.....ft-1- Размерность массивов: х, уЛ-Щ и

Сначала процедура определяет точное распределение частот последовательности относительно ключа, т. е. число элементов вектора х со значением ключевого массива, точно равным / для всех / от О до k-1. Затем вычисляется для i от О до k-1 кумулятивная плотность I

распределения ф]=2э.где OTj -число элементов мас-

сива X со значением ключа, равным /. Это индуцирует прямое соответствие (аккумулирующа[я функция отображения) каждого элемента массива х одному-единст-венному элементу массива у. При таком сопоставлении (подобно вычислению плотности распределения) щеоб-ходим только один просмотр каждого элемента массива X. Таким образом, алгоритм требует 2п операций просмотра и действия плюс k-•! сложение (для получения кумулятивной плотности распределения).

Этот алгоритм может быть легко и эффективно приспособлен для ручных сортировок алфавита или для сортировок составных ключей: Для сортировки по другому ключу можно использовать этот же алгоритм с новым массивом X, принятым в качестве последнего индуцированного порядка (т. е. в качестве текущего значения вектора /).

Алгоритм 23 (по данным его автора) широко использовался (В машинах с двоичным и десятичным представлением чисел для внутренней па1мяти и (с помощью простой модификации) для больших лент, procedure matsort (x,n,k,f) result: (y,t);

value n,k; integer n,k; array x,y; integer array t;

integer procedure f; begin integer i,j;

for i:= 0 step 1 until k-l do Щ] :=0;

for i:= 1 step 1 until n do begin j: = f(x{iJ); tj]:=t[j]+l end;

for i:=k-2 step -1 until 0 do t[i]: = 1ili]+tli+15;

for i: = 1 step 1 until n do begin j: = f(x[i]);

yi[n+l-t[j]]: = x[i]; t[j]:=tij]-l end

end matsort;

Алгоритм 236 получен путем модификации алгоритма За с целью его сокращения и ускорения его работы. Модификация состояла в следующем.

1. Описание integer i заменено на integer /;

2. Оператор t[f(x[i])]:=t[f(x[i])] +1 заменен на оператор j: = f(x{i]); t[j] :=t[]] +1

3. Операторы

y[n+ l-t[f(x[i})]]: = x[i]; t[f(x[i])]:=t[f(xli])]~l заменены на

j: = f(xW); y[n + l-t[j]]: = xlil; tU]: = t[j]-l Алгоритм 236 был т1ранслирован на машине М-220 в системе ТА-1М и правильно расположил в порядке возрастания массивы х={3, 1, 1, 5) и х={2, 2, 1, 5, 4, 4, 4, 3). При этом использовался следующий тест-блок, begin real min, max; integer i,k,n; start: p0042(n,k); pl041(n,k);

begin array х,у[1:к]; integer array t[0:k-1];

. integer procedure f(a); value a; real a;

f:=entier((a-min)/(max-min) X (n-1)); p0042(x); pl041(x); max:=-iol8; min: = iol8; for i:= 1 step 1 until к do

if x[i]>max then max:=:x[i] else if x{i]<min then min:=x[i];

matsort (x,n,k,f,y,t);

pl041(y,t)

end;

stop;

go to start

В системе TA-IM процедура p0042 -процедура ввода, a /71041 - процедура вывода. В расчетах принималось k=n.

Свидетельство к алгоритму 23а

Алгоритм 23а получен в результате ординарной переработки процедуры, приведенной в нижеследующем подтверждении (Ranshaw R. W. «САСМ», 1961, № 5) к алгоритму 23 (F е и е г z е и g W. «САСМ», 1960, № 11).

Алгоритм 23а проверен ручным счетом- для последовательности целык положительных чисел 3, 1, 1, 5 при