 |
 |
 |
 |
|
 |
 |
137
и последовательность индексов в массиве L[1:N], удовлетворяющих условиям
x(k)' = p(L(k)) для всех k = 1, .... N.
Доказательство. Первое утверждение об упорядоченности значений х(1)'
х(2)'
...
x(N)' массива
x[l:N] по завершении алгоритма следует из доказательства правильности алгоритма упорядочения
последовательности чисел. Для доказательства второго утверждения рассмотрим результаты
перестановок значений элементов:
Imn := L(imn)
Imn = L(imn)
xmn := x(imn)
xmn = x(imn)
L(imn) := L(k)
L(imn)' = L(k)
x(imn) := x(k)
x(imn)' = x(k)
L(k) := Imn
L(k)' = Imn = L(imn)
x(k) := xmn
x(k)' = xmn = x(imn)
Перед началом выполнения алгоритма упорядочения массива в алгоритме сортировки данных массив
индексов L[1:N] и упорядочиваемый массив x[l:N] получают значения, удовлетворяющие следующим
соотношениям:
х(i) = P(L(i) для всех i = 1, ..., N.
Покажем, что эти соотношения сохраняются после каждого шага цикла. Действительно, на каждом
очередном 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',... будут равны: