Алгоритм 1. Сортировка вставками

Алгоритм 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.

В принципе, данную сортировку можно реализовать и без дополнительного массива B, если сортировать массив A сразу при считывании, т. е. осуществлять вставку нового элемента в массив A.