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

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

Пусть имеется 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;