Простые вставки

Пусть в заданной последовательности а₁, А₂, ..., А_N первые I-1 элементов уже отсортированы. Найдем в этой части последовательности место для I-го элемента. Для этого будем сравнивать его по порядку со всеми элементами, стоящими левее, до тех пор пока не окажется, что некоторый А_K<= а_I. Затем сдвинем часть последовательности А_K+1, А_K+2, ..., А_I-1 на один элемент вправо и освободим таким образом место А_K+1для элемента А_I , куда его и поставим. Эта последовательность действий отображена на Рис. 2 при упорядочивании последовательности треугольников разной высоты. Считая, что первые три элемента уже упорядочены, ищем место для четвертого по вышеизложенному правилу. Знак <= (а не <) показывает, когда нужно прекратить сравнения, т. е. движение влево по последовательности. При этом достигается устойчивость сортировки вставками.

После того как мы проделаем подобные действия для всех элементов от 2-го до N-го, мы получим отсортированную последовательность. Отметим очень важную деталь в наших действиях. Когда мы проводим сравнение I-го элемента со всеми, стоящими левее него, может оказаться, что не найдется такого Ак, что А_K<= а_I; это произойдет, если А_I меньше всех левых элементов. На Рис. 2 эта ситуация отмечена дорожным знаком "Прочие опасности". В этом случае нужно закончить просмотр (по достижении первого элемента последовательности) и осуществить сдвиг A₁, ..., A_I-1 вправо, а элемент A_I поставить на первое место.

Составим алгоритм решения этой задачи. Как и в предыдущих случаях, основным оператором здесь будет цикл, определяющий, для какого элемента последовательности мы ищем место в упорядоченной левой части.

I := 2; пока I <= N нц найти место Ак для А_I, в упорядоченной части последовательности (1)   сдвинуть элементы А_к+1, А_к+2,:, A_i-1 вправо (2)   поставить элемент А_I на нужное место (3)   I := I+1 кц

В результате действия 1 мы должны получить номер К, индекс элемента, рядом с которым справа нужно поставить А_I.

Чтобы найти место для А_I, нужно сравнивать его последовательно со всеми левыми соседями до элемента А_K<= а_I и, если такового не окажется, остановиться на первом элементе. Действия эти - циклические, причем удобнее оформить цикл по текущему номеру элемента. Получим:

1 инициализация цикла (1.1) пока J>0 нц сравнить элементы а_I и a_J (1.2) кц

Обдумывая пункт 1.1 - инициализацию цикла, мы должны предусмотреть три момента. Во-первых, значение элемента а_I; нужно запомнить, так как иначе при сдвиге оно может потеряться. Во-вторых, нужно зафиксировать номер I-1 - с этого элемента начнется сравнение. В-третьих, нужно позаботиться о том, чтобы в ситуации, когда а_I, меньше A₁, A₂..., A_I-1, он смог встать на первое место. Следовательно, получаем:

1.1 X := A[I]; J := I-1; K := 1

Далее, по результатам сравнения а_I, и a_J мы должны сделать вывод о том, продолжать сравнение или нужный элемент уже найден и пора закончить цикл. Закончить цикл можно присваиванием переменной J нулевого значения. Имеем:

1.2 если A[I] >= A[J]   то K := J+1; J := 0   иначе J := J-1 все

Перейдем к детализации пункта 2. Для сдвига последовательности вправо нужно просматривать ее из конца в начало и последовательно сдвигать элементы.

2. J := I пока J>K нц A[J] := A[J-1]   J := J-1 кц

Пункт 3 - это один оператор присваивания:

3. A[K] := X

И наконец, законченный алгоритм сортировки простыми вставками. алг ВСТАВКА (цел N, вещ таб A[1:N]) арг A, N рез A нач цел I, J, K, вещ X I := 2 пока I <= N нц X := A[I]; J := I-1; K := 1   пока J>0   нц если A[I] >= A[J]       то K := J+1; J := 0       иначе J := J-1     все   кц   J := I   пока J>K   нц A[J] := A[J-1]     J := J-1   кц   A[K] := X;   I := I+1 кц кон

На паскале

Program SortByVstavka;

var A: array of Integer;

i, j, key: Integer;

begin

//Заполняем массив A

for i := 0 to Length(A) - 1 do

begin

key := A[i];

j := i - 1;

while (j >= 0) and (A[j] > key) do

begin

A[j + 1] := A[j];

j := j - 1;

A[j + 1] := key;

end;

end;

End.

Найти номер минимального элемента последовательности (все элементы разные).

const m = 10;

type mass = array [1..m] of real;

procedure nommin (x:mass; n:integer; var nom:integer);

var i : integer; min : real;

begin min := x[i]; nom := 1;

for i := 2 to n do

if min > x[i] then begin

min := x[i];

nom := i

end

end;

Найти номер элемента с заданным значением (все элементы разные).

Не отсортированный массив

const m=10;

type mass = array [1..m] of integer;

procedure poisk (x:mass; n,p:integer; var k:integer);

var i : integer;

begin

i := 1; k := 0;

while i <= n do

if x[i]=p

then begin k := i; i := n+1

end

else i := i + 1

end;

Отсортированный массив

алг ДИХ (цел N, цел таб X[1:N], цел P,K) арг X, N, P рез K нач цел A, B, C A := 1; B := N пока A<B   нц C := INT((A+B)/2)   если X[С]<P     то A := C+1     иначе B := C   все кц если X[A]=P   то K := A   иначе K := 0 все кон