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

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

В начале работы алгоритмы в качестве отсортированной части массива принимают только один первый элемент, а в качестве неотсортированной части – все остальные элементы.

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

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

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

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

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

1 шаг:

3

2 шаг:

1

3 шаг:

1

4 шаг:

1

5 шаг:

1

Результат:

БЛОК – СХЕМА

I = 2

Æ 1

J = 1 R = A(I) IR =

Æ 1

I = I + I

1 Æ

IR = 1

1 Æ

J = J+1

K = I - 1

1

A(J) = R IR = 2

A(K+1) = A(K) K = K - 1

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

Program Insertion Sort;

Uses Crt;

Const

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

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;

{ - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - }

Writein (‘Отсортированный массив:’);

For i: = 1 to n do write (‘vector [i]: 8: 2);

Writeln;

End.

Результат работы:

Bведите элементы массива: Отсортированный массив: