4 Прохід

A

1	2	3	4	5	6	7	8=N
2	3	5	8	6	10	11	18

{L=4; R=5}

Умова: L<R => true => у зовнішній цикл заходимо:

Imin:=L; {Imin=4}

Imax:=L; {Imax=4}

Робимо прохід по і {від L+1 до R} комірках:

{i=5} Якщо A[i]<A[Imin] => true =>Imin:=I {Imin=5}

Міняємо елементи місцями:

B:=A[Imin]; A[Imin]:=A[L]; A[L]:=B; {A[4]=6; A[5]=8}

Якщо Imax=L => true =>міняємо елементи місцями:

{R=Imin => заміну елементів проводити не треба}

Маємо відсортований масив:

A

1	2	3	4	5	6	7	8=N
2	3	5	6	8	10	11	18

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

За Віртом для масиву з 256 елементами: 0,82с. – найкращий випадок, 0,96 – середній, 2,04 – найгірший.

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

program Select4;

const n=10;

type

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

var

A : TVector;

B : integer;

L, R, i, imin, imax : word;

Begin

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

readln;

L:=1; R:=n;

while L<R do

begin

imin:=L; imax:=L;

for i:=L+1 to R do

if A[i] < A[imin] then

imin:=i

else

if A[i] > A[imax] then

imax:=i;

B:=A[imin];

A[imin]:=A[L];

A[L]:=B;

if imax=L then

begin

B:=A[imin];

A[imin]:=A[R];

A[R]:=B;

end

else begin

B:=A[imax];

A[imax]:=A[R];

A[R]:=B;

end;

L:=L+1; R:=R-1;

end;

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

writeln;

End.

3. Алгоритм сортування №3 методу прямого обміну (із запам’ятовуванням місця останньої перестановки).

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

1. Присвоюємо межі сортування значення кількості елементів масиву;

2. Головний цикл діє поки значення межі сортування більше за 1:

а) номеру останньої перестановки присвоюємо 1;

б) внутрішній цикл проходить по i{від 1 до номера, попереднього межі сортування} комірках:

якщо поточний елемент більший за наступний, то вони міняються місцями, номер поточного елемента запам‘ятовується;

в) Межі сортування присвоюється значення останньої перестановки;

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

n– кількість елементів масиву;

k – місце останньої перестановки;

R – значення межі сортування;

i – лічильник внутрішнього циклу;

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

А

1	2	3	4	5	6	7	8=n
16	3	7	11	5	8	2	14

R:=n; {R=8}

1 Прохід

Умова: R>1 => true =>

k:=1;

Робимо прохід по i {від 1 до R-1} комірках:

{i=1} Якщо A[i]>A[i+1] => true => замінюємо місцями елементи:

B:=A[i]; A[i]:=A[i+1]; A[i+1]:=B; {A[1]=3; A[2]=16} k:=i; {k=1}

{i=2} Якщо A[i]>A[i+1] => true => замінюємо місцями елементи:

B:=A[i]; A[i]:=A[i+1]; A[i+1]:=B; {A[2]=7; A[3]=16} k:=i; {k=2}

{i=3} Якщо A[i]>A[i+1] => true => замінюємо місцями елементи:

B:=A[i]; A[i]:=A[i+1]; A[i+1]:=B; {A[3]=11; A[4]=16} k:=i; {k=3}

{i=4} Якщо A[i]>A[i+1] => true => замінюємо місцями елементи:

B:=A[i]; A[i]:=A[i+1]; A[i+1]:=B; {A[4]=5; A[5]=16} k:=i; {k=4}

{i=5} Якщо A[i]>A[i+1] => true => замінюємо місцями елементи:

B:=A[i]; A[i]:=A[i+1]; A[i+1]:=B; {A[5]=8; A[6]=16} k:=i; {k=5}

{i=6} Якщо A[i]>A[i+1] => true => замінюємо місцями елементи:

B:=A[i]; A[i]:=A[i+1]; A[i+1]:=B; {A[6]=2; A[7]=16} k:=i; {k=6}

{i=7} Якщо A[i]>A[i+1] => true => замінюємо місцями елементи:

B:=A[i]; A[i]:=A[i+1]; A[i+1]:=B; {A[7]=14; A[8]=16} k:=i; {k=7}

R:=k; {R=7};