 |
 |
 |
 |
|
 |
 |
101
L(k) = k
L(k) = k
x(k)=p(L(k))
x(k)=p(L(k))
кцикл
next k
сортировка-массива
gosub sortmas 'сортировка
от k = 1 до N цикл
for k = 1 to N
i := L(k)
i = L(k)
вывод (tv(i),c(i),p(i))
? tv$(i);c(i);p(i)
кцикл
next k
кон
return
Модификация алгоритма упорядочения чисел, размещаемых в массиве x[l:N], с учетом пе-
рестановок значений в массиве индексов L[1:N] получает следующий вид:
алг «сортировка массива»
sortmas: 'сортировка массива
нач
'
от k = 1 до N-1 цикл
for k = 1 to N-1
xmn := x(k)
xmn = x(k)
imn := k
imn = k
от i = k + 1 до N цикл
for i = k + 1 to N
если x(i) < xmn то
if x(i) < xmn then
xmn := x(i)
xmn = x(i)
imn := i
imn = i
кесли
end if
кцикл
next i
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
x(k) := xmn
x(k) = xmn
кцикл
next k
кон
return
Лемма 4. Результатами выполнения алгоритма сортировки массива будут последователь-
ность чисел, упорядоченная по возрастанию
х(1)'
х(2)'
...
x(N)'
и последовательность индексов в массиве 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.