Структуры и алгоритмы данных Python: сортировка вставками

Поиск и сортировка Python: упражнение 6 с решением

Напишите программу на Python для сортировки списка элементов, используя алгоритм сортировки вставками.
Примечание. Согласно Википедии «Сортировка вставкой - это простой алгоритм сортировки, который создает окончательный отсортированный массив (или список) по одному элементу за раз. Он гораздо менее эффективен в больших списках, чем более продвинутые алгоритмы, такие как быстрая сортировка, сортировка по типу сортировки или сортировка слиянием». «.

Иллюстрированная презентация: вставка сортировки

Пример решения : -

Код Python:

def insertionSort(nlist):
   for index in range(1,len(nlist)):
     currentvalue = nlist[index]
     position = index
     while position>0 and nlist[position-1]>currentvalue:
         nlist[position]=nlist[position-1]
         position = position-1
     nlist[position]=currentvalue
nlist = [14,46,43,27,57,41,45,21,70]
insertionSort(nlist)
print(nlist)

Пример вывода:

 [14, 21, 27, 41, 43, 45, 46, 57, 70] 

Блок-схема:

Визуализируйте выполнение кода Python:

Следующий инструмент визуализирует, что компьютер делает шаг за шагом при выполнении указанной программы:

Редактор кода Python:

Внесите свой код и комментарии через Disqus.

Предыдущая: Напишите программу на Python для сортировки списка элементов с использованием алгоритма сортировки выбора.
Далее: Напишите программу на Python для сортировки списка элементов, используя алгоритм сортировки оболочки.