Факультет информационных технологий и робототехники
Кафедра программного обеспечения вычислительной техники
и автоматизированных систем
Отчет по лабораторной работе № 7
по дисциплине: ”Основы алгоритмизации и программирования”
на тему: ”Алгоритмы поиска и сортировки”
Вариант 1
Выполнил: студент группы 10702214 Церковный Д.О.
Приняла: ст.пр. И. М. Борисова
Минск 2015
Лабораторная работа № 007. Алгоритмы поиска и сортировок
Задание 1.
Считайте все записи из файла "7.dat". Для чтения каждой отдельной записи осуществите динамический захват памяти. Предполагается, что к-во записей в файле заранее неизвестно.
Выполните сортировку записей по различным ключам. Для каждого ключа используйте различные алгоритмы сортировки:
· сортировка выбором,
· сортировка вставками,
· сортировка Шелла,
· быстрая сортировка.
Всего сортировка будет выполнена 12 раз, каждый раз сортируется массив в первоначальном состоянии. Для каждого случая подсчитайте к-во сравнений и перестановок. Оцените скорость, естественность и устойчивость каждого алгоритма. Оптимальную организацию функций продумайте самостоятельно.
Код программы
#include <stdio.h>
#include <locale>
#include <fstream>
#include <conio.h>
#include <iostream>
#include <string.h>
#include <windows.h>
using namespace std;
int v=0;
int swaps;
int comps;
struct person
{
char fam[20];
char name[20];
int nomer;
int date;
int oklad;
}*pr[20]={NULL};
void scan()
{
fstream fin("7.dat");
int sum=0;
for(int i = 0;!fin.eof(); i++)
{
pr[i] = new person;
fin >> pr[i]->fam;
fin >> pr[i]->name;
fin >> pr[i]->nomer;
fin >> pr[i]->date;
fin >> pr[i]->oklad;
}
fin.close();
}
void print()
{
for (int k=1; k<9; k++)
{
cout<<"\nФамилия: "<< pr[k]->fam;
cout<<"\nИмя: "<<pr[k]->name;
cout<<"\nНомер телефона: "<<pr[k]->nomer;
cout<<"\nДата: "<<pr[k]->date;
cout<<"\nОклад: "<<pr[k]->oklad;
cout<<"\n\n";
}
}
int vibor()
{
cout << " Выберите поле для сортировки:" << endl;
cout << " 1. Сотовый номер (по возрастанию);" << endl;
cout << " 2. По дате рождения (по убыванию);" << endl;
cout << " 3. По окладу (по убыванию);" << endl;
cin >> v;
return v;
}
void selectSort(person *arr[], int size)
{
person *tmp; int p;
p=vibor();
for(int i = 0; i < size; ++i) // i - номер текущего шага
{
int pos = i;
tmp = arr[i];
for(int j = i + 1; j < size; ++j) // цикл выбора наименьшего элемента
{
switch(p)
{
case 1:{
if (arr[j]->nomer < tmp->nomer)
{
pos = j;
tmp = arr[j];
}
}break;
case 2:
{
if (arr[j]->date > tmp->date)
{
pos = j;
tmp = arr[j];
}
}break;
case 3:
{
if (arr[j]->oklad > tmp->oklad)
{
pos = j;
tmp = arr[j];
}
}break;
default: cout << "Данного варианта не существует, попробуйте еще раз" << endl;break;
}
comps++;
}
arr[pos] = arr[i];
arr[i] = tmp; // меняем местами наименьший с a[i]
swaps++;
}
}
void insertSort(person *a[], int size)
{
person *tmp;
int p;
p=vibor();
for (int i = 1, j; i < size; ++i) // цикл проходов, i - номер прохода
{
tmp = a[i];
switch(p)
{
case 1:
{ for (j = i - 1; j >= 0 && a[j]->nomer > tmp->nomer; --j) // поиск места элемента в готовой последовательности
a[j + 1] = a[j], swaps++,comps++; // сдвигаем элемент направо, пока не дошли
a[j + 1] = tmp; // место найдено, вставить элемент
}break;
case 2:
{ for (j = i - 1; j >= 0 && a[j]->date < tmp->date; --j) // поиск места элемента в готовой последовательности
a[j + 1] = a[j], swaps++,comps++; // сдвигаем элемент направо, пока не дошли
a[j + 1] = tmp; // место найдено, вставить элемент
}break;
case 3:
{ for (j = i - 1; j >= 0 && a[j]->oklad < tmp->oklad; --j) // поиск места элемента в готовой последовательности
a[j + 1] = a[j], swaps++,comps++; // сдвигаем элемент направо, пока не дошли
a[j + 1] = tmp; // место найдено, вставить элемент
}break;
default: cout << "Данного варианта не существует, попробуйте еще раз" << endl;break;
}
}
}
int increment(long inc[], long size)
{
int p1, p2, p3, s;
p1 = p2 = p3 = 1;
s = -1;
do
{
if (++s % 2)
{
inc[s] = 8*p1 - 6*p2 + 1;
}
else
{
inc[s] = 9*p1 - 9*p3 + 1;
p2 *= 2;
p3 *= 2;
}
p1 *= 2;
}
while(3*inc[s] < size);
return s > 0? --s: 0;
}
void shellSort(person *a[], long size)
{
long inc, i, j, seq[40];
int p;
p=vibor();
int s;
s = increment(seq, 10); // вычисление последовательности приращений
while (s >= 0) // сортировка вставками с инкрементами inc[]
{
inc = seq[s--];
for (i = inc; i < size; ++i)
{
person *temp = a[i];
switch(p)
{
case 1:
{ for (j = i-inc; (j >= 0) && (a[j]->nomer > temp->nomer); j -= inc) {
a[j + inc] = a[j]; swaps++; comps++;
}
a[j+inc] = temp;
}break;
case 2:
{ for (j = i-inc; (j >= 0) && (a[j]->date < temp->date); j -= inc){
a[j + inc] = a[j]; swaps++; comps++;
}
a[j+inc] = temp;
}break;
case 3:
{ for (j = i-inc; (j >= 0) && (a[j]->oklad < temp->oklad); j -= inc){
a[j + inc] = a[j]; swaps++; comps++;
}
a[j+inc] = temp;
}break;
default: cout << "Данного варианта не существует, попробуйте еще раз" << endl;break;
}
}
}
}
void quickSortR(person *a[],int v, long size)
{// На входе - массив a[], a[N] - его последний элемент.
long i = 0, j = size; // поставить указатели на исходные места
person *temp, *p;
p = a[ size>>1 ]; // центральный элемент
// процедура разделения
do {
switch(v)
{
case 1:
{
while (a[i]->nomer < p->nomer) { i++; comps++; }
while (a[j]->nomer > p->nomer) {j--; comps++; }
if (i <= j)
{
temp = a[i]; a[i] = a[j]; a[j] = temp;
i++; j--;
swaps++;
}
}break;
case 2:
{
while (a[i]->date > p->date) { i++; comps++; }
while (a[j]->date < p->date) {j--; comps++; }
if (i <= j)
{
temp = a[i]; a[i] = a[j]; a[j] = temp;
i++; j--;
swaps++;
}
}break;
case 3:
{
while (a[i]->oklad > p->oklad) { i++; comps++; }
while (a[j]->oklad < p->oklad) {j--; comps++; }
if (i <= j)
{
temp = a[i]; a[i] = a[j]; a[j] = temp;
i++; j--;
swaps++;
}
}break;
default: cout << "Данного варианта не существует, попробуйте еще раз" << endl;break;
}
}while (i<=j);
// рекурсивные вызовы, если есть, что сортировать
if (j > 0) quickSortR(a, v, j);
if (size > i) quickSortR(a+i, v, size-i);
}
int main()
{
int a;
setlocale(LC_CTYPE, "Russian");
scan();
while(true)
{
cout << "*******Выберите тип сортировк****** " << endl;
cout << " 1. Сортировка выбором" << endl;
cout << " 2. Сортировка вставками" << endl;
cout << " 3. Сортировка Шелла" << endl;
cout << " 4. Быстрая cортировка" << endl;
cin >> a;
switch(a)
{
case 1:
{
swaps = comps = 0;
double start = GetTickCount();
selectSort(pr, 10);
double finish = GetTickCount();
float s=0;
s=(finish-start)/1000;
cout << "\n\nВремя сортировки: " << finish - start <<" Миллисикунд."<<"<"<<s<<">"<< endl;
break;
}
case 2:
{
swaps = comps = 0;
double start = GetTickCount();
insertSort(pr, 10);
double finish = GetTickCount();
float s=0;
s=(finish-start)/1000;
cout << "\n\nВремя сортировки: " << finish - start <<" Миллисикунд."<<"<"<<s<<">"<< endl;
break;
}
case 3:
{
swaps = comps = 0;
double start = GetTickCount();
shellSort(pr, 10);
double finish = GetTickCount();
float s=0;
s=(finish-start)/1000;
cout << "\n\nВремя сортировки: " << finish - start <<" Миллисикунд."<<"<"<<s<<">"<< endl;
break;
}
case 4:
{
swaps = comps = 0;
v=vibor();
double start = GetTickCount();
swaps = comps = 0;
quickSortR(pr,v,9);
double finish = GetTickCount();
float s=0;
s=(finish-start)/1000;
cout << "\n\nВремя сортировки: " << finish - start <<" Миллисикунд."<<"<"<<s<<">"<< endl;
break;
}
default: cout << "Данного варианта не существует, попробуйте еще раз" << endl;break;
}
print();
cout << endl;
cout << "Перестановок, сравнений:" << swaps << "; " << comps << endl;
}
return 0;
}
Скриншоты результатов
Задание 2.
Напишите функцию search_record для поиска записи в массиве из предыдущего задания по определенному ключу. Ключом может являться любое поле структуры (название начального пункта маршрута; название конечного пункта маршрута; номер маршрута; длина маршрута).
Причем функция должна выполнять последовательный поиск, если массив не сортирован, и бинарный поиск, если массив сортирован.