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

Требуется упорядочить массив B, состоящий из N элементов. Пусть B₁, B₂, …, B_i-1 уже отсортированная часть массива B, а B_i, B_i+1, …, B_n не отсортированная. Идея метода:

1) выбираем очередной элемент B_i (начинаем с i=1);

2) в упорядоченной части массива находим k-ое место, такое чтобы при вставке на это место элемента B_i порядок не нарушился;

3) все элементы начиная с B_k–го до B_i-1 сдвигаем на одну позицию вправо и вставляем элемент B_i на k-ое место;

4) повторяем пункты 1-3 до тех пор пока i < N.

2. Выполните следующие упражнения:

Задания уровня 1

Упражнение 1. Программа с процедурами сортировки простого выбора и простой вставки.

Type

Mas = Array [1 .. n] Of Integer;

Var A: Mas;

Procedure SetRandomMas ( Var A: Mas ); {Задание случайного массива}

Var i: Integer;

Begin

Randomize;

For i := 1 To n Do A[i] := Random (100);

End;

Procedure OutPutMas ( Var A: Mas ); {Вывод массива на экран}

Var i: Integer;

Begin

For i := 1 To n Do Write( A[i]:3 );

WriteLn;

End;

Procedure SortVybor ( Var A: Mas ); {Сортировка выбором}

Var i, k, m, j,Temp, Min: Integer;

Begin

For i := 1 To n Do

Begin

Min := A[i];

k := i;

For j := i+1 To n Do

If A[j] < Min Then Begin Min := A[j]; k := j; End;

Temp := Min;

For m := k-1 DownTo i DoA[m+1] := A[m];

A[i] := Temp;

End;

End;

Procedure SortVstav ( Var A: Mas ); {Сортировка вставкой}

Var i, k, j, Temp: Integer;

Begin

For i := 1 To n-1 Do

Begin

If A[i+1] < A[i] Then

Begin

j := i;

While (A[j] > A[i+1]) And (j >0) Do j := j – 1;

k := j + 1;

Temp := A[i+1];

For j := i DownTo k Do A[j+1] := A[j];

A[k] := Temp;

End;

End;

End;

Begin

ClrScr;

SetRandomMas(A);

OutPutMas(A);

SortVstav(A);