Можно выбрать одну из тем курсовых работ с номером от 1 до 19

size (); ++i) {std:cout << v[i] << ' '; }std:cout << std: endl;}Теперь мы можем вывести оригинал массива и его отсортированные версии, чтобы убедиться, что сортировка прошла успешно. print_vector («unsorted», unsorted);print_vector («bubble», bubble->getVector ());print_vector («quick», quick->getVector ());Результат вывода на экран представлен на Рис. 6: Рис. 6 — Вывод консоли после запуска теста на корректность алгоритмов сортировок.

Для того чтобы замерить производительность каждого из алгоритмов сортировки, нужно многократно запустить функцию сортировки обоих объектов-сортировщиков на большой тестовой выборке, поскольку адекватные замеры времени исполнения можно получить только под большой нагрузкой. Для примера, тестовый вектор из предыдущего теста на корректность сортировался менее одной миллисекунды для каждого из алгоритмов сортировки. Такие малые замеры не позволят объективно судить о реальном времени исполнения функций сортировок и подвержены большой погрешности. Поэтому тест будет генерировать массив из 100 случайных чисел и сортировать его обоими алгоритмами и повторит данную процедуру генерации-сортировки 500 раз, чтобы получить репрезентативные замеры, о которых можно будет судить о производительности алгоритмов. Тест будет использовать следующую функцию генерации вектора случайных чисел: std:vector<int> generate_vector () {constint N = 100;std:vector<int> v (N);for (int i = 0; i<N; ++i) {v[i] = rand (); }return v;}Для измерения времени исполнения функций сортировки будет использоваться переменная tтипа clock_t, которой в нужные моменты времени будет присваиваться результат вызова функции clock () стандартной библиотеки C. Тогда сам тест будет выглядеть следующим образом: Sorter *bubble = new BubbleSorter ();Sorter *quick = new QuickSorter ();constint N = 500;longbubble_time = 0;longquick_time = 0;clock_t t;for (int i = 0; i<N; ++i) {std:vector<int> v = generate_vector ();bubble->setVector (v);quick->setVector (v);t = clock ();bubble->sort ();bubble_time += clock () — t;t = clock ();quick->sort ();quick_time += clock () — t;}std:cout << «bubble_time: «<< bubble_time << std: endl;std:cout << «quick_time: «<< quick_time << std: endl;Результат выполнения теста представлен на Рис 7: Рис. 7 — Вывод консоли после запуска теста на производительность алгоритмов сортировок (результаты представлены в миллисекундах) Таким образом, на практике алгоритм быстрой сортировки оказался быстрее алгоритма сортировки методом пузырька примерно в 20 раз на тестовой выборке из тысячи массивов тысячи случайных чисел.

Заключение

.

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

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

Таблица 1 — Количество непустых строк реализации алгоритмов сортировки.

ПсевдокодКод С++Сортировка пузырьком4−812Быстрая обменная сортировка1622.

Метод быстрой обменной сортировки более производителен в терминах времени исполнения, чем метод пузырька. По итогам тестовых замеров: примерно в 20 раз быстрее. Вычислительная сложность алгоритмов и тестовое время исполнения представлены в Таблице 2: Таблица 2 — Характеристики вычислительной сложности алгоритмов сортировки.

Вычислительная сложность.

Тестовое время исполнения.

Сортировка пузырькомO (n2)1946мс.

Быстрая обменная сортировкаO (nlogn) — O (n2)95мс.

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

Таблица 3 — Характеристики пространственной сложности алгоритмов сортировки.

Пространственная сложность.

Сортировка пузырькомO (1)Быстрая обменная сортировкаO (nlogn)Список использованных источников.

Электронные источники.

Википедия [Электронный ресурс] Сортировка. ;

https://ru.wikipedia.org/wiki/Сортировка проверено 16.

03.2018.

Википедия [Электронный ресурс]. Алгоритм сортировки ;

https://ru.wikipedia.org/wiki/Алгоритм_сортировки проверено 16.

03.2018.

Википедия [Электронный ресурс]. Сортировка пузырьком ;

https://ru.wikipedia.org/wiki/Сортировка_пузырьком проверено 16.

03.2018.

Википедия [Электронный ресурс]. Быстрая сортировка ;

https://ru.wikipedia.org/wiki/Быстрая_сортировка проверено 16.

03.2018.

Приложение А. Код объектной модели программыclassSorter{public:virtual void setVector (std:vector<int> unsorted) { v = unsorted; }virtualstd:vector<int> getVector () const {return v; }virtual void sort () = 0;protected:std:vector<int> v;};classBubbleSorter: public Sorter{public:virtual void sort () override {for (int i = 0; i<v.size ()-1; ++i) {int f = 0;for (int j = 0; j<v.size ()-i-1; ++j) {if (v[j] > v[j+1]) {std:swap (v[j], v[j+1]); f = 1; } }if (!f) {break; } } }};classQuickSorter: public Sorter{public:virtual void sort () override {if (v.empty ()) {return; } _quick_sort (v, 0, v. size ()-1); }private:void _quick_sort (std:vector<int> &v, int first, int last) {int mid = v[(first+last)/2]; int b = first;int e = last;while (b <= e) {while (v[b] < mid) { ++b; }while (v[e] > mid) { —e; }if (b <= e) {std:swap (v[b], v[e]); ++b; —e; } }if (e > first) { _quick_sort (v, first, e); }if (b < last) { _quick_sort (v, b, last);} }};Приложение.

Б. Кодтестовалгоритмовсортировкиvoidprint_vector (std:string label, conststd: vector<int> &v) {std:cout << label << «: «;for (int i = 0; i<v.size (); ++i) {std:cout << v[i] << ' '; }std:cout << std: endl;}voidtest_correctness () {std:cout << «Test correctness» << std: endl;std:vector<int> unsorted = { 18, 4, 8, 0, 1, 10, 2, 5, 5 }; Sorter *bubble = new BubbleSorter ();bubble->setVector (unsorted);bubble->sort (); Sorter *quick = new QuickSorter ();quick->setVector (unsorted);quick->sort ();print_vector («unsorted», unsorted);print_vector («bubble», bubble->getVector ());print_vector («quick», quick->getVector ());delete bubble;delete quick;std:cout << std: endl;}std:vector<int> generate_vector () {constint N = 1000;std:vector<int> v (N);for (int i = 0; i<N; ++i) {v[i] = rand (); }return v;}voidtest_performance () {std:cout << «Test performance…» << std: endl; Sorter *bubble = new BubbleSorter (); Sorter *quick = new QuickSorter ();constint N = 1000;longbubble_time = 0;longquick_time = 0;clock_t t;for (int i = 0; i<N; ++i) {std:vector<int> v = generate_vector ();bubble->setVector (v);quick->setVector (v); t = clock ();bubble->sort ();bubble_time += clock () — t; t = clock ();quick->sort ();quick_time += clock () — t; }std:cout << «bubble_time: «<< bubble_time << std: endl;std:cout << «quick_time: «<< quick_time << std: endl;delete bubble;delete quick;}int main (){test_correctness ();test_performance ();return 0;}.