Здравствуйте уважаемые форумчане!
Имеется алгоритм сортировки вставкой из Кормена

при сортировке массива {5, 2, 4, 6, 1, 3}, получаются следующие итерации:

, где чёрный квадратик - это элемент с индексом j, серые квадратики - подмассив A[ 1..j - 1]
и белые квадратики соответственно подмассив A[ j+1..n ]
Далее идёт формулировка инвариантов цикла данного алгоритма:


И наконец вопрос!  
Как я понял, при соблюдении инварианта цикла, в подмассиве 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] уже другие значения).
Получается что инварианты не соблюдаются??

Объясните пожалуйста, что я не так понял?! И заранее спасибо!

Что-то на первый взгляд картинка иллустрирует алгоритм пузырьковой сортировки. Или я чего-то спросонья не понимаю?

Нет, это именно сортировка вставкой

 

Классные танцы   

К сожалению, названия алгоритмов и то, что танцами продемонстрировано - полная путаница. Кликаю "Bubble sort with Hungarian", а вижу алгоруитм попарной перестановки.

Так что, похоже, озаглавленное "Insert sort with Romanian folk dance" на самом деле иллустрирует пузырек в его худшей реализации (в лучшей реализации элементы не переставляются попарно, а "всплывающий" элемент помещается во временную переменную).

  
Сортировку вставкой сравнивают ещё с сортировкой карт в руке:


Вот примеры сортировок на Java, вставкой

и пузырьком

может они и похожи, но они разные)

О! О чем я и говорю:

Т.е. сортировка вставкой иллюстрируется "переносом" элементов из одного массива в другой. А в первом посте рисунок иллюстрирует пересортировку одного массива методом пузырька.

В реализации, конечно, можно обойтись одним массивом, но тогда, похоже, эти алгоритмы будут идентичными. Или я все еще не проснулся? Пятница все-таки

Добавлено через 3 минуты и 30 секунд
Что касается кода, то второй код имеет чисто академический смысл т.к. по сравнению с первым ИМХО имеет только недостатки - дополнительные ненужные операции присвоения.

при сортировке вставкой, как показано на рисунке в первом посте, "берется карта со стола" (это элемент с индексом j) и сравнивается с "картами в левой руке" (т.е. элементы с меньшим индексом, чем j или ещё можно сказать подмассив A[1..j - 1]). Если A[j] меньше A[j - 1], то сдвигаем A[j - 1] вправо, если A[j] < A[j - 2], то A[j - 2] тоже сдвигаем вправо, т.е. на место A[j - 1] и т.д. пока не дойдём до начала массива или не найдём элемент меньший, чем A[j] и только тогда вставляем A[j] в нужное место. Тем самым подмассив A[1..j - 1] ВСЕГДА (на начало итерации for) отсортирован!

а при пузырьковой сортировке мы таскаем элемент по всему массиву, пока не дойдём до нужного места. Если, допустим самый большой элемент стоит на 1-ом месте, то мы его протащим до конца массива.

да, у этих сортировок сложность примерно одинаковая (O(n^2)), но логика разная....

точнее, если самый маленький элемент на последнем месте, то протащим его на первое место, внутренним циклом for, конечно же  

Это сообщение отредактировал(а) Pretorian - 27.1.2012, 13:47

Мне кажется, мы начали толочь воду в ступе фактически обсуждая сколько ангелов... является ли алгоритм сортировки вставкой алгоритмом сортировки пузырьком. 

По данному флейму выходит что да, поскольку "таскать элемент по всему массиву" занятие совершенно безсмысленное. Логика, конечно, своя есть, но имеет она смысл чисто академический: типа "а вот можно еще и так извратиться"  

да, вобщем неважно кто есть кто... мнеб по моему вопросу лучше)

....кстати, было бы хорошо, если объяснили бы на пальцах про инвариант цикла и показали бы на каких-нибудь простых циклах  , типа while(i < 10) i++; хотябы, если это возможно... или вот ещё линейный поиск максимума в массиве, тоже хороший пример...
теории об инвариантах в сети полно, я её уже начитался   

Итак Вы предложили  объяснить инварианты цикла на двух примерах:
сортировки и поиска максимума в массиве.

Начнем со второго.
сначала код (возможно не оптимальный но для примера сойдет)

Инвариант: max содержит максимум элементов от 0 до текущего.
1. проверяем корректность Первое значение в цикле БУДЕТ 1. Значит текущее 0 ДО НАЧАЛА ЦИКЛА max СОДЕРЖИТ МАКСИМУМ ОТРЕЗКА ОТ 0 ДО 0. Верно.
2. Если инвариант справедлив ПЕРЕД итерацией то он справедлив и после нее.
итерация начинается с ИЗМЕНЕНИЯ ПЕРЕМЕННОЙ ЦИКЛА. Таким образом перед итерацией k значение i==k-1. и max содержит максмум на отрезке от 0 до k-1. 
изменяем i++ теперь i=k. после выполнения ТЕЛА цикла в переменной max содержится максимум значения участка от 0 до k. все верно. 
Из 1 и 2 следует утверждение, что после завершения цикла в переменной max будет максимум всего массива.

Теперь сортировка.
Инвариант. На шаге j отрезок массива от 1 до j отсортирован.
проверяем.
ДО ЦИКЛА j=1. Один элемент очевидно отсортирован. Верно.
на начало итерации с j=k значение j очевидно равно k-1. Если массив на отрезке от 1 до k-1 отсортирован, то после выполнения ИЗМЕНЕНИЯ ПЕРЕМЕННОЙ ЦИКЛА и ТЕЛА ЦИКЛА отсортирован будет отрезок  от 1 до k. верно.

Значит и весь алгоритм сортировки верен.

Основная ваша ошибка состоит в том, что вы неправильно определили итерацию цикла. Она либо начинается, либо заканчивается изменением переменной цикла.

Большое спасибо Mirkes, за хороший ответ! Поставил бы +, но жаль не могу   

Pretorian, не переживай, я ему плюс поставил