AiSD_metoda

b:=a; sort_insert(b);

output_to_file('result.txt','После сортировки вставками:',b); b:=a; sort_choice(b);

output_to_file('result.txt','После сортировки выбором:',b); b:=a; sort_hoor(b);

output_to_file('result.txt','После быстрой сортировки Хоора:',b); b:=a; sort_wf(b);

output_to_file('result.txt','После сортировки методом пирамиды Уильямса-Флойда:',b);

writeln('Ok')

end.

Исходный текстовый файл:

Сидорова Елена ИС-10-1 1993 75.8 Петров Павел ИС-10-1 1993 88.2 Иванов Алексей ИС-10-1 1993 61.8 Зосимова Елена ИС-10-2 1993 55.0

Иванов Иван ИС-10-2 1991 95.4

Результаты:
Исходный массив
|	-----------------------------------------------
|	Фамилия	|	Имя	|	Группа	| Г.р. | С.р. |
|-----------------------------------------------
|	Сидорова |		Елена|		ИС-10-1|		1993|	75.8|
|	Петров |		Павел|		ИС-10-1|		1993|	88.2|
|	Иванов |		Алексей|		ИС-10-1|		1993|	61.8|
|	Зосимова |		Елена|		ИС-10-2|		1993|	55.0|
|	Иванов |		Иван|		ИС-10-2|		1993|	95.4|
|-----------------------------------------------
После сортировки обменами:
|-----------------------------------------------
|	Фамилия	|	Имя	|	Группа	| Г.р. | С.р. |
|-----------------------------------------------
|	Зосимова |		Елена|		ИС-10-2|		1993|	55.0|
|	Иванов |		Алексей|		ИС-10-1|		1993|	61.8|
|	Иванов |		Иван|		ИС-10-2|		1991|	95.4|
|	Петров |		Павел|		ИС-10-1|		1993|	88.2|
|	Сидорова |		Елена|		ИС-10-1|		1993|	75.8|
|-----------------------------------------------

31

После сортировки вставками:
|	-----------------------------------------------
|	Фамилия	|	Имя	|	Группа	| Г.р. | С.р. |
|	-----------------------------------------------
|	Зосимова |		Елена|		ИС-10-2| 1993|			55.0|
|	Иванов |		Алексей|		ИС-10-1| 1993|			61.8|
|	Иванов |		Иван|		ИС-10-2| 1991|			95.4|
|	Петров |		Павел|		ИС-10-1| 1993|			88.2|
|	Сидорова |		Елена|		ИС-10-1|		1993|	75.8|
|-----------------------------------------------
После сортировки выбором:
|-----------------------------------------------
|	Фамилия	|	Имя	|	Группа	| Г.р. | С.р. |
|-----------------------------------------------
|	Зосимова |		Елена|		ИС-10-2| 1993|			55.0|
|	Иванов |		Алексей|		ИС-10-1| 1993|			61.8|
|	Иванов |		Иван|		ИС-10-2| 1991|			95.4|
|	Петров |		Павел|		ИС-10-1| 1993|			88.2|
|	Сидорова |		Елена|		ИС-10-1|		1993|	75.8|
|-----------------------------------------------
После быстрой сортировки Хоора:
|-----------------------------------------------
|	Фамилия	|	Имя	|	Группа	| Г.р. | С.р. |
|-----------------------------------------------
|	Зосимова |		Елена|		ИС-10-2| 1993|			55.0|
|	Иванов |		Иван|		ИС-10-2| 1991|			95.4|
|	Иванов |		Алексей|		ИС-10-1| 1993|			61.8|
|	Петров |		Павел|		ИС-10-1| 1993|			88.2|
|	Сидорова |		Елена|		ИС-10-1|		1993|	75.8|
|-----------------------------------------------
После сортировки методом пирамиды Уильямса-Флойда:
|-----------------------------------------------
|	Фамилия	|	Имя	|	Группа	| Г.р. | С.р. |
|-----------------------------------------------
|	Зосимова |		Елена|		ИС-10-2| 1993|			55.0|
|	Иванов |		Алексей|		ИС-10-1| 1993|			61.8|
|	Иванов |		Иван|		ИС-10-2| 1991|			95.4|
|	Петров |		Павел|		ИС-10-1| 1993|			88.2|
|	Сидорова |		Елена|		ИС-10-1|		1993|	75.8|
|-----------------------------------------------

32

ЛАБОРАТОРНАЯ РАБОТА №5

Алгоритмы поиска данных Цель работы: получение навыков составления программ для реали-

