Правильно ли псевдокод для сортировки вставки?

Question

Я пытаюсь реализовать в Python следующий псевдокод (от Russian page for insertion sorting):

for i = 2, 3, ..., n: 
    key := A[i] 
    j := i - 1 
    while j >= 1 and A[j] > key: 
     A[j+1] := A[j] 
     j := j - 1 
    A[j+1] := key 

У меня есть ошибка: Traceback (самый последний вызов последний): Файл "insertion.py", строка 6, в test_sort self.assertEqual (sort ([5, 2, 6, 3, 7]), [2, 3, 5, 6, 7]) Файл «insertion.py», строка 12, в сортировке key = a [ i] IndexError: список index out of range

Мой код() is:

def sort(a): 
    len_a = len(a) 
    len_a_plus_1 = len_a + 1 
    for i in range(2, len_a_plus_1): 
     key = a[ i ] 
     j = i - 1 

     while j >= 1 and a[ j ] > key: 
      a[ j + 1 ] = a[ j ] 
      j -= 1 
     a[ j + 1 ] = key 

    return a  

Если изменить аргументы для диапазона() вызов:

for i in range(2, len_a) 

... тогда я получаю неверный результат:

[5, 2, 3, 6, 7] 

мой код неправильно или является алгоритм в article неподдельный?

Обновление.

Я изменил код (с 0-индексированным принципом Python), но он не работает должным образом:

def sort(a): 
    len_a = len(a) 
    for i in range(1, len_a): 
     key = a[ i ] 
     j = i - 1 

     while j and a[ j ] > key: 
      a[ j + 1 ] = a[ j ] 
      j -= 1 
     a[ j + 1 ] = key 

    return a   

Входной сигнал: [5, 2, 6, 3, 7] Выход: [5, 2, 3, 6, 7]

Разрешение.

Мы нашли решение:

while j and a[ j ] > key 

Шоуда быть

while j >= 0 and a[ j ] > key 

Answer 1

[5, 2] не работает. Если вы просто отметите while j (>0), вы никогда не переместите первый элемент. Я думаю, что это работает

while j >= 0 and a[ j ] > key: 

Answer 2

Python использует 0-индексирование, что делает a[len(a)] из диапазона. Псевдокод использует индексирование на основе 1.

Вы должны уменьшить как ваши индексы одно:

len_a = len(a) 
for i in range(1, len_a): 

и

while j >= 0 and a[j] > key: