Сортировка вставками. 
Теоретические основы информатики

Алгоритм сортировки вставками (англ, insertion sort) заключается в сравнении каждого из элементов множества, начиная со второго, с предыдущими, уже отсортированными элементами и вставкой (перемещением) в нужную позицию среди них.

Пусть множество {вц, а₂,…, а,-}, 1 < i < п, уже упорядочено. Элемент a_i+i сравнивается с а*. Если Uj ^ Oi+i, то Oi+i находится на своем месте и, следовательно, множество {а_ь…, Oi, a_i+1} отсортировано. В противном случае a_i+i и а* меняются местами (после этот сравниваемый элемент имеет номер г). Затем элемент сравнивается с а*. Если a;_i ^ а,;, то а* находится на своем месте в отсортированной части, иначе а* и а_г_1 меняются местами. Далее происходит сравнение а,-_2 и а*_i, но аналогичной схеме. Процесс продолжается до тех пор. пока сравниваемый элемент нс окажется на своем месте в отсортированной части.

Пример 11.3. Используя алгоритм сортировки вставками, упорядочить множество чисел Л = {9,3,12,1,8,5} по возрастанию.

Решение. Состояния множества Л приведены в табл. 11.2.

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

Таблица 11.2

В состояниях s и 6'7 элементы стоят на своих местах в отсортированном списке, поэтому никаких действий нс производится. ?

Алгоритм сортировки вставками имеет сложность порядка 0(п²).