Сортировка вставкой

Принцип метода:

Массив разделяется на две части: отсортированную и неотсортированную. Элементы из неотсортированной части поочередно выбираются и вставляются в отсортированную часть так, чтобы не нарушить в ней упорядоченность элементов. В начале работы алгоритма в качестве отсортированной части массива принимают только один первый элемент, а в качестве неотсортированной части –все остальные элементы.

Таким образом, алгоритм будет состоять из n-1 –го прохода (n –размерность массива), каждый из которых будет включать четыре действия:

- взятие очередного i -го неотсортированного элемента и сохранение его в дополнительной переменной;

- поиск позиции j в отсортированной части массива, в которой присутствие взятого элемента не нарушит упорядоченности элементов;

- сдвиг элементов массива от i-1 -го до j-1 -го вправо, чтобы освободить найденную позицию вставки;

- вставка взятого элемента в найденную j -ю позицию.

Программа, реализующая рассмотренный алгоритм, будет иметь следующий вид:

Program InsertionSort;

uses Ctr;

const

n = 20; {длина массива}

type

TVector = array [1…n] of Real;

var

Vector: TVector;

B: Real;

I, j, k: Integer;

begin

ClrScr;

Writeln ('Введите элементы массива:');

for i:=1 to n do

Read (Vector[i]);

Readln;

{_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ }

for i:=2 to n do

begin

B:= Vector[i]; {Взятие неотсортированного элемента}

{Цикл поиска позиции вставки}

j: = 1;

while (B > Vector [j]) do

j:= j + 1; {После окончания цикла индекс}

{j фиксирует позицию вставки}

{ Цикл сдвига элементов для освобождения позиции вставки }

for k:= i-1 downto j do

Vector [k +1]:= Vector [k];

{Вставка взятого элемента на найденную позицию}

Vector [j]:= B;

end;

{_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _}

Writeln (' Отсортированный массив: ');

for i:=1 to n do

Write (Vector [i]:8:2);

Writeln;

End.