Сортировка вставками.

Теория метода:

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

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

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

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

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

Пример:

38 12 80 15 36 23 74 62 – исходный массив

38 12 80 15 36 23 74 62 – 1 проход

12 38 80 15 36 23 74 62 – 2 проход

12 38 80 15 36 23 74 62 – 3 проход

12 15 38 80 36 23 74 62 – 4 проход

12 15 36 38 80 23 74 62 – 5 проход

и так далее

Размещение элемента массива на соответствующем ему месте в уже упорядоченной последовательности может быть определено следующими способами:

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

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

3. Поиск места вставки методом двоичного включения. Так как последовательность в которую вставляем очередной элемент является упорядоченной, то используется метод двоичного поиска при котором делается попытка сравнить вставляемый элемент с серединой готовой последовательности. Затем процесс деления пополам идет до тех пор, пока не будет найдена точка включения.

Реализация метода размещения путем сравнения и обмена (1-ый способ).

Program sort_vstav1;

const n=10;

M:array[1..n] of byte = (9,11,12,3,19,1,5,17,10,7);

var

i,j,b:byte;

BEGIN

for i:=2 to n do

begin

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

j:=i-1;

{Цикл поиска позиции вставки в отсортированном массиве}

while (j>0)and(m[j]>=b) do

begin

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

j:=j-1;

end;

m[j+1]:=b; {Вставка взятого элемента на найденную позицию}

end;

for i:=1 to n do

write(a[i]:3);

END.

Реализация метода размещения путем поиска места в вставки (2-ой способ).

Program sort_vstav2;

const n=10;

M:array[1..n] of byte = (9,11,12,3,19,1,5,17,10,7);

var

i,j,k,b:byte;

BEGIN

for i:=2 to n do

begin

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

j:=1;

{Цикл поиска позиции вставки в отсортированном массиве}

while (b>m[j]) do

j:=j+1; {После окончания цикла индекс j фиксирует позицию вставки}

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

for k:=i-1 downto j do

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

m[j]:=b; {Вставка взятого элемента на найденную позицию}

end;

for i:=1 to n do

write(a[i]:3);

END.