Сортировка вставками на Python

Программа будет сортировать список методом вставок (Insertion sort).

, Сортировка вставками на Python

Суть сортировки

  1. Перебираются элементы в неотсортированной части массива.
  2. Каждый элемент вставляется в отсортированную часть массива на то место, где он должен находиться.

Шаги к правильному решению

  1. Создадим функцию insertion_sort которая принимает на вход список.
  2. Внутри функции создадим цикл с переменной i которая будет исчисляться от 1 до (длины списка - 1)
  3. Создадим переменную temp = alist[i].
  4. Установим j = i - 1.
  5. Создадим цикл while, который будет работать до тех пор, пока j не отрицательное и temp меньше, чем элемент под индексом j.
  6. Внутри цикла while установим alist[j + 1] = alist[j] и затем уменьшим j на 1.
  7. После окончания цикла while установим alist[j + 1] = temp.

Исходный код для сортировки вставками:

def insertion_sort(alist):
    for i in range(1, len(alist)):
        temp = alist[i]
        j = i - 1
        while (j >= 0 and temp < alist[j]):
            alist[j + 1] = alist[j]
            j = j - 1
        alist[j + 1] = temp
 
 
alist = input('Enter the list of numbers: ').split()
alist = [int(x) for x in alist]
insertion_sort(alist)
print('Sorted list: ', end='')
print(alist)