 |
 |
 |
 |
|
 |
 |
96
перестановка2:
1, 3, 9, 7, 4.
перестановка3:
1, 3, 4, 7, 9.
упорядочено.
Приведем точную математическую постановку задачи.
Постановка задачи
Упорядочение последовательности чисел.
Дано: x1, х2, ..., х
N
- исходные числа.
Треб.: x1', x2', ..., х
N
' - упорядоченные числа.
Где: х1'
х2'
...
х
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
)
кон
x1 < х2 < ... < х
k
Приведенный алгоритм можно рассматривать как алгоритм, сложенный из нескольких
фрагментов - вспомогательных алгоритмов, решающих определенные подзадачи.
Первый фрагмент (внутренний цикл) решает подзадачу нахождения минимального значе-
ния в подмассиве x[k:N]. Второй фрагмент решает подзадачу перемещения k-го минимального
значения на k-e место в массиве.
Лемма 1. Для вспомогательного алгоритма
алг «поиск минимума»
нач
хтп := xk
imn := k
от i = k + 1 до N цикл
если x
i
< хтп то
хтп := x
i
imn := i
кесли
кцикл
{ xmn = Min (х
k
, ..., х1) }
кон
конечным результатом вычислений будет значение
xmn = Min (х
k
, ..., х
N
).
Доказательство. Применим индуктивную схему рассуждений. Первое присваивание дает
xmn
k
= x
k
.
Далее на первом шаге цикла при i = k + 1 будет получен минимум первых двух чисел:
x
k+1
при x
k+1
< xmn
k
,
xmn
k+l
=
xmn
k
при x
k+1
xmn
k
.
На втором шаге цикла будет получен минимум первых трех чисел:
xmn
k+2
= min (x
k+2
, min (х
k+1
, х
k
)) = Min (х
k+2
, х
k+1
, х
k
).