Сортировка вставкой
Сортировка вставкой является последней из класса простых ал- горитмов сортировки. При сортировке вставкой сначала упорядочива- ются два элемента массива. Затем делается вставка третьего эле- мента в соответствующее место по отношению к первым двум элементам. Затем делается вставка четвертого элемента в список из трех элементов. Этот процесс повторяется до тех пор, пока все элементы не будут упорядочены. Например, для массива "dcab" сор- тировка вставкой будет проходить следующим образом:
- исходное состояние: d c a b;- первый проход: c d a b;
- второй проход: a c d b;
- третий проход: a b c d.
Ниже приводится алгоритм сортировки вставкой:
{ сортировка вставкой }
procedure Inser(var item: DataArray; count:integer);
var
i, l: integer;
x: DataItem;
begin
for i := 2 to count do
begin
x := item[i];
j := i-1;
while (x
begin
item[j+1] := item[j];
j := j-1;
end; item[j+1] := x; end; end; { конец сортировки вставкой }
В отличие от сортировки пузырьковым методом и сортировки вы- бором число операций сравнения для сортировки вставкой зависит от исходной упорядоченности массива элементов. Если исходный массив уже упорядочен, то число операций сравнения равно n-1. Если массив упорядочен в обратном порядке, то число операций сравнения равно 1/2 (n**2 +n)-1,давая в среднем значение 1/4 (n**2+n-2). Число операций обмена будет следующим:
- для лучшего случая: 2 (n-1);- в среднем: 1/4 (n**2+9n-10);
- для худшего случая: 1/2 (n**2+3n-4).
Таким образом, число операций обмена для худшего случая бу- дет столь же большим, как и для сортировок пузырьковым методом и сортировок выбором. Число операций обмена для среднего случая бу- дет лишь на немного меньше. Однако сортировка вставкой имеет два преимущества. Во-первых, она обладает естественным поведением, т. е. она выполняется быстрее для упорядоченного массива и дольше всего выполняется, когда массив упорядочен в обратном направле- нии. Это делает сортировку вставкой полезной для упорядочения почти отсортированных массивов. Во-вторых, элементы с одинаковыми ключами не переставляются: если список элементов сортируется с использованием двух ключей, то после завершения сортировки встав- кой он по-прежнему будет упорядочен по двум ключам.
Несмотря на то, что число сравнений может быть довольно не- большим для определенных наборов данных, постоянные сдвиги масси- ва требуют выполнения большого числа операций пересылок. Однако, сортировка вставкой имеет естественное поведение, требуя наимень- шее число операций обмена для почти упорядоченного списка и наи- большее число операций обмена, когда массив упорядочен в обратном направлении.
