Алгоритм сортировки вставками (англ, insertion sort) заключается в сравнении каждого из элементов множества, начиная со второго, с предыдущими, уже отсортированными элементами и вставкой (перемещением) в нужную позицию среди них.
Пусть множество {вц, а2,…, а,-}, 1 < i < п, уже упорядочено. Элемент ai+i сравнивается с а*. Если Uj ^ Oi+i, то Oi+i находится на своем месте и, следовательно, множество {аь…, Oi, ai+1} отсортировано. В противном случае ai+i и а* меняются местами (после этот сравниваемый элемент имеет номер г). Затем элемент сравнивается с а*. Если a;_i ^ а,;, то а* находится на своем месте в отсортированной части, иначе а* и аг_1 меняются местами. Далее происходит сравнение а,-_2 и а*_i, но аналогичной схеме. Процесс продолжается до тех пор. пока сравниваемый элемент нс окажется на своем месте в отсортированной части.
Пример 11.3. Используя алгоритм сортировки вставками, упорядочить множество чисел Л = {9,3,12,1,8,5} по возрастанию.
Решение. Состояния множества Л приведены в табл. 11.2.
Сортировка вставками
Таблица 11.2
Состояние. | Упорядоченные элементы. | Сравниваемый элемент. | Сравнение. | Действие. |
so = {9.3,12,1,8,5}. | —. | | 3 и 9. | Перестановка 3 и 9. |
81 = {3,9,12,1,8,5}. | {3,9}. | | 12 и 9. | —. |
s2 = {3,9,12,1,8,5}. | {3,9,12}. | | 1 и 12. | Перестановка 1 и 12. |
«3 = {3,9,1,12,8,5}. | {3.9,12}. | | 1 и 9. | Перестановка 1 и 9. |
s4 = {3,1,9,12,8,5}. | {3,9,12}. | | 1 и 3. | Перестановка 1 и 3. |
55 = {1,3,9,12,8,5}. | {1,3,9,12}. | | 8 и 12. | Перестановка 8 и 12. |
«6 = {1,3,9,8,12,5}. | {1,3,9,12}. | | 8 и 9. | Перестановка 8 и 9. |
87 = {1,3,8,9,12,5}. | {1.3,9,12}. | | 8 и 3. | —. |
s" = {1,3,8,9,12,5}. | {1,3,8,9,12}. | | 5 и 12. | Перестановка 5 и 12. |
sg = {1,3,8,9,5,12}. | {1.3,8,9,12}. | | 5 и 9. | Перестановка 5 и 9. |
s, o = {1,3,8,5,9.12}. | {1.3,8,9,12}. | | 5 и 8. | Перестановка 5 и 8. |
sii = {1,3,5,8,9,12}. | {1,3,8,9,12}. | | 5 и 3. | —. |
В состояниях s и 6'7 элементы стоят на своих местах в отсортированном списке, поэтому никаких действий нс производится. ?
Алгоритм сортировки вставками имеет сложность порядка 0(п2).
