program P_176552;
{ Константы }
const
NUM_CNT=100; { Количество чисел }
NUM_LO=1; { Минимальное значение }
NUM_HI=100; { Максимальное значение }
{ Типы }
type
TArray=array[1..NUM_CNT] of Integer; { Массив }
{ Процедура сортировки
Sequence - последовательность
Comparisions - сравнений
Permutations - перестановок }
TSortProc=procedure(var Sequence:TArray;var Comparisions,Permutations:Integer);
{ Заполняет массив случайными значениями в диапазоне [NUM_LO..NUM_HI] }
procedure CreateArray(var Sequence:TArray);
var
i:Integer;
begin
for i:=1 to NUM_CNT do begin
Sequence[i]:=Random(NUM_HI-NUM_LO+1)+NUM_LO;
end;
end;
{ Выводит массив }
procedure PrintArray(Message:String;Sequence:TArray);
var
i:Integer;
begin
WriteLn(Message);
for i:=1 to NUM_CNT do begin
Write(Sequence[i]:4,' ');
end;
WriteLn;
end;
{ Пузырьковая сортировка }
procedure BubbleTest(var Sequence:TArray;var Comparisions,Permutations:Integer);
var
i,j,Tmp:Integer;
begin
{ Обнулим счетчики }
Comparisions:=0;
Permutations:=0;
for i:=1 to NUM_CNT-1 do begin
for j:=1 to NUM_CNT-i do begin
Inc(Comparisions);
if Sequence[j]>Sequence[j+1] then begin
Inc(Permutations);
Tmp:=Sequence[j];
Sequence[j]:=Sequence[j+1];
Sequence[j+1]:=Tmp;
end;
end;
end;
end;
{ Сортировка включением }
procedure InclusionTest(var Sequence:TArray;var Comparisions,Permutations:Integer);
var
i,j,item:Integer;
begin
{ Обнулим счетчики }
Comparisions:=0;
Permutations:=0;
for i := 2 to NUM_CNT do begin
item:=Sequence[i];
j:=i-1;
Inc(Comparisions);
{ Ищем куда вставить }
while (j>0) and (item<=Sequence[j]) do begin
Inc(Comparisions);
Inc(Permutations);
Sequence[j+1]:=Sequence[j];
Dec(j);
end;
Inc(Permutations);
Sequence[j+1]:=item;
end;
end;
{ Помогает нам оформить вывод }
procedure Test(Message:String;Sequence:TArray;Proc:TSortProc);
var
Comparisions,Permutations:Integer;
begin
WriteLn;
Proc(Sequence,Comparisions,Permutations);
WriteLn(Message);
PrintArray('Массив после сортировки:',Sequence);
WriteLn('Сравнений:',Comparisions);
WriteLn('Перестановок:',Permutations);
end;
var
Sequence:TArray;
begin
Randomize;
{ Заполним массив }
CreateArray(Sequence);
{ Выведем его }
PrintArray('Исходный массив:',Sequence);
{ Проверяем }
Test('Пузырьковая сортировка.',Sequence,@BubbleTest);
Test('Сортировка включением.',Sequence,@InclusionTest);
end.
~/projects/Pascal> ./P_176552
Исходный массив:
61 69 74 91 28 39 13 35 77 78 42 62 12 43 37 72
34 24 70 100 23 60 27 1 63 72 60 27 24 90 83 25
60 37 52 100 11 69 71 12 52 78 81 94 64 36 32 21
86 64 77 70 42 17 13 64 3 12 23 64 33 9 88 49
8 99 68 26 15 66 38 28 86 77 98 66 8 28 59 37
49 24 82 87 3 65 19 95 94 68 27 37 55 73 68 42
6 71 60 6
Пузырьковая сортировка.
Массив после сортировки:
1 3 3 6 6 8 8 9 11 12 12 12 13 13 15 17
19 21 23 23 24 24 24 25 26 27 27 27 28 28 28 32
33 34 35 36 37 37 37 37 38 39 42 42 42 43 49 49
52 52 55 59 60 60 60 60 61 62 63 64 64 64 64 65
66 66 68 68 68 69 69 70 70 71 71 72 72 73 74 77
77 77 78 78 81 82 83 86 86 87 88 90 91 94 94 95
98 99 100 100
Сравнений:4950
Перестановок:2512
Сортировка включением.
Массив после сортировки:
1 3 3 6 6 8 8 9 11 12 12 12 13 13 15 17
19 21 23 23 24 24 24 25 26 27 27 27 28 28 28 32
33 34 35 36 37 37 37 37 38 39 42 42 42 43 49 49
52 52 55 59 60 60 60 60 61 62 63 64 64 64 64 65
66 66 68 68 68 69 69 70 70 71 71 72 72 73 74 77
77 77 78 78 81 82 83 86 86 87 88 90 91 94 94 95
98 99 100 100
Сравнений:2666
Перестановок:2666
a[i]:= random (100)+1
program Psort;
{$APPTYPE CONSOLE}
const
n=100;
type
XArray = array[1..n] of integer;
var
x,y:XArray;
i:integer;
c,m:integer;
procedure InitData;
var
i: integer;
begin
Randomize;
for i:=1 to n do begin
x[i]:=Random(n)+1;
y[i]:=x[i];
end;
end;
procedure DirectIncludeSort;
var
i,j,tmp:integer;
begin
for i:=2 to n do begin
tmp:=x[i];
j:=i;
while (j>1)and(tmp<x[j-1]) do begin
x[j]:=x[j-1];
j:=j-1;
m:=m+1;
c:=c+1;
end;
c:=c+1;
x[j]:=tmp;
m:=m+1
end
end;
procedure BubbleSort;
var
i,j,tmp:integer;
begin
for i:=1 to n-1 do
for j:=n downto i+1 do
begin
if y[j-1]>y[j] then
begin
tmp:=y[j];
y[j]:=y[j-1];
y[j-1]:=tmp;
m:=m+1;
end;
c:=c+1
end
end;
begin
InitData;
for i:=1 to n do write('x[',i,']=',x[i],' ');
writeln;
c:=0;
m:=0;
DirectIncludeSort;
writeln('c=',c,' m=',m);
for i:=1 to n do write('x[',i,']=',x[i],' ');
writeln;
c:=0;
m:=0;
BubbleSort;
Writeln('c=',c,' m=',m);
for i:=1 to n do write('x[',i,']=',y[i],' ');
writeln;
readln
end.
Если Вы уже зарегистрированы на Портале - войдите в систему, если Вы еще не регистрировались - пройдите простую процедуру регистрации.