1. Алгоритм сортування №1 методу прямої вставки (з лінійним пошуком місця вставки від початку послідовності, що сортується , або «зліва»).

Загальна схема

Принцип сортування №1 методу прямої вставки (з лінійним пошуком місця вставки від початку послідовності, що сортується , або «зліва») заключається в тому, що ми проходимо масив від 2 елементу до кінця і на кожному етапі проходу виконуємо такі дії:

1. Елемент поточної позиції зберігаємо в допоміжній комірці пам‘яті B;

2. Порівнюючи елемент B із попередніми по черзі, визначаємо його правильне місце у масиві і, якщо потрібно, виконуємо зсув елементів масиву вправо з позиції правильного місця елементу B до позиції елемента, попереднього поточному (порівнюємо за визначеною умовою);

3. На визначену позицію вставляємо елемент, записаний на початку проходу.

А ­– даний масив;

І – лічильник основного циклу;

J – змінна потрібної позиції;

K – лічильник зсуву елементів масиву вправо;

Маємо початковий масив:

А

1	2	3	4	5	6	7	8
7	1	3	6	14	9	5	4

B

1. прохід {i=2}

А

1	2	3	4	5	6	7	8
7	1	3	6	14	9	5	4

B

1

J:=1; {A[j]=7} B:=1; { B:=A[i] }

Умова: B>A[j] => false => у внутрішній цикл не заходимо

{i-1=1; j=1 => K=1 ^-1 > 1}

A[2]:=A[1]; {A[2]:=7;}

A[j]:=B {A[1]:=1}

А

1	2	3	4	5	6	7	8
7{1}	1{7}	3	6	14	9	5	4

B

1

2. прохід {i=3}

А

1	2	3	4	5	6	7	8
1	7	3	6	14	9	5	4

B

3

J:=1; {A[j]=1} B:=3; { B:=A[i] }

Умова: B>A[j]=> true => у внутрішній цикл заходимо

j:=j+1; {j=2; A[j]=7}

B>A[j]=> false => у внутрішній цикл не заходимо

{i-1=2; j=2;=>K=2 ^-1 > 2}

A[3]:=A[2]; {A[3]=7}

A[j]:=B; {A[2]=3}

А

1	2	3	4	5	6	7	8
1	7{3}	3{7}	6	14	9	5	4

B

3

3. прохід {i=4}

А

1	2	3	4	5	6	7	8
1	3	7	6	14	9	5	4

B

6

J:=1; {A[j]=1} B:=6; { B:=A[i] }

Умова: B>A[j]=> true => у внутрішній цикл заходимо:

j:=j+1; {j=2; A[j]=3}

B>A[j]=> true => у внутрішній цикл заходимо:

j:=j+1; {j=3; A[j]=7}

B>A[j]=> false => у внутрішній цикл не заходимо

{i-1=3; j=3; k=3 ^-1 > 3}

A[4]:=A[3]; {A[4]=7}

A[j]:=B; {A[3]=6}

А

1	2	3	4	5	6	7	8
1	3	7{6}	6{7}	14	9	5	4

B

6

4. прохід {i=5}

А

1	2	3	4	5	6	7	8
1	3	6	7	14	9	5	4

B

14

J:=1; {A[j]=1} B=14; { B:=A[i] }

Умова: B>A[j]=> true => у внутрішній цикл заходимо:

j:=j+1; {j=2; A[j]=3}

B>A[j]=>true => у внутрішній цикл заходимо:

j:=j+1; {j=3; A[j]=6}

B>A[j]=>true => у внутрішній цикл заходимо:

j:=j+1; {j=4; A[j]=7}

B>A[j]=>true => у внутрішній цикл заходимо:

j:=j+1; {j=5; A[j]=14}

B>A[j]=> false =>у внутрішній цикл не заходимо;

{i-1=4; j=5; k=4 ^-1 > 5 – у внутрішній цикл не заходимо}

Масив залишається без змін:

А

1	2	3	4	5	6	7	8
1	3	6	7	14	9	5	4

5. прохід {i=6}

А

1	2	3	4	5	6	7	8
1	3	6	7	14	9	5	4

B

9

J:=1; {A[j]=1} B:=9; { B:=A[i] }

Умова: B>A[j]=> true => у внутрішній цикл заходимо:

j:=j+1; {j=2; A[j]=3}

B>A[i] => true => у внутрішній цикл заходимо:

j:=j+1; {j=3; A[j]=6}

B>A[i] => true => у внутрішній цикл заходимо:

j:=j+1; {j=4; A[j]=7}

B>A[i] => true => у внутрішній цикл заходимо:

j:=j+1; {j=5; A[j]=14}

B>A[i] => false => у внутрішній цикл не заходимо:

{i-1=5; j=5; k=5 ^-1 > 5 }

A[6]:=A[5]; {A[6]=14}

A[j]:=B {A[5]=9}

А

1	2	3	4	5	6	7	8
1	3	6	7	14{9}	9{14}	5	4

B

9

6. прохід {i=7}

А

1	2	3	4	5	6	7	8
1	3	6	7	9	14	5	4

B

5

J:=1; {A[j]=1} B:=5; { B:=A[i] }

Умова: B>A[j]=> true => у внутрішній цикл заходимо:

j:=j+1; {j=2; A[j]=3}

B>A[j]=> true => у внутрішній цикл заходимо:

j:=j+1; {j=3; A[j]=6}

B>A[j]=> false => у внутрішній цикл не заходимо:

{i-1=6; j=3; k=6 ^-1 > 3 }

A[7]:=A[6]; {A[7]=14}

A[6]:=A[5]; {A[6]=9}

A[5]:=A[4]; {A[5]=7}

A[4]:=A[3]; {A[4]=6}

A[j]:=B; {A[3]=5}

А

1	2	3	4	5	6	7	8
1	3	6{5}	7{6}	9{7}	14{9}	5{14}	4

B

5

7. прохід {i=8}

А

1	2	3	4	5	6	7	8
1	3	5	6	7	9	14	4

B

4

J:=1; {A[j]=1} B:=4; { B:=A[i] }

Умова: B>A[j] => true => у внутрішній цикл заходимо:

j:=j+1; {j=2; A[j]=3}

B>A[j]=>true => у внутрішній цикл заходимо:

j:=j+1; {j=3; A[j]=5}

B>A[j] =>false => у внутрішній цикл не заходимо

{i-1=7; j=3; k=7 ^-1 > 3 }

A[8]:=A[7] {A[8]=14}

A[7]:=A[6] {A[7]=9}

A[6]:=A[5] {A[6]=7}

A[5]:=A[4] {A[5]=6}

A[4]:=A[3] {A[4]=5}

A[j]:=B {A[3]=4}

А

1	2	3	4	5	6	7	8
1	3	5{4}	6{5}	7{6}	9{7}	14{9}	4{14}

B

4

Основний цикл завершено, маємо відсортований масив:

А

1	2	3	4	5	6	7	8
1	3	4	5	6	7	9	14

Загальновідома оцінка роботи цього алгоритму:

За Віртом для масиву з 256 елементами: 0,02с. – найкращий випадок, 0,94 – середній, 1,26 – найгірший.

Алгоритм має вигляд (для одновимірного масиву):

program Insert1;

const n=10;

type

TVector=array[1..n] of integer;

var

A : TVector;

B : integer;

i, j, k : word;

Begin

for i:=1 to n do read(A[i]);

readln;

for i:=2 to n do

begin

B:=A[i];

j:=1;

while B>A[j] do j:=j+1;

for k:=i-1 downto j do

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

A[j]:=B;

end;

for i:=1 to n do write(A[i]:8);

writeln;

End.