Алгоритм 1. Сортировка вставками
Это изящный и простой для понимания метод. Вот в чем его суть: создается новый массив, в который мы последовательно вставляем элементы из исходного массива так, чтобы новый массив был упорядоченным. Вставка происходит следующим образом: в конце нового массива выделяется свободная ячейка, далее анализируется элемент, стоящий перед пустой ячейкой (если, конечно, пустая ячейка не стоит на первом месте), и если этот элемент больше вставляемого, то подвигаем элемент в свободную ячейку (при этом на том месте, где он стоял, образуется пустая ячейка) и сравниваем следующий элемент. Так мы прейдем к ситуации, когда элемент перед пустой ячейкой меньше вставляемого, или пустая ячейка стоит в начале массива. Помещаем вставляемый элемент в пустую ячейку . Таким образом, по очереди вставляем все элементы исходного массива. Очевидно, что если до вставки элемента массив был упорядочен, то после вставки перед вставленным элементом расположены все элементы, меньшие его, а после — большие. Так как порядок элементов в новом массиве не меняется, то сформированный массив будет упорядоченным после каждой вставки. А значит, после последней вставки мы получим упорядоченный исходный массив. Вот как такой алгоритм можно реализовать на языке программирования Pascal:
Program InsertionSort;
Var A,B : array[1..1000] of integer;
N,i,j : integer; Begin
{Определение размера массива A (N) и его заполнение}
… {сортировка данных} for i:=1 to N do
begin
j:=i;
while (j>1) and (B[j-1]>A[i]) do
begin
B[j]:=B[j-1];
j:=j-1;
end;
B[j]:=A[i];
end;
{Вывод массива B} …
End.
Program InsertionSort;
Var A,B : array[1..1000] of integer;
N,i,j : integer; Begin {Определение размера массива A (N) и его заполнение}
…
{сортировка данных} for i:=1 to N do
begin
j:=i;
while (j>1) and (B[j-1]>A[i]) do
begin
B[j]:=B[j-1];
j:=j-1;
end;
B[j]:=A[i];
end;
{Вывод массива B}
… End. |
В принципе, данную сортировку можно реализовать и без дополнительного массива B, если сортировать массив A сразу при считывании, т. е. осуществлять вставку нового элемента в массив A.
