 |
 |
 |
 |
|
 |
 |
102
Покажем, что эти соотношения сохраняются после каждого шага цикла. Действительно, на
каждом очередном k-м шаге цикла будут получены следующие результаты:
Imn = L(imn)
xmn = x(imn) == p(L(imn))
L(imn)' = L(k)
x(imn)' = x(k) = p(L(k)) = p(L(imn)')
L(k)' = Imn = L(imn)
x(k)' = xmn = x(imn) = p(L(imn)) = p(L(k)')
Следовательно, после каждого шага цикла для переставленных элементов массивов сохра-
няются соотношения
x(i)' = p(L(i)) для всех i = 1, ..., N.
Что и требовалось доказать.
Утверждение. Конечным результатом выполнения алгоритма и подпрограммы сортировки
данных будет список данных, в котором последовательность значений р1', р2', ..., р
N
' будет упоря-
дочена:
p1'
р2'
…
p
N
'
Доказательство. В соответствии с доказанной выше леммой 4 значения в массиве x[l:N]
после выполнения алгоритма упорядочения чисел будут удовлетворять условиям
х(1)'
х(2)'
...
x(N)'.
В силу этой же леммы 4 значения индексов в массиве L[1:N] будут удовлетворять соотно-
шениям x[k]' = p(L(k)) для всех k = 1, ..., N.
Конечным результатом алгоритма сортировки данных является вывод значений из массива
p[l:N] в соответствии с массивом индексов L[1:N]. Таким образом, очередные значения последова-
тельности p1', p2',... будут равны:
р1' = p(L(l)) = х(1)',
p2'= р(L (2)) = х(2)'и т. д.
В силу упорядоченности значений х(1)', х(2)', ..., x(N)' получаем, что значения выходной
последовательности будут также упорядочены:
p1'
р2'
…
p
N
'
Что и требовалось доказать.
Следовательно, весь комплекс алгоритмов и подпрограмм полностью соответствует по-
ставленной задаче и гарантирует получение правильных результатов, при любых допустимых ис-
ходных данных.
Проверка на ЭВМ программы сортировки товаров, составленной таким систематическим
образом, при указанных исходных данных дает следующие результаты:
товары:
яблоки, 500, 200
огурцы, 400, 250
арбузы, 200, 600
персики, 800, 100
остатки:
яблоки, 2500, 100
огурцы, 2000, 150
арбузы, 1200, 200
персики, 2000, 0
выручка = 880000
сортировка:
персики, 2000, 0
яблоки, 2500, 100
огурцы, 2000, 150
арбузы, 1200, 200