МИНИСТЕРСТВО ЦИФРОВОГО РАЗВИТИЯ, СВЯЗИ И МАССОВЫХ КОММУНИКАЦИЙ РОССИЙСКОЙ ФЕДЕРАЦИИФедеральное государственное бюджетное образовательное учреждение высшего образования «Санкт-Петербургский государственный университет телекоммуникаций им. проф. М. А. Бонч-Бруевича»(СПбГУТ)Факультет Информационных систем и технологийКафедра Безопасности информационных системОтчетПо предмету «Алгоритмы и структуры данных»о практической работе №3:«Сортировка числовых массивов. Некоторые методы сортировки.»Выполнил студент гр. ИСТ-022:Волков Кирилл // //оценка     Проверил: Бородянский Ю.М. // //ПодписьЗадача работыПрименить на практике три метода сортировки массива. Проанализировать результаты работы программ по затраченного времени. Сделать выводы об эффективности.Ход работыРазработаем программу, которая создаёт файл со случайным массивом. Затем сортирует его по возрастанию и тоже записывает файл, аналогично с массивом по убыванию. Итогом является три файла. Затем массив из каждого файла сортируется каждым методом, засекается время. Результатом является вывод в консоль времени работы методов с разными массивами.Блок-схема алгоритма выбораБлок-схема алгоритма вставкиБлок-схема алгоритма пузырькаБлок-схема метода пузырька с оптимизацией Cложность Big-OМетод выбора: O(n^2).Метод вставки: O(n^2).Метод пузырька: O(n^2).Метод пузырька с оптимизацией: в лучше случае O(n) и O(n^2) в худшем.

---

Результат работы программыВыводВ ходе практической работы были применены знания о одномерных массивах, на практике проверены алгоритмы сортировки. Найдены их сложности в нотации Big-O. Анализ времени работы позволяет сделать следующие выводы: самым эффективным является оптимизированный метод пузырька, самым худшим же обычный метод пузырька. Средним по эффективности оказались метод вставки и выбора, причём алгоритм вставки немного выигрывает в эффективности.Код программы смотрите в приложении 1.Приложение 1#include

#include

#include

#include

using namespace std;

void creat_mass (){

ofstream mass_rand_f("mass_rand.txt");

ofstream mass_sort_f1("mass_sort_asc.txt");

ofstream mass_sort_f2("mass_sort_desc.txt");

int length = 10000;

int mass_rand[length], temp, id;

for (int i = 0; i < length; i++)

{

mass_rand[i] = 1 + rand() % 100;

mass_rand_f<
}

for (int i = 1; i < length; i++)

{

temp = mass_rand[i]; // текущее значение элемента массива

id = i - 1; // индекс предыдущего элемента массива

while (id >= 0 && mass_rand[id] > temp)

{

mass_rand[id + 1] = mass_rand[id]; // перестановка элементов массива

mass_rand[id] = temp;

id--;

}

}

for (int i = 0; i < length; i++)

mass_sort_f1<
for (int i = 1; i < length; i++)

{

temp = mass_rand[i]; // текущее значение элемента массива

id = i - 1; // индекс предыдущего элемента массива

while (id >= 0 && mass_rand[id] < temp)

{

mass_rand[id + 1] = mass_rand[id]; // перестановка элементов массива

mass_rand[id] = temp;

id--;

}

}

for (int i = 0; i < length; i++)

mass_sort_f2<
}

