Пусть одномерный массив задан вектором v = (v0 v1 ... vn-1). Сортировка его простыми включениями (вставками) может быть описана так. Пусть весь массив уже разбит на отсортированную - (S) и не отсортированную - (NS) части. На первом шаге S состоит из одного элемента v0. Далее возьмем очередной элемент из NS и вставим его в требуемое место S так, чтобы сохранить отсортированность S. Повторяя последнюю операцию до полного исчерпания NS, мы отсортируем весь исходный массив. Заметим, что именно этим методом обычно упорядочивают наборы своих карт игроки во многих карточных играх.
адача
2.
Составить рекурсивную программу-функцию
сортировки простыми включениями массива,
заданного вектором v = (v0
v1 ... vn-1).
Решение. Описанная выше процедура сортировки простыми включениями явно рекурсивна. Соответствующая программа может быть задана функцией sortins(v):
(4)
Сортировка включениями обычно используется, когда v есть динамически формируемый массив, который все время должен поддерживаться в упорядоченном состоянии.