зации некоторых алгоритмов поиска данных на языке программирования Паскаль.

Теоретические сведения – [11, c. 61 – 81].

Задание к работе. Сформировать массив записей (не менее 5), содержащий данные по студентам в следующем виде: «Фамилия Имя Отчество Группа Город ГР RS», где ГР – год рождения, RS – средний рейтинг (данные можно считывать из предварительно набранного текстового файла). Найти студента, полностью соответствующего заданным параметрам (варианты 1-14, табл. 9) или чьи текстовые параметры содержат заданную строку (варианты 15-24).

Таблица 9 – Варианты заданий

Вар.	Поле для поиска	Алгоритм поиска
1	Фамилия
2	Имя
3	Отчество
4	Группа	Линейный (прямой) поиск
5	Город
6	Год рождения
7	Средний рейтинг
8	Фамилия
9	Имя
10	Отчество
11	Группа	Двоичный поиск
12	Город
13	Год рождения
14	Средний рейтинг
15	Фамилия
16	Имя
17	Отчество	Алгоритм Кнута-Морриса-Пратта
18	Группа
19	Город
20	Фамилия
21	Имя
22	Отчество	Алгоритм Боуэра-Мура
23	Группа
24	Город

33

САМОСТОЯТЕЛЬНАЯ РАБОТА

Разработка системы для сравнения алгоритмов сортировки данных

Теоретические сведения – [11, 14].

Задание

В соответствии с вариантом реализовать один или два заданных алгоритма (табл.10) и выполнить их анализ по критерию «Время выполнения»: для первого и второго алгоритма; для наилучшего, наихудшего и среднего случая. Критериями «Требования к объему оперативной памяти» и «Сложность алгоритма» пренебрегаем. Для исследований используется массив, состоящий из 10 000 элементов – целых чисел.

Отчет по работе должен содержать описание анализируемых алгоритмов, оценку их категорий сложности, таблицы оценок времени выполнения (общий, наихудший, наилучший случай для каждого алгоритма в каждой среде программирования) и анализ полученных результатов.

Таблица 10 – Варианты заданий

	№	Ф	Алгоритм
	1,2	А	Сортировка выбором
	3,4	Б	Сортировка вставками (метод прямого включения)
	5,6	В	Сортировка прямыми обменами (пузырьковый метод)
	7	Г	Шейкерная сортировка (улучшенный пузырьковый метод)
	8	Д	Улучшенная сортировка вставками (метод Шелла)
	9,10	Е,Ж	Сортировка с помощью дерева (метод Уильямса-Флойда)
	11,12	З,И	Быстрая сортировка (метод Хоора)
	13	К	Улучшенная быстрая сортировка (метод медианы из трех
			элементов)
	14	Л	Быстрая сортировка с разделением на три части (метод
			Бентли-Макилроя)
	15	М	Сортировка двухпутевым слиянием
	16	Н	Сортировка абстрактным обменным слиянием
	17	О	Нисходящая сортировка слиянием
	18	П	Сортировка слиянием без копирования
	19	Р	Восходящая сортировка слиянием
	20	С,Т	Бинарная быстрая сортировка
	21	У,Ф	Поразрядная сортировка MSD
	22	Х, Ц	Трехпутевая поразрядная быстрая сортировка
	23	Ч,Ш	Поразрядная сортировка LSD
	24	Щ,Э	Четно-нечетная сортировка слиянием (1-й метод Бэтчера)
	25	Ю,Я	Нечетно-четная сортировка слиянием (2-й метод Бэтчера)

34

Пример выполнения задания

Выдан вариант № 5, первая буква фамилии студента – З. Сравниваются алгоритмы сортировки прямыми обменами (пузырь-

ковый метод) и быстрой сортировки (метод Хоора).

Описание выбранных алгоритмов сортировки

Суть метода сортировки обменами («метода пузырька») состоит в последовательном просмотре массива от конца к началу или от начала к концу и сравнении каждой пары элементов между собой. При этом «неправильное» расположение элементов устраняется путем их перестановки (обмена значениями). Процесс просмотра и сравнения элементов повторяется до получения результата. При сортировке по неубыванию «легкие» элементы с меньшим значением как бы «всплывают» к началу массива подобно тому, как это делают пузырьки воздуха в стакане с водой – отсюда и происходит популярное название алгоритма. «Пузырьковая» сортировка имеет очень плохие временные характеристики – ее трудоемкость выражается величиной вида O(n2), где n – размер массива.

