Сортировка вставками
Метод называется сортировкой вставками, так как на i-м этапе "вставляем" i-й элемент A[i] в нужную позицию среди элементов А[1], А[2], ..., A[i - 1], которые уже упорядочены. После этой вставки первые i элементов будут упорядочены. Сказанное можно записать в виде следующей псевдопрограммы:
for i : = 2 to n do
переместить A[i] на позицию j < i такую, что
A[i] < A[k] для j ≤ k < i и
либо A[i] ≥ A[j - 1], либо j = 1
Чтобы сделать процесс перемещения элемента A[i] более простым, полезно ввести элемент А[0], чье значение ключа будет меньше значения ключа любого элемента А[1], ..., А[n]. Постулируем существование константы - ∞ типа keytype, которая будет меньше значения ключа любой записи, встречающейся на практике. Если такую константу нельзя применить, то при вставке A[i] в позицию j - 1 надо проверить, не будет ли j = 1, если нет, тогда сравнивать элемент A[i] (который сейчас находится в позиции j) с элементом A[j - 1]. Описанный алгоритм показан в листинге 3.
Листинг 2. Сортировка вставками
А[0].key:= - ∞;
for i:= 2 to n do
Begin
j:= i;
while (A[j] < A[j - 1]) or (j>=1) do
Begin
temp := A[j];
A[j] := A[j-1];
A[j-1] := temp;
j:= j - 1
End
End
Пример 7.2. В табл. 6 показан начальный список из табл. 5 и последовательные этапы алгоритма вставкой для i = 2, 3, ..., 6. После каждого этапа алгоритма элементы, расположенные выше линии, уже упорядочены, хотя между ними на последующих этапах могут быть вставлены элементы, которые сейчас находятся ниже линии.
Таблица 6. Этапы сортировки вставками
i | начальное положение | 1-й проход | 2-й проход | 3-й проход | 4-й проход | 5-й проход |
1669 | ||||||
1669 | 1902 | |||||
i | i = 1 | i = 2 | i = 3 | i = 4 | i = 5 | i = 6 |
Задача 7.11. Дан целочисленный массив размерностью 10 элементов. Упорядочить элементы данного массива по возрастанию вставками.
Листинг программы
program task2;
uses crt;
const n = 10;
type vector = array [1..n] of integer;
var
a : Vector;
i, j : integer;
temp : integer;
begin
clrscr;
randomize;
for i :=1 to n do a[i] := random(11)-4;
for i :=1 to n do
writeln ('a[', i, ']=', a[i]:3);
for i := 2 to n do
begin
j := i;
while (a[j] < a[j-1]) and (j>=1) do
begin
temp := a[j];
a[j] := a[j-1];
a[j-1] := temp;
j:=j-1;
end;
end;
writeln ('Отсортированный массив по возрастанию');
for i := 1 to n do
writeln ('a[', i, ']=', a[i]:3);
readln;
end.