Создание программ, выполняющих сортировку массива тремя методами

Министерство образования Российской федерации

УГТУ – УПИ

Филиал в г. Краснотурьинске

Кафедра вычислительной техники

Отчет

По лабораторной работе №7

По теме ,,Сортировка массивов.”

Преподовалель                                                                           О. В. Мезенцева

Студент                                                                                       Д. В. Поздняков

Группа                                                                                              Р - 131 КТ

2003

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

Задания:

а)Случайным образом дан массив, размером n .Выполниь его сортировку и подсчитать число сровнений и перестановок в кождом случае

1.   Блок – схемы

а)

 

                                                           

 

 

 

3.Программы :

a) program overdrive;

uses crt;

type over=array[1..100] of integer;

var b,a,c:over;

i,j,m,n,p,v,t,d,k,h,z,max,min,buff:word;

begin

clrscr;

write('введите размер массива n=');

readln(n);

randomize;

for i:=1 to n do

a[i]:=random(100-50);

begin b:=a;

for i:=1 to n do begin

max:=b[1];k:=1;

for j:=2 to n do begin

t:=t+1;

if b[j]>max then begin

max:=b[j]; k:=j; end; end;

c[n-i+1]:=max;

d:=d+1; b[k]:=0; end;

writeln('Сортировка методом максимумов:');

writeln('число сравнений t=',t);

writeln('число перестановок d=',d);

b:=c; end; writeln;

begin b:=a;

for i:=2 to n do begin

for j:=1 to i-1 do begin

h:=h+1; if b[i]<b[j] then begin buff:=b[i];

for k:=i-1 downto j do begin

z:=z+1; b[k+1]:=b[k]; end;

b[j]:=buff; end; end; end;

writeln('сортировка простыми включениями:');

writeln('число сравнений h=',h);

writeln('числ перестановок z=',z); end; writeln;

begin b:=a;

for i:=1 to (n div 2) do begin

min:=b[i]; k:=0;

for j:=(i+1) to (n-i+1) do BEGIN inc(p);

if b[j]<min then

begin

min:=b[j]; k:=j; end; end;

if k>0 then begin

for j:=k-1 downto i do begin inc(v);

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

end; b[i]:=min; end;

max:=b[n-i+1]; k:=0;

for j:=(i+1) to (n-i+1) do begin

inc(p);

if b[j]>max then

begin max:=b[j];

k:=j; end; end; if k>0 then

for j:=k to (n-i+1) do begin inc(v);

b[j]:=b[j+1]; end;

b[n-i+1]:=max; end; end;

writeln('Шейкер сортировка :');

writeln('число сравнений=',p);

writeln('число перестановок v=',v);

writeln; begin

writeln('исходный массив a');

for i:=1 to n do

write(a[i],' ');

writeln; end;

begin

writeln('полученный массив b');

for i:=1 to n do

write(b[i],' ');

end;

readln;

end.

 4. Результат

   а)  n = 9

Сортировка методом максимумов:

Число сравнений       t = 72

Число перестановок  d = 9

Сортировка простыми включениями:

Число сравнений       h = 36

Число перестановок  z = 19

Шейкер сортировка:

Число сравнений       p = 40

Число перестановок  v = 22

Исходный массив     а:  29  33  19  38  24  1   34  30  26  

полученный массив b:   1  19  24  26  29  30  33  34  38

Вывод: создал программы, выполняющие сортировку массива тремя методами: сортировка методом максимумов, сортировка простыми включениями, шейкер сортировка.