void selection_sort (){

ifstream mass_rand_f("mass_rand.txt");

ifstream mass_sort_f_asc("mass_sort_asc.txt");

ifstream mass_sort_f_desc("mass_sort_desc.txt");

int length = 10000;

int mass[length];

for (int i = 0; i < length; i++)

mass_rand_f>>mass[i];

int minim, cnt=0;

unsigned int start_time = clock();

for (int i=0; i
minim = i;

for (int j=i+1;j
if (mass[j]
minim = j;

}

swap(mass[i],mass[minim]);

cnt++;

}

unsigned int end_time = clock();

cout<<"\nКоличетсво элементов = 10000";

cout<<"\n\nМетод выбора\nНеотсортированным массив.\t\tВремя работы:\t"<
for (int i = 0; i < length; i++)

mass_sort_f_asc>>mass[i];

start_time = clock();

for (int i=0; i
minim = i;

for (int j=i+1;j
if (mass[j]
minim = j;

}

swap(mass[i],mass[minim]);

}

end_time = clock();

cout<<"\nОтсортированный по возрастанию массив.\tВремя работы:\t"<<(end_time-start_time)<<" млс";

for (int i = 0; i < length; i++)

mass_sort_f_desc>>mass[i];

start_time = clock();

for (int i=0; i
minim = i;

for (int j=i+1;j
if (mass[j]
minim = j;

}

swap(mass[i],mass[minim]);

}

end_time = clock();

cout<<"\nОтсортированный по убыванию массив.\tВремя работы:\t"<<(end_time-start_time)<<" млс";

}

void vstavka_sort (){

ifstream mass_rand_f("mass_rand.txt");

ifstream mass_sort_f_asc("mass_sort_asc.txt");

ifstream mass_sort_f_desc("mass_sort_desc.txt");

int length = 10000;

int mass[length], temp, j;

for (int i = 0; i < length; i ++)

mass_rand_f>>mass[i];

unsigned int start_time = clock();

for (int i = 1; i < length; i++)

{

temp = mass[i]; // текущее значение элемента массива

j = i - 1; // индекс предыдущего элемента массива

while (j >= 0 && mass[j] > temp)

{

mass[j+ 1] = mass[j]; // перестановка элементов массива

j--;

}

mass[j] = temp;

}

unsigned int end_time = clock();

cout<<"\n\nМетод вставки\nНеотсортированный массив.\t\tВремя работы:\t"<
for (int i = 0; i < length; i ++)

mass_sort_f_asc>>mass[i];

start_time = clock();

for (int i = 1; i < length; i++)

{

temp = mass[i]; // текущее значение элемента массива

j = i - 1; // индекс предыдущего элемента массива

while (j >= 0 && mass[j] > temp)

{

mass[j + 1] = mass[j]; // перестановка элементов массива

mass[j] = temp;

j--;

}

}

end_time = clock();

cout<<"\nОтсортированный по возрастанию массив.\tВремя работы:\t"<
for (int i = 0; i < length; i ++)

mass_sort_f_desc>>mass[i];

start_time = clock();

for (int i = 1; i < length; i++)

{

temp = mass[i]; // текущее значение элемента массива

j = i - 1; // индекс предыдущего элемента массива

while (j >= 0 && mass[j] > temp)

{

mass[j + 1] = mass[j]; // перестановка элементов массива

mass[j] = temp;

j--;

}

}

end_time = clock();

cout<<"\nОтсортированный по убыванию массив.\tВремя работы:\t"<
}

void bubble_sort (){

ifstream mass_rand_f("mass_rand.txt");

ifstream mass_sort_f_asc("mass_sort_asc.txt");

ifstream mass_sort_f_desc("mass_sort_desc.txt");

int length = 10000;

int mass[length], temp;

for (int i = 0; i < length; i ++)

mass_rand_f>>mass[i];

unsigned int start_time = clock();

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

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

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

// меняем элементы местами

temp = mass[j];

mass[j] = mass[j + 1];

mass[j + 1] = temp;

}

}

}

unsigned int end_time = clock();

cout<<"\n\nМетод пузырька\nНеотсортированный массив.\t\tВремя работы:\t"<
for (int i = 0; i < length; i ++)

mass_sort_f_asc>>mass[i];

start_time = clock();

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

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

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

// меняем элементы местами

temp = mass[j];

mass[j] = mass[j + 1];

mass[j + 1] = temp;

}

}

}

end_time = clock();

cout<<"\nОтсортированный по возрастанию массив.\tВремя работы:\t"<
for (int i = 0; i < length; i ++)

mass_sort_f_desc>>mass[i];

start_time = clock();

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

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

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

// меняем элементы местами

temp = mass[j];

mass[j] = mass[j + 1];

mass[j + 1] = temp;

}

}

}

end_time = clock();

cout<<"\nОтсортированный по убыванию массив.\tВремя работы:\t"<
}

void bubble_sort_opt (){

ifstream mass_rand_f("mass_rand.txt");

ifstream mass_sort_f_asc("mass_sort_asc.txt");

ifstream mass_sort_f_desc("mass_sort_desc.txt");

int length = 10000;

int mass[length], temp;

bool flag;

for (int i = 0; i < length; i ++)

mass_rand_f>>mass[i];

unsigned int start_time = clock();

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

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

flag = false;

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

// меняем элементы местами

temp = mass[j];

mass[j] = mass[j + 1];

mass[j + 1] = temp;

flag = true;

}

}

if (!flag)

break;

}

unsigned int end_time = clock();

cout<<"\n\nМетод пузырька(Оптимизированный)\nНеотсортированный массив.\t\tВремя работы:\t"<
for (int i = 0; i < length; i ++)

mass_sort_f_asc>>mass[i];

start_time = clock();

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

flag = false;

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

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

// меняем элементы местами

temp = mass[j];

mass[j] = mass[j + 1];

mass[j + 1] = temp;

flag = true;

}

}

if (!flag)

break;

}

end_time = clock();

cout<<"\nОтсортированный по возрастанию массив.\tВремя работы:\t"<
for (int i = 0; i < length; i ++)

mass_sort_f_desc>>mass[i];

start_time = clock();

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

flag = false;

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

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

// меняем элементы местами

temp = mass[j];

mass[j] = mass[j + 1];

mass[j + 1] = temp;

flag = true;

}

}

if (!flag)

break;

}

end_time = clock();

cout<<"\nОтсортированный по убыванию массив.\tВремя работы:\t"<
}

int main()

{

SetConsoleCP(1251);

SetConsoleOutputCP(1251);

creat_mass();

selection_sort();

vstavka_sort ();

bubble_sort();

bubble_sort_opt ();

}

г. Санкт-Петербург

2021

---

Смотрите также файлы

• Что такое толерантность.docx

• Профилактика туберкулеза у детей.doc

• Как мультфильмы влияют на психику ребенка.docx

• Лабораторная работа 1 Тема. Основы работы с электронной таблицей Excel. Цель.doc

• Волейбол (правила игры и история развития).docx