Haikson

[ Everything is possible. Everything takes time. ]

Сортировка методом вставки

 
# В данном видео рассматриваем алгоритм сортировки вставками

def insertion_sort(lst):
    # Определим переменную для временного хранения значения элемента массива (списка)
    key = 0
    # Циклом проходимся по всем элементам массива, начиная с первого (lst[1]) до последнего (lst[N])
    for i in range(1, len(lst)):
        key = lst[i]  # в переменную key положили значение элемента
        j = i - 1  # определяем переменную j, которая меньше i на единицу
        while j >= 0 and lst[j] > key:  # пока j больше или равен 0 и элемент массива под j больше key
            lst[j+1] = lst[j]  # перемещаем элемент вправо по массиву
            j -= 1
            # Чтобы было наглядно видно, как происходид перемещение по массиву, выводим массив на экран
            print j+1, ": ", lst
        lst[j + 1] = key
        print "\n\n"
        
    print "Результат сортировки", lst
        
# Попробуем вызвать функцию с разными массивами

insertion_sort([4,2,5,66,12,32,1])