Информатика

              

Решение сложных задач - часть 11


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.

Покажем, что эти соотношения сохраняются после каждого шага цикла. Действительно, на каждом очередном 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)')

Следовательно, после каждого шага цикла для переставленных элементов массивов сохраняются соотношения




Содержание  Назад  Вперед