Имеется алгоритм сортировки вставкой из Кормена
| Код |
|
при сортировке массива {5, 2, 4, 6, 1, 3}, получаются следующие итерации:
, где чёрный квадратик - это элемент с индексом j, серые квадратики - подмассив A[ 1..j - 1]
и белые квадратики соответственно подмассив A[ j+1..n ]
Далее идёт формулировка инвариантов цикла данного алгоритма:
| Цитата |
В начале каждой итерации цикла for подмассив A[1..j - 1] содержит те же элементы, которые были в нём с самого начала, но расположенные в отсортированном порядке. Инварианты цикла позволяют понять, корректно ли работает алгоритм. Необходимо показать, что инварианты циклов обладают следующими тремя свойствами. Инициализация. Они справедливы перед первой инициализацией цикла. Сохранение. Если они истинны перед очередной итерацией цикла, то остаются истинны и после неё. Завершение. По завершении цикла инварианты позволяют убедиться в правильности алгоритма. |
И наконец вопрос!
Как я понял, при соблюдении инварианта цикла, в подмассиве A[1..j - 1] в начале и в конце итерации цикла for будут
одни и те же элементы. Но на самом то деле если посмотреть, допустим на итерацию а), на картинке, то видно, что
в начале итерации в ячейке A[1] значение 5, и по завершении цикла в A[1] будет содержаться значение 2, а 5 будет уже
в ячейке A[2].
Так же можно рассмотреть итерацию б) - в начале итерации A[1] = 2, A[2] = 5 (т.е. в подмассиве A[1..j-1] такие значения),
а после окончания итерации A[1] = 2, A[2] = 4 (в подмассиве A[1..j-1] уже другие значения).
Получается что инварианты не соблюдаются??
Объясните пожалуйста, что я не так понял?! И заранее спасибо!
, типа while(i < 10) i++; хотябы, если это возможно... или вот ещё линейный поиск максимума в массиве, тоже хороший пример...