Файл: Отчет по выполнению практического задания 2.docx

МИНОБРНАУКИ РОССИИ

Федеральное государственное бюджетное образовательное учреждение высшего образования «МИРЭА – Российский технологический университет» РТУ МИРЭА

Отчет по выполнению практического задания 2

Тема. Эмпирический анализ аdaлгоритмов сортировки

Дисциплина Структуры и алгоритмы обработки данных

Выполнил

студент
	Фамилия И.О.
группа
	Номер группы

Москва 2021

1Задания

Задание 1.

1)Составить программу сортировки одномерного целочисленного массива A[n], используя алгоритм прямого выбора. Провести тестирование программы на исходном массиве, сформированном вводом с клавиатуры. Рабочий массив A сформировать с использованием генератора псевдослучайных чисел. Провести контрольные прогоны программы для размеров массива n = 100, 1000, 10000, 100000 и 1000000 элементов с вычислением времени выполнения T(n). Полученные результаты свести в сводную таблицу. Построить график зависимости времени выполнения программы от размера массива.

Примечание. Массив может быть статическим или динамическим по вашему усмотрению.

2)Провести эмпирическую (практическую) оценку вычислительной сложности алгоритма, для чего предусмотреть в программе подсчет фактического количества операций сравнения Сф и количества операций перемещения Мф. Полученные результаты свести в сводную таблицу.

Таблица 1 Сводная таблица результатов

n	T	f(C+M)	Cф+Mф
100
1000
10000
100000
1000000

---

3)Построить в одной координатной плоскости графики зависимости теоретической О(n)=f(С+М) и эмпирической (Сф+Мф) вычислительной сложности алгоритма от размера массива n.

4)Провести анализ полученных результатов. Сделать выводы о проделанной работе, основанные на полученных результатах.

Задание 2

1) Провести дополнительные прогоны программы на рабочих массивах, отсортированных строго в убывающем и возрастающем порядке значений элементов. Провести анализ зависимости (или независимости) алгоритма сортировки от исходной упорядоченности массива.

2) Провести программную реализацию алгоритмов «Простой вставки», «Простого обмена» с последующим сравнительным анализом полученных результатов контрольных прогонов и построением соответствующих графиков.

Отчет по заданию 1

1. 
   Была составлена программа сортировки одномерного целочисленного массива, с использованием алгоритма прямого выбора. Ниже представлен код функции, реализующей данный алгоритм:
   

void LinearSelection(int* arr, int size) {

long long int Cf = 0;

long long int Mf = 0;
unsigned int start = clock();

for (int i = 0; i < size - 1; i++) {

int min = i;

for (int j = i + 1; j < size; j++) {

Cf++;

if (arr[j] < arr[min]) {

min = j;

}

}

if (min != i) {

Mf++;

std::swap(arr[i], arr[min]);

}

}

unsigned int end = clock();
std::cout << "Cf = " << Cf;

std::cout << "; Mf = " << Mf;

std::cout << "; Time = " << (end - start) / (CLOCKS_PER_SEC) << '\n';

}

2. 
   Была проведена эмпирическая оценка вычисленной сложности алгоритма. Было подсчитано фактическое количество операций сравнения Сф и фактическое количество операций перемещения Мф. Результаты были занесены в таблицу 1.
   

Таблица 1 Сводная таблица результатов

n	T	f(C+M)	Cф+Mф
100	0		4950+ 94
1000	0		499500+995
10000	0		49995000+9993
100000	11		4999950000+99981
1000000	1181		499999500000+999952

---

3. 
   На одной координатной плоскости были построены графики зависимости теоретической и эмпирической вычисленной сложности алгоритма от размера массива.
   

4. 
   Вывод
   

По результатам выполненной работы видно, что сложность данного алгоритма очень быстро растет при увеличении размера массива. Также можно заметить, что фактическая сложность алгоритма заметно меньше, чем теоретическая, однако, она все равно является очень большой при больших размерах массива.

Отчет по заданию 2

1. 
   Были проведены дополнительные прогоны программы на отсортированных массивах. Результаты представлены в таблицах 2 и 3.
   

Таблица 2 Результаты для отсортированного по возрастанию массива

n	T	f(C+M)	Cф+Mф
100	0		4950+ 50
1000	0		499500+ 500
10000	0		49995000+ 5000
100000	11		4999950000+50000
1000000	1109		499999500000+500000

Таблица 3 Результаты для отсортированного по убыванию массива

---

n	T	f(C+M)	Cф+Mф
100	0		4950+ 0
1000	0		499500+ 0
10000	0		49995000+ 0
100000	11		4999950000+0
1000000	1078		499999500000+0

Исходя из полученных результатов видно, что для отсортированных массивов заметно уменьшается количество перемещений. Причем, для отсортированного по возрастанию массива количество перемещений уменьшается почти в 2 раза, а для отсортированных по убыванию вообще рано 0. При больших размерах массива это является весомым уменьшением количества операций, но оно не сильно уменьшает время работы программы.

2. 
   Были реализованы алгоритмы «Простой вставки» и «Простого обмена». Ниже представлен код функций, которые реализуют данные алгоритмы.
   

Простая вставка:

bool InsertionsComp(int j, int num, int arr_elem, long long int *Cf) {

*Cf += 1;

if ((j >= 0) && (arr_elem > num)) {

return true;

}

return false;

}
void Insertions(int* arr, int size) {

long long int Cf = 0;

long long int Mf = 0;
unsigned int start = clock();

for (int i = 1; i < size; i++) {

int j = i - 1;

int num = arr[i];

while (InsertionsComp(j, num, arr[j], &Cf)) {

std::swap(arr[j], arr[j + 1]);

Mf++;

j--;

}

arr[j + 1] = num;

Mf++;

}

unsigned int end = clock();
std::cout << "Cf = " << Cf;

std::cout << "; Mf = " << Mf;

std::cout << "; Time = " << (end - start) / CLOCKS_PER_SEC << '\n';

}

Простой обмен:

void Trade(int* arr, int size) {

long long int Cf = 0;

---

long long int Mf = 0;
unsigned int start = clock();

for (int i = size - 1; i > 0; i--) {

for (int j = 0; j < i; j++) {

Cf++;

if (arr[j] > arr[j + 1]) {

Mf++;

std::swap(arr[j], arr[j + 1]);

}

}

}

unsigned int end = clock();
std::cout << "Cf = " << Cf;

std::cout << "; Mf = " << Mf;

std::cout << "; Time = " << (end - start) / CLOCKS_PER_SEC << '\n';

}
Для алгоритма простой вставки:

Таблица 4 Сводная таблица результатов

n	T	f(C+M)	Cф+Mф
100	0		2708+ 2708
1000	0		254383+254383
10000	1		25351217+25351217
100000	194		2506144510+2506144510

Для алгоритма простого обмена:
Таблица 5 Сводная таблица результатов

n	T	f(C+M)	Cф+Mф
100	0		4950+ 2609
1000	0		499500+253384
10000	2		49995000+25341218
100000	238		4999950000+2506044511

---