Метод называется сортировкой вставками, так как на 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.