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

Question

Я посещаю базовый класс под названием «Алгоритмы». Мы изучаем алгоритмы сортировки; мы получили следующий псевдокод в качестве примера алгоритма сортировки вставки. Однако я думаю, что это неправильно.

For i in {2,..,n}: 
    For j in {i,..,2}: 
     If a(j)<a(j-1), swap a(j) and a(j-1) 
     Else, Break 

Вы также можете увидеть его здесь в конспектов, на этом скриншоте:

Я понимаю первую строку - она ​​начинается с 2, потому что первая карта «уже заказал», так как оно пока единственная карта.

Является ли вторая строка ошибкой? Как может быть, что мы используем j от i до 2? Конечно, это не может быть справедливым в будущем. Кроме того, не должен ли разрыв быть менее отступом? Итак, только одна вкладка вместо 2?

Редактировать

Вот "основная идея" алгоритма. Как видите, диапазон индекса j кажется неправильным.

Edit2 Так вот я пытаюсь написать, что происходит в моем уме, читая этот псевдокод: Предположим, у меня есть список (5,3,8,7,2,4,1,6). Я напишу |, чтобы отделить «руку» от колоды, также напишу 5_, чтобы подчеркнуть, на каком элементе я смотрю. Так вот мы идем:

i = 1, (5|3,8,7,2,4,1,6) 
i = 2, (5,3|8,7,2,4,1,6), now j in {2}, so we only have j = 2, a(j=2)=3 < a(j=1)=5, hence swap 3 with 5 
i = 3, (3,5,8|7,2,4,1,6), j in {2,3}, so j=2 gives a(j=2)=5 !< a(j=1)=3 SO WE BREAK! 
i = 4, (3,5,8,7|2,4,1,6), j in {2,3,4}, so j = 2 gives a(j=2)=5 !< a(j=1)=3, SO WE BREAK 

и, как вы видите, это всегда будет происходить с этого момента, потому что мы начинаем с 2 и потому, что мы нарушаем его! Таким образом, несмотря на множество целых чисел для J увеличивается, мы не можем идти дальше 2, потому что мы просто нарушают условие

Answer 1

Если исходить из следующих предположений, код правильный:

• Массив длина N имеет индексы 1..N
• Для петель покрыть указанный диапазон независимо от направления; таким образом, for x in {a,...,b} будет проходить через a, a+1, a+2, ..., b-1, b if a <= b, но пройти через a, a-1, a-2, ..., b+1 b if a >= b.

Answer 2

Вторая строка не является ошибкой, потому что вы пытаетесь взять i-й элемент (работающий на внешнем контуре) и вставить в раздел перед ним. Затем вам нужно сравнить этот элемент с разделом перед его сортировкой.

это SO пост имеет хорошую визуализацию: Insertion Sort vs. Selection Sort