Сортировка вставками. достаточно простой, но очень эффективный в некоторых случаях способ сортировки

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

Псевдокод алгоритма сортировки вставками:

Процедура BoobleSort(A: массив, min - начальный индекс, max - конечный индекс);
Начало
Цикл для i от min+1 до max
j=i
tmp=Ai; //запоминаем значение ещё неотсортированного элемента
цикл пока (j> 0 и Aj-1> tmp): //Сравниваем очередной отсортированный элемент, если он больше,
1. Aj=Aj-1 //то сдвигаем его в большую сторону, освобождая место для вставки
2. j=j-1 //Переходим к следующему элементу в отсортированной части массива
Aj=tmp; //Место для нового элемента определено - вставляем его туда
Конец процедуры

Реализация алгоритма сортировки вставками:

type TArray: Array of Integer; //Параметры массива нужно определить до вызова процедуры

procedure booblesort(var A: TArray; min, max: Integer);
var i, j, tmp: Integer;
begin
for i: =min+1 to max do
begin
j: =i;
tmp: =A[i];
while ((j> 0)and(A[j-1]> tmp)) do
begin
A[j]: =A[j-1];
j: =j-1;
end;
A[j]: =tmp;
end;
end;

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

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

Таким образом, для массива в 100 000 элементов требуется максимально не 100 000, а не более 18 (100 000 < 218) сравнений для нахождения места вставки, для массива из миллиона элементов - не более 21. Правда, дополнительные затраты времени нужны для организации цикла сдвига. Тем не менее, время сортировки ощутимо сокращается:

type TArray: Array of Integer; //Параметры массива нужно определить до вызова процедуры

procedure injection(var A: TArray; min, max: Integer);
var i, j, k, tmp: Integer;
function seek(min, max, T: Integer): Integer;
begin
Result: =min+Round((max-min)/2);
if max-min< =1 then
Result: =Result+1 else
if T< A[Result]
then
Result: =seek(min, Result, T)
else
Result: =seek(Result, max, T)
end;
begin
for i: =min+1 to max do
begin
if A[i]> =A[i-1] then continue;
if A[i]< A[min]
then j: =min
else j: =seek(min, i-1, A[i]);
tmp: =A[i];
for k: =i downto j+1 do
A[k]: =A[k-1];
A[j]: =tmp;
end;
end;

Для поиска места вставки процедура сортировки использует внутреннюю рекурсивную функцию seek, реализующую метод половинного деления, постепенно уменьшающий область поиска до искомого индекса.