Простейшие методы сортировки: метод вставок

Данный метод также относится к классу простейших, но по сравнению с методом пузырька имеет немного лучшие показатели.

Пусть имеется n элементов а₁ а₂, а₃, . . ., а_n, расположенных в ячейках массива. Сортировка выполняется за (n–1) шаг, причем шаги удобно нумеровать от 2 до n. На каждом i-ом шаге обрабатываемый набор разбивается на 2 части:

· левую часть образуют уже упорядоченные на предыдущих шагах элементы а₁, а₂, а₃, . . ., а_i-1

· правую часть образуют еще не обработанные элементы а_i, а_i+1, а_i+2, . . ., а_n

На шаге i для элемента а_i находится подходящее место в уже отсортированной последовательности. Поиск подходящего места выполняется поэлементными сравнениями и перестановками по необходимости: сравниваем а_i с а_i-1, если а_i < а_i-1, то переставляем их, потом сравниваем а_i-1 с а_i-2 и т. д. Сравнения и, возможно, перестановки продолжаются до тех пор, пока не будет выполнено одно из 2-х следующих условий:

· в отсортированном наборе найден элемент, меньший а_i (все остальные не просмотренные элементы будут еще меньше)

· достигнут первый элемент набора а₁, что произойдет в том случае, если а_i меньше всех элементов в отсортированном наборе и он должен занять первое место в массиве

Пример. Возьмем тот же исходный набор целых чисел: 15-33-42-07-12-19

Для данного примера было сделано 12 сравнений и 8 перестановок, что чуть лучше предыдущего метода. В среднем, число сравнений по данному методу примерно в 2 раза меньше, чем в методе пузырька, оставаясь тем не менее пропорциональным величине n². Наилучший результат этот метод показывает для уже упорядоченного исходного массива – всего (n-1) сравнение.

Программная реализация включает два вложенных цикла, но в отличие от предыдущего метода, внутренний цикл реализуется как while-do с возможностью остановки при обнаружении меньшего элемента.

for i := 2 to n do

Begin

temp := a [i]; j := i – 1;

While (j > 0) and (temp < a [j] ) do

begin a [j+1] := a [j]; j := j – 1; end;

a [j+1] := temp;

end;