Метод «быстрой» сортировки, предложенный К. Хоором, основан на разделении массива на два непустых непересекающихся подмножества элементов. При этом в одной части массива должны оказаться все элементы, которые не превосходят по значению некоторый предварительно выбранный элемент массива, а в другой части – все элементы, не меньшие его. Аналогично следует поступить с каждой из полученных групп (при этом элемент для разделения можно выбирать просто из «середины» группы). Очевидно, что на определенном этапе массив окажется полностью отсортированным. В подавляющем большинстве реальных случаев использование «быстрой» сортировки дает лучшие результаты по времени, чем все прочие методы.

Реализация методов в среде Turbo-Pascal

program analize_methods; uses dos;

const amax=10000;

type ar=array [1..amax] of integer; ar3=array [1..3] of ar;

var a:ar3;b:^ar3;

time:array [1..2,1..3] of real; hour,min,sec,sec100:word; r,r1,r2:real;

ns,i,k:integer;

f:text;

35

{Стандартная процедура для обмена значениями} procedure obmen(var a,b:integer);

var r:integer; begin

r:=a;a:=b;b:=r

end;

{Метод сортировки обменами (алгоритм "пузырька")} procedure sort_obmen(var m:ar);

var i,j:integer; begin

for i:=2 to amax do

for j:=amax downto i do

if m[j-1] > m[j] then obmen(m[j-1],m[j]) end;

{Метод "быстрой" сортировки (алгоритм Хоора)} procedure hoor(var m:ar);

procedure sort(l,r:integer); var i,j,x:integer;

begin

i:=l;j:=r;x:=m[(l+r) div 2]; while i <= j do

begin

while m[i] < x do i:=i+1; while m[j] > x do j:=j-1; if i <= j then

begin obmen(m[i],m[j]);i:=i+1;j:=j-1; end;

end;

if l < j then sort(l,j); if i < r then sort(i,r);

end; begin

sort(1,amax);

end;

{Главная программа} begin

randomize;

assign(f,'pasc.txt');rewrite(f);

writeln(f,'Сравнение двух методов сортировки в Турбо-Паскале'); writeln(f); new(b);

{Заполнение идеальными данными} for i:=1 to amax do a[1,i]:=i;

{Заполнение случайными данными} for i:=1 to amax do a[2,i]:=random(amax);

36

{Заполнение худшими данными} for i:=1 to amax do a[3,i]:=amax+1-i;

{Начинаем сортировку}

for ns:=1 to 2 do begin {два алгоритма} if ns=1 then begin

writeln('Метод сортировки обменами'); writeln(f,'Метод сортировки обменами'); end

else begin

writeln('Метод быстрой сортировки'); writeln(f,'Метод быстрой сортировки'); end;

writeln;writeln(f);

{Передаем во второй массив} for k:=1 to 3 do b^[k]:=a[k];

{Сортировка}

for i:=1 to 3 do begin case i of

1:begin writeln('Идеальное расположение'); writeln(f,'Идеальное расположение') end;

2:begin writeln('Случайное расположение'); writeln(f,'Случайное расположение') end;

3:begin writeln('Обратное расположение'); writeln(f,'Обратное расположение') end;

end;

writeln('До сортировки:');writeln(f,'До сортировки:');

for k:=1 to 10 do begin write(b^[i,k],' ');write(f,b^[i,k],' ') end; writeln;writeln(f);

gettime(hour,min,sec,sec100);

r1:=sec100/100+sec+min*60+hour*3600;

if ns=1 then sort_obmen(b^[i]) else hoor(b^[i]); gettime(hour,min,sec,sec100); r2:=sec100/100+sec+min*60+hour*3600; time[ns,i]:=r2-r1;

writeln('После сортировки:');writeln(f,'После сортировки:'); for k:=1 to 10 do begin write(b^[i,k],' ');write(f,b^[i,k],' ') end; writeln;writeln(f);

writeln('Время: ',time[ns,i]:0:2);writeln; writeln(f,'Время: ',time[ns,i]:0:2);writeln(f); end;{i}

writeln;writeln(f);

end;{ns}

writeln('Подведение итогов (время в секундах)'); writeln(f,'Подведение итогов (время в секундах)'); writeln('|----------------------------------------------|');

37

writeln('| Алгоритм | Идеальный | Случайный | Наихудший |');

writeln('|----------------------------------------------	|');
writeln(f,'|----------------------------------------------	|');

writeln(f,'| Алгоритм | Идеальный | Случайный | Наихудший |'); writeln(f,'|----------------------------------------------|');

for ns:=1 to 2 do begin

