Министерство образования Российской федерации
УГТУ – УПИ
Филиал в г. Краснотурьинске
Кафедра вычислительной техники
По теме ,,Сортировка массивов.”
Студент Д. В. Поздняков
Группа Р - 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
Вывод: создал программы, выполняющие сортировку массива тремя методами: сортировка методом максимумов, сортировка простыми включениями, шейкер сортировка.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.