Что и требовалось

Утверждение. Конечным результатом выполнения алгоритма будет упорядоченная последовательность чисел х₁',..., х_N', удовлет­воряющая условию х₁' £ х₂' £... £ х_N'.

Доказательство проводится по индуктивной схеме рассуждений. Рассмотрим результаты выполнения основного цикла основного алгоритма:

алг «упорядочение чисел»

Нач

от k = 1 до N - 1 цикл

xmn:=х_k

............... { xmn = Min (х_k,..., х_i) }

х¢_k = xmn_N

хmп¢ = х_k

кцикл { х_k' = Min (х_k,..., х_N) }

кон { х₁' £ х₂' £... £ х_k' }

На первом шаге при k = 1 первый элемент последовательности

х₁' = Min (x₁, х₂,..., х_N),

На втором шаге второй элемент последовательности

x₂' = Min (х₂,..., х_N).

В силу свойств минимума последовательности чисел будем иметь

х₁' = Min(x₁, x₂,..., х_N) = min (x₁, Min (х2,..., хN) £ (Min (х2,..., хN) = x₂'.

Таким образом, при k = 2 результатом станут значения х₁' и x₂', такие что

х₁' £ x₂'

На третьем шаге выполнения основного цикла результатом станет

х₃ = Мin(х₃,..., х_N).

Опять же в силу свойств минимума последовательности имеем

х₂' = Min (х₂, х₃,..., х_N) = min (x₂, Min (x₃,..., х_N)) £ Min (x₃,..., х_N) = x₃'.

Таким образом, после третьего шага при k = 3 первые три значе­ния последовательности х₁', x₂', x₃' будут удовлетворять условию

х₁'£ x₂'£ x₃'

Из приведенных выкладок можно сделать индуктивное предположение, что на каждом очередном k-м шаге выполнения основного цикла первые k членов последовательности х₁', x₂',.... х_k' будут удов­летворять условию

х₁'£ x₂'£ … £ x_k'.

Данное предположение доказывается с помощью математической индукции. На начальных шагах при k = 2 и k = 3 оно уже показано. Покажем, что оно будет выполнено на (k + 1)-м шаге, если это усло­вие выполнено на k-м. шаге.

В силу леммы 2 на k-м и (k + 1)-м шагах выполнения основного цикла промежуточными результатами будут

х_k' = Min(x_k, x_k+1,..., х_N),

х_k+1' = Min (x_k+1,..., х_N).

В силу свойств минимума последовательности чисел имеем

х_k' = Min(x_k, x_k+1,..., х_N) = min (х_k, Min (х_k+1,...,х_N)) £ Min (x_k+1,..., х_N) = х_k+1'.

Таким образом, х_k £ x_k+1 и в силу индуктивного предположения получаем, что

x₁' £ х₂' £... £ х_k' £ x_k+'₁.

Что и требовалось доказать.

Осталось уточнить результаты выполнения последнего шага цикла при k = N - 1. В силу леммы 2 результатом будет значение

x_N-'₁ = Min (x_N-1, x_N) £ х_N'.

Таким образом, после N - 1 шагов выполнения основного цикла для последовательности в целом будут выполнены соотношения упорядоченности

x₁' £ x₂' £... £ х_N'.

Что и требовалось доказать. Следовательно, рассмотренный алго­ритм упорядочения чисел правильный в целом.

Применим теперь данный способ упорядочения для решения задачи сортировки. Рассмотрим следующую задачу. Пусть дана не­которая партия товаров с заданной отпускной ценой, указана цена товаров и известны остатки от их продажи. Требуется подсчитать выручку от продажи и отсортировать товары по их остатку.

Данные о товарах представлены двумя таблицами: