В корневой папке проекта присутствуют следующие директории:
-
Debug - файлы, используемые при отладке программы.
- data.txt - файл, содержащий в себе показатели и результаты всех сортировок одного вектора
- TXTWriter.cpp - функция для записи необходимой информации о сортировках одного вектора в файл data.txt.
-
Enums - перечисления:
- ArrayTypeEnum.h - перечисление видов генерации массивов.
- FunctionEnum.h - перечисление видов сортировок.
-
Headers - заголовки:
- AlgoHeader.h - инклюды, используемые в каждой из 12 сортировок.
- SortingHeaders.h - инклюды всех сортировок, чтобы не захламлять ими main.cpp.
-
Output - выходные файлы:
- data.csv - файл, содержащий всю требуемую заданием информацию о сортировках.
-
Services - вспомогательные функции:
- ArrayGenerator.cpp - 4 функции генерации массивов, описанные в задании.
- CSVWriter.cpp - функции для работы с data.csv.
- GetTimespan.cpp - функция получения временного интервала между переданным значением времени и текущем.
-
SortingAlgorithms - функции, реализующие различные сортировки, которые взяты для анализа согласно заданию.
-
SortingScript - анализ полученного файла data.csv с помощью Python и Jupyter Notebook:
- Graphs.ipynb - сам Notebook, включающий в себя код анализа полученного data.csv файла.
- data.csv - файл, содержащий всю требуемую заданием информацию о сортировках.
В качестве оценок работы сортировок используются время в наносекундах и количество элементарных операций, используемых сортировкой:
- Стандартные арифметические операции (сложение, вычитание, умножение, деление).
- Сравнение, присваивание.
- std::swap(i, j).
-
Наблюдаемые в построенных графиках выбросы могут быть порождены тем фактом, что работа реализована не на обычных массивах, а на динамических, которые копируют содержимое в новый вектор в случае заполнения capacity, из-за чего, очевидно, может существенно повыситься время выполнения сортировки на больших размерах исходного сортируемого массива.
-
Чтобы получить более достоверные данные касательно времени сортировки, каждая из них выполняется над одним и тем же массивом 30 раз. Полученное время усредняется.
-
Количество элементарных операций и время работы сортировки измеряется непосредственно в самой функции сортировки для исключения возможности "погрешности" из-за затраты времени на вызов функции.
-
В течение последних двух часов работы над проектом (и, соответственно, как полагается любому уважающему себя студенту, за два часа до дедлайна) было замечено, что сортировки массива, заполненного случайными элементами от 0 до 5, ведут себя подозрительно странно и работают даже медленне, чем сортировки массивов, заполненных элементами от 0 до 4100. По возможности, я проведу анализ и напишу здесь же о причинах такого парадокса.