Почему этот код для сортировки вставок не работает?

Question

def insertion_sort(l):
    i = 0 ;
    while i < len(l):
        if l[i] > l[i +1]:
            l[i], l[i+1] = l[i +1], l[i];
            i = i +1;
        else:
            i = i + 1 ;
    return lst; 

lst = [34,12,56,4,90,66];

insertion_sort(lst);

ПРИМЕЧАНИЕ. Я использую мобильную версию Stack exchange, которая портит отступы. Поэтому, пожалуйста, игнорируйте это.

Answer 1

Ваш код не работает должным образом, потому что вы go над массивом только один раз. Есть также некоторые незначительные улучшения, которые вы могли бы сделать. Ваш код должен выглядеть примерно так:

def insertion_sort(l):
    for i in range(1, len(l)):
        j = i
        while l[j] < l[j - 1] and j > 0:
            temp = l[j - 1]
            l[j - 1] = l[j]
            l[j] = temp
            j -= 1

    return l


lst = [34, 12, 56, 4, 90, 66]

print(insertion_sort(lst))

Вывод будет:

[4, 12, 34, 56, 66, 90]