III. Сортировка простыми вставками

Просматривать последовательно A2, ..., An и каждый новый элемент Ai вставлять на подходящее место в уже упорядоченную совокупность A(1)...A(i-1). Это место определяется последовательным сравнением Ai с упорядоченными элементами A(1), ..., A(i-1).

Примеры решений задач

1. Сортировка отбором.

Procedureotbor (Var x:arr; dlina:integer);

Var mal: dano;

Min, k,j: integer;

Begin

For k:=1 to dlina-1 do

Begin

Mal:=x[k];

Min:=k;

For j:=k+1 todlinado

If x[j]<mal then

Begin

Mal:=x[j];

Min:=j;

End;

X[min]:=x[k];

X[k]:=mal

End

End

2. Сортировка методом пузырька.

ProcedureBubble(VarX:massiv; DLINA:integer);

Var A:dannoe;

J,R: integer;

ZAMENA: boolean;

Begin

Repeat

ZAMENA:=false;

ForJ:=2 toRdo

IfX[j-1]>X[J]then

Begin

A:=X[J-1];

X[J-1]:=X[J];

X[J]:=A;

ZAMENA:= true

End;

R:=R-1

Until notZAMENA;

End.

3. Сортировка методом простых вставок.

Procedure simpins (Var a:arr);

Var j,j,k: word;

T: integer;

Begin

For i:=2 to n do

Begin

T:=a[i];

J:=1;

While (t>=a[j]) and (j<i) do inc(j);

If j<>i then

For k:=j-1 downto j do a[k+1]=a[k];

A[j]:=t

End;

End;

End.

4.Задача поиска места элемента. Для решения задачи полезен алгоритм, который называется алгоритмом деления пополам.

Пусть дан упорядоченный по неубыванию массив целых или действительных чисел А1<=А2<=Аn. Пусть дано некоторое число В (соответственно целое или действительное), для которого нужно найти такое место среди чисел А1, ..., Аn, чтобы после вставки числа В на это место упорядоченность не нарушилась. Если вследствие равенства между собой некоторых элементов массива число В можно вставлять на разные места, то требуется определить ближайшее к началу массива место.