Лабораторная работа №5
.docxМинистерство образования и науки Российской Федерации
Федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования «Вятский государственный университет»
(ФГОУ ВПО «ВятГУ»)
Отчет по лабораторной работе №5
Исследование алгоритмов сортировки.
Выполнил студент группы ИВТ-11________________________Гонин С.А.
Проверил преподаватель_________________________________Чистяков Г.А.
Киров, 2013
Цель работы: получить базовые сведения о наиболее известных алгоритмах сортировки, изучить принципы работы с текстовыми файлами.
Задание:
1. Реализовать сортировку данных с помощью алгоритма выбором.
2. Реализовать сортировку данных с помощью быстрого алгоритма.
3. В обоих случаях необходимо предусмотреть возможность изменения компаратора (реализация компаратора в виде передаваемой в подпрограмму функции).
4. Считывание и вывод данных необходимо производить из текстового файла.
5. Для демонстрации работы программных реализаций самостоятельно подготовить варианты входных данных (при этом объем тестовых файлов должен позволять оценить скорость работы программ).
Код программы №1:
program laba5_1;
uses crt;
type mass=array[1..10000000] of longint;
var
f1,f2:text;
i,n,z,j:longint;
a:mass;
function comp(var a,b :longint):boolean;
begin
if a>b then
comp:=true
else
comp:=false;
end;
procedure sortselect(var a:mass; l,r:longint);
var s,min:longint;
begin
for i:=1 to n-1 do
begin
min:=i;
for j:=i+1 to n do
if a[min]<a[j] then
min:=j;
if min<>i then
begin
s:=a[i];
a[i]:=a[min];
a[min]:=s;
end;
end;
end;
begin
assign(f1,'input.txt');
reset(f1);
read(f1,n);
for i:=1 to n do
read(f1,a[i]);
sortselect(a,1,n);
assign(f2,'output.txt');
rewrite(f2);
for i:=1 to n do
write(f2,a[i],' ');
close(f2);
end.
Код программы №2:
program laba5_1;
uses crt;
type mass=array[1..10000000] of longint;
var
f1,f2:text;
i,n,z,j:longint;
a:mass;
function comp(var a,b :longint):boolean;
begin
if a<b then
comp:=true
else
comp:=false;
end;
procedure sortselect(var a:mass; l,r:longint);
var s,min:longint;
begin
for i:=1 to n-1 do
begin
min:=i;
for j:=i+1 to n do
if a[min]>a[j] then
min:=j;
if min<>i then
begin
s:=a[i];
a[i]:=a[min];
a[min]:=s;
end;
end;
end;
begin
assign(f1,'input.txt');
reset(f1);
read(f1,n);
for i:=1 to n do
read(f1,a[i]);
sortselect(a,1,n);
assign(f2,'output.txt');
rewrite(f2);
for i:=1 to n do
write(f2,a[i],' ');
close(f2);
end.
Код программы №3:
program lab5;
uses crt;
type mas=array[1..1000000] of longint;
var
f1,f2:text;
i,n,start:longint;
a:mas;
procedure quicksort(l, r: longint);
var
i, j, x, y: longint;
begin
i := l;
j := r;
x := a[(l+r) div 2];
repeat
while a[i] > x do inc(i);
while a[j] < x do dec(j);
if i <= j then
begin
y := a[i];
a[i] := a[j];
a[j] := y;
inc(i);
dec(j);
end;
until i > j;
if l < j then quicksort(l, j);
if i < r then quicksort(i, r);
end;
begin
assign(f1,'input.txt');
reset(f1);
read(f1,n);
for i:=1 to n do
read(f1,a[i]);
quicksort(1,n);
assign(f2,'output.txt');
rewrite(f2);
for i:=1 to n do
write(f2,a[i], ' ');
close(f2);
end.
Код программы №4:
program lab5;
uses crt;
type mas=array[1..1000000] of longint;
var
f1,f2:text;
i,n,start:longint;
a:mas;
procedure quicksort(l, r: longint);
var
i, j, x, y: longint;
begin
i := l;
j := r;
x := a[(l+r) div 2];
repeat
while a[i] < x do inc(i);
while a[j] > x do dec(j);
if i <= j then
begin
y := a[i];
a[i] := a[j];
a[j] := y;
inc(i);
dec(j);
end;
until i > j;
if l < j then quicksort(l, j);
if i < r then quicksort(i, r);
end;
begin
assign(f1,'input.txt');
reset(f1);
read(f1,n);
for i:=1 to n do
read(f1,a[i]);
quicksort(1,n);
assign(f2,'output.txt');
rewrite(f2);
for i:=1 to n do
write(f2,a[i], ' ');
close(f2);
end.
Вывод: в ходе лабораторной работы были получены базовые сведения об алгоритмах сортировки на примере быстрой сортировки и сортировки выбором с возможностью изменения компаратора, а также изучены основные принципы работы с текстовыми файлами.