Постановка задачи. Упорядочение последовательности чисел

Упорядочение последовательности чисел.

Дано: x₁, х₂,..., х_N - исходные числа.

Треб.: x₁', x₂',..., х_N' - упорядоченные числа.

Где: х₁' £ х₂' £... £ х_N'.

При: N > 0.

Упорядочение чисел по методу «пузырька» в общей форме имеет вид:

Способ «упорядочение чисел»

нач

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

хтп:= xk

imn:= k

от i=k+1 до N цикл

если xi < хтп то

хтп:= xi

imn: = i

кесли

кцикл

xmn = Min (х_k,..., х_N)

xk' = хтп

ximn ' = xk

кцикл х_k¢ = Min (х_k,..., х_N)

кон x₁ < х₂ <... < х_k¢

Приведенный алгоритм можно рассматривать как алгоритм, сло­женный из нескольких фрагментов - вспомогательных алгоритмов, решающих определенные подзадачи.

Первый фрагмент (внутренний цикл) решает подзадачу нахожде­ния минимального значения в подмассиве x[k:N]. Второй фрагмент решает подзадачу перемещения k-го минимального значения на k-e место в массиве.

Лемма 1. Для вспомогательного алгоритма