Материал: GrozI_Course_Work
20
Для кожного алгоритму , для кожної розмірності даних було проведено по 10 сортувань і взято середній час. Час замірявся за допомогою функції
high_resolution_clock з бібліотеки chrono.
Для запуску програмної реалізації тестування необхідно зробити наступне: 1. Після відкриття проекту , відкрити файл main.cpp
(main.cpp виглядає наступним чином)
2.Ввести ім’я алгоритму сортування ,яке буде відображатися при виконанні програми в змінній name.
2.Ввести ім’я функції , яка викликає потрібний алгоритм сортування варгуменах функції tester. (ім’я всіх функції можна подивитись в файлі – sort_algorithms.h)
2.Скомпілювати та запустити програму.
3.Очікуваний результат виконання програми
21
(Очікуваний результат виконання програми)
22
Тестування
Після тестування всіх алгоритмів було виявлено декілька залежностей деяких тестових даних та алгоритмів повя’язаних з принципами роботи цих алгоритмів. Спершу розглянемо графіки всіх тестів:
1.1. Довільні дані ,I-група
|
|
|
Random data |
(I-group) |
|
|
0.35 |
|
|
|
|
|
0.3 |
|
|
|
|
|
0.25 |
|
|
|
|
(seconds) |
0.2 |
|
|
|
|
0.15 |
|
|
|
|
|
Time |
0.1 |
|
|
|
|
|
|
|
|
|
|
|
0.05 |
|
|
|
|
|
0 |
|
|
|
|
|
10 |
100 |
1000 |
10000 |
100000 |
N-elements (array size)
Selection sort Insertion sort Shaker sort Counting sort
Time (seconds)
|
|
|
|
Random data |
(I-group) |
|
|
|
||||
0.35000000 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0.30000000 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0.25000000 |
|
|
|
|
|
|
|
|
|
|
|
Selection sort |
|
|
|
|
|
|
|
|
|
|
|
||
0.20000000 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Insertion sort |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0.15000000 |
|
|
|
|
|
|
|
|
|
|
|
Shaker sort |
|
|
|
|
|
|
|
|
|
|
|
||
0.10000000 |
|
|
|
|
|
|
|
|
|
|
|
Counting sort |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0.05000000 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0.00000000 |
|
|
|
|
|
|
|
|
|
|
|
|
10 |
100 |
1000 |
10000 |
100000 |
|
|||||||
N-elements (array size)
23 Можемо побачити, що insertion sort найшвидший з представлених алгоритмів, (не враховуючи counting sort) для довільних даних. Selection, Insertion, Shaker sorts - алгоритми з квадратичною складнітю. Відповідно, особливих результатів ми не побачимо. Із зростанням кількості даних швидкість квадатично зменшується.
1.2. Довільні дані ,II-група |
|
|
|
|
|
|
|
Random data |
(II-group) |
|
|
0.45 |
|
|
|
|
|
0.4 |
|
|
|
|
|
0.35 |
|
|
|
|
|
0.3 |
|
|
|
|
|
0.25 |
|
|
|
|
|
0.2 |
|
|
|
|
|
0.15 |
|
|
|
|
|
0.1 |
|
|
|
|
|
0.05 |
|
|
|
|
|
0 |
|
|
|
|
|
10 |
100 |
1000 |
10000 |
100000 |
1000000 |
24
Quick sort
Counting sort
Merge sort
Heap sort
Random data (II-group)
0.45000000 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0.40000000 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0.35000000 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0.30000000 |
|
|
|
|
|
|
|
|
|
|
|
|
Quick sort |
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0.25000000 |
|
|
|
|
|
|
|
|
|
|
|
|
Counting sort |
|
|
|
|
|
|
|
|
|
|
|
|
Merge sort |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0.20000000 |
|
|
|
|
|
|
|
|
|
|
|
|
Heap sort |
|
|
|
|
|
|
|
|
|
|
|
|
||
0.15000000 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0.10000000 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0.05000000 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0.00000000 |
|
|
|
|
|
|
|
|
|
|
|
|
|
10 |
100 |
1000 |
10000 |
100000 |
1000000 |
|
|||||||