Сортировка вставки не упорядочивает массив правильно

Question

Вот мой вид вставки, именно такой, как в книге "Введение в алгоритмы":

def insertion_sort():
    A = [5,2,4,6,1,3]
    for j in range(1, len(A)):
        print 'j:'+str(j)
        key = A[j]
        print 'key:'+str(key)
        i=j-1
        print 'i:'+str(i)
        while i > 0 and A[i] > key:
            A[i+1] = A[i]
            i=i-1
            print 'new i: '+str(i)
        print 'swapping value: '+str(A[i]) + ' with value: '+str(A[i+1])
        print ' '
        A[i+1] = key
    print A

Это печатает:

[5, 1, 2, 3, 4, 6]

Что я делаю не так, чтобы они вышли из строя?

Answer 1

Во введении к алгоритмам они всегда предполагают, что массивы начинаются с индекса 1, поэтому вы начинаете range() в 1, но списки Python индексируются на основе 0. Это означает, что вы никогда не сравниваете 5, который находится в A[0], Обратите внимание на все после 5 отсортировано

изменив цикл for на -

for j in range(0, len(A)):

и ваше время, пока

while i >= 0 and A[i] > key:

Должен сделать свое дело.