if ns=1 then begin write('| Обмен ');write(f,'| Обмен ') end else begin write('| Хоор ');write(f,'| Хоор ') end;

for i:=1 to 3 do begin write('|',time[ns,i]:11:2);write(f,'|',time[ns,i]:11:2) end; writeln('|');writeln(f,'|')

end;
writeln('|----------------------------------------------	|');
writeln(f,'|----------------------------------------------	|');
close(f);
dispose(b)
end.

Сравнение двух методов сортировки в Турбо-Паскале

Метод сортировки обменами

Идеальное расположение До сортировки:

1 2 3 4 5 6 7 8 9 10

После сортировки:

1 2 3 4 5 6 7 8 9 10

Время: 2.81

Случайное расположение До сортировки:

298 6179 5360 8197 9804 1173 8346 6670 7217 141

После сортировки:

0 1 1 2 2 4 5 6 7 8

Время: 8.56

Обратное расположение До сортировки:

10000 9999 9998 9997 9996 9995 9994 9993 9992 9991

После сортировки:

1 2 3 4 5 6 7 8 9 10

Время: 13.63

Метод быстрой сортировки

Идеальное расположение До сортировки:

1 2 3 4 5 6 7 8 9 10

После сортировки:

1 2 3 4 5 6 7 8 9 10

Время: 0.00

38

Случайное расположение До сортировки:

298 6179 5360 8197 9804 1173 8346 6670 7217 141

После сортировки:
0 1 1	2 2	4	5 6 7	8
Время: 0.00
Обратное расположение
До сортировки:
10000	9999 9998 9997 9996				9995 9994 9993 9992 9991
После сортировки:
1 2 3	4 5	6	7 8 9	10
Время: 0.00
Подведение итогов (время в секундах)
|----------------------------------------------					|

| Алгоритм | Идеальный | Случайный | Наихудший |

|----------------------------------------------				|
| Обмен	|	2.81|	8.56|	13.63|
| Хоор	|	0.00|	0.00|	0.00|
|----------------------------------------------				|

Реализация методов в среде Turbo-С++

#include <dos.h> #include <math.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #define amax 10000

// Метод сортировки обменами (алгоритм "пузырька") void sort_obmen(int m[amax])

{

int r,i,j;

for (i=2;i<=amax;i++) { for (j=amax;j>=i;j--) { if (m[j-1-1] > m[j-1])

{ r=m[j-1-1];m[j-1-1]=m[j-1];m[j-1]=r; }

}}

}

// Метод "быстрой" сортировки (алгоритм Хоора) void hoor(int m[],int l,int r)

{

int i,j,x,o; i=l;j=r;x=m[int(floor((l+r)/2))]; while (i<=j)

{

while (m[i-1] < x) {i++;} while (m[j-1] > x) {j--;}

39

if (i <= j) { o=m[i-1];m[i-1]=m[j-1];m[j-1]=o; i++;j--;}

}

if (l < j) {hoor(m,l,j);} if (i < r) {hoor(m,i,r);}

}

// Главная программа void main(void)

{

int a[3][amax],ns,i,k; float time[2][3],r1,r2; struct time t;

FILE *f; srand(1);

f=fopen("res_cpp.txt","w");

fprintf(f,"Сравнение двух методов сортировки в Турбо-C++\n\n"); // начинаем сортировку

for (ns=1;ns<=2;ns++) // два алгоритма

{

if (ns==1) {printf("Метод сортировки обменами\n"); fprintf(f,"Метод сортировки обменами\n");} else {printf("Метод быстрой сортировки\n");

fprintf(f,"Метод быстрой сортировки\n");}

//заполнение идеальными данными for (i=1;i<=amax;i++) {a[0][i-1]=i;}

//заполнение случайными данными

for (i=1;i<=amax;i++) {a[1][i-1]=abs(rand()%amax);}

// заполнение худшими данными

for (i=1;i<=amax;i++) {a[2][i-1]=amax+1-i;}

// сортировка

for (i=1;i<=3;i++)

{

switch (i) {

case 1: printf("Идеальное расположение\n"); fprintf(f,"Идеальное расположение\n");break;

case 2: printf("Случайное расположение\n"); fprintf(f,"Случайное расположение\n");break;

case 3: printf("Обратное расположение\n"); fprintf(f,"Обратное расположение\n");break;}

printf("До сортировки\n");fprintf(f,"До сортировки\n"); for (k=0;k<10;k++) {printf("%6i",a[i-1][k]);fprintf(f,"%6i",a[i-1][k]);} printf("\n");fprintf(f,"\n");

gettime(&t);

40