Сортировка вставками - достаточно простой, но очень эффективный в некоторых случаях способ сортировки. Массив чисел сортируется с начала, и каждое последующее число вставляется в уже отсортированную часть массива на предназначенное ему место. Таким образом, новое число сравнивается и при необходимости меняется местами не со всеми числами в массиве, а только до тех пор, пока в уже отсортированной части массива не найдется меньшее его число. Поэтому сортировка вставками примерно в два раза быстрее сортировки пузырьком. А для уже частично отсортированных массивов сортировка вставками - наилучший алгоритм сортировки. Время сортировки вставками также пропорционально квадрату количества элементов в массиве.
Псевдокод алгоритма сортировки вставками:
Процедура 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; //Место для нового элемента определено - вставляем его туда Конец процедуры
Реализация алгоритма сортировки вставками в Delphi:
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. Правда, дополнительные затраты времени нужны для организации цикла сдвига.Тем не менее, время сортировки ощутимо сокращается. Вот код на Delphi:
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, реализующую метод половинного деления, постепенно уменьшающий область поиска до искомого индекса. Попробуйте вставить эту процедуру в код программы на странице Обзор алгоритмов сортировки, сравнивающей разные алгоритмы сортировки, и оцените выигрыш по скорости. Мой результат - на сортировку миллиона чисел вместо 17 минут новый алгоритм затратил всего 7 минут!