Мегаобучалка Главная | О нас | Обратная связь


Тестирование разработанных функций сортировки методом простых вставок и методом пузырька



2019-12-29 315 Обсуждений (0)
Тестирование разработанных функций сортировки методом простых вставок и методом пузырька 0.00 из 5.00 0 оценок




 

В ходе работы над курсовым проектом было разработано 2 функции: функция сортировки массива методом простых вставок, и функция сортировки массива методом пузырька. Так же в разработанной программе использована функция подсчета времени работы программы clock (), содержащаяся в библиотеке time. h. Массив формируется автоматически с помощью встроенной функции randomize (), пользователю нужно лишь задать число элементов в массиве и выбрать метод сортировки. После чего будет выполнена сортировка выбранным методом, выведен на экран упорядоченный массив и время сортировки в миллисекундах.

Для тестирования работы программы совершим несколько прогонов с разными значениями. В качестве отчета о работе программы приведены скриншоты:

 

Рисунок 12. Скриншот работающей программы, сортировка методом простых вставок

 

Рисунок 13. Скриншот работающей программы, сортировка методом пузырька

 

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


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

 

Для экспериментального сравнения эффективности работы методов сортировок нужно определить время сортировки − в данном случае оно является главным показателем эффективности. В таблице 3 указано время сортировки соответствующее определенному количеству элементов массива, определенное экспериментально для каждого метода сортировки.

 

Таблица 3. Время сортировки

Количество элементов массива Время сортировки для метода простых вставок, мс Время сортировки для метода пузырька, мс
5 237 245
10 248 267
15 253 272
20 259 294
30 277 311
40 279 320
64 346 368
128 659 702
256 876 912
512 910 975
1024 953 1034

 

На основе данной таблицы построены графики для экспериментального анализа эффективности методов сортировки.


Рисунок 14. Графики зависимости времени сортировки от количества элементов массива

 

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


Заключение

 

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

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

Были разработаны функции сортировки методом простых вставок (insert) и методом пузырька (bubble). Данные функции интегрированы в разработанное приложение, с помощью которого можно создать массив с заданным количеством элементов, отсортировать его любым из рассмотренных в курсовом проекте методом сортировки и узнать время сортировки массива.

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


Список литературы

 

1. Лекции по предмету "Программирование языков высшего уровня"

2. "Программирование и основы алгоритмизации" - В.Г. Давыдов - изд. "Высшая школа", 2005.

3. "Основы алгоритмизации и программирования" - О.Л. Голицына, И.И. Попов - изд. "ФОРУМ-ИНФРА-М", 2006.

4. "Программирование на языке высокого уровня" - Т.А. Павловская - изд. "Питер", 2004.


Приложение

 

(листинг рабочего кода разработанного приложения)

#pragma argsused

#include <iostream. h>

# include <time. h>

void insert (int *a, int n) // ФУНКЦИЯ ВСТАВОК

{

int i, j, t; // объявление переменных

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

{

t=a [i] ; // запоминается элемент для вставки

for (j=i-1; j>=0 && t<a [j] ; j--) // ищем место для вставки

a [j+1] =a [j] ; // сдвиг на одну позицию

a [j+1] =t;

}

}

void buble (int *a, int n) // функция пузырька

{

int i,j,t; // объявление переменных

for (i = 0; i <= n-1; i++)

{

for (j = 0; j <= n-2-i; j++)

{

if (a [j] >a [j+1]) // сравниваем пару соседних элементов

{

t = a [j] ; // и меняем их местами если это требуется

a [j] = a [j+1] ;

a [j+1] = t;

}

}

}

}

int main (int argc, char* argv [])

{

char b;

int n;

typedef long clock_t; // тип данных времени

clock_t t; // t - время выполнения программы

char str1 [100] = "Введите количество элементов для сортировки: ";

char str2 [100] ;

char str3 [100] ;

CharToOem (str1, buf);

cout<<buf<<endl;

cin>>n;

int* a=new int; // создание, указание кол-ва элементов

randomize (); // и заполнение массива

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

a [i] =random (50) - 30;

strcpy (str1,"Первичный массив: ");

CharToOem (str1, buf);

cout<<buf<<endl;

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

{

cout<<" a ["<<i<<"] ="<<a [i] <<' ';

if (! ( (i+1)%5)) cout << "\n"; // массив выводится по 5 значений в строке

};

cout<<endl;

strcpy (str1,"Выберите тип сортировки: ");

strcpy (str2,"1. Сортировка методом простых вставок");

strcpy (str3,"2. Сортировка методом пузырька ");

CharToOem (str1, buf);

CharToOem (str2, buf1);

CharToOem (str3, buf2);

cout<<buf<<endl

<<buf1<<endl

<<buf2<<endl;

cin>>b;

strcpy (str1,"Отсортированные элементы: ");

CharToOem (str1, buf);

cout<<buf<<endl;

if (b='1')

{

insert (a,n); // вызов функции сортировки

}

if (b='2')

{

buble (a,n); // вызов функции

}

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

{

cout<<" a ["<<i<<"] ="<<a [i] <<' ';

if (! ( (i+1)%5)) cout << "\n";

}

cout<<endl; // подсчёт времени выполнения программы

strcpy (str1,"Время сортировки в мс: ");

CharToOem (str1, buf);

cout<<buf<<endl;

t= (clock () /CLOCKS_PER_SEC) * 60; // функция clock () возвращает время исп программы

cout<<t; // как значение типа clock_t объявленного ранее это // значение можно перевести в секунды

 // поделив на определенную в библиотеке time. h константу CLOCKS_PER_SEC

getchar ();

getchar ();

return 0; }



2019-12-29 315 Обсуждений (0)
Тестирование разработанных функций сортировки методом простых вставок и методом пузырька 0.00 из 5.00 0 оценок









Обсуждение в статье: Тестирование разработанных функций сортировки методом простых вставок и методом пузырька

Обсуждений еще не было, будьте первым... ↓↓↓

Отправить сообщение

Популярное:
Модели организации как закрытой, открытой, частично открытой системы: Закрытая система имеет жесткие фиксированные границы, ее действия относительно независимы...
Как выбрать специалиста по управлению гостиницей: Понятно, что управление гостиницей невозможно без специальных знаний. Соответственно, важна квалификация...
Организация как механизм и форма жизни коллектива: Организация не сможет достичь поставленных целей без соответствующей внутренней...
Как вы ведете себя при стрессе?: Вы можете самостоятельно управлять стрессом! Каждый из нас имеет право и возможность уменьшить его воздействие на нас...



©2015-2020 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (315)

Почему 1285321 студент выбрали МегаОбучалку...

Система поиска информации

Мобильная версия сайта

Удобная навигация

Нет шокирующей рекламы



(0.009 сек.)