Timsort - алгоритм основанный на Merge и Insertion sort, сложность по времени в стандартной реализации O(nlogn), в данной O(nlog^2n), сложность по памяти в стандартной реализации O(n), в данной O(1). Опубликован в 2002 году Тимом Петерсом. Является стандартным алгоритмом сортировки в некоторых популярных языках программирования (Python, Swift и т.д.)
Merge sort - сортировка слиянием. Упорядочивает списки, либо любые другие структуры данных, которые можно получать только последовательно, в нужном порядке. Основана на принципе "разделяй и властвуй". Есть несколько вариантов реализации: top-down и bottom-up. Первый вариант рекурсивно разделяет список на списки состоящие из половин исходного, сортирует их и потом объединяет. Второй вариант сначала разделяет исходный список на списки длины 1, а затем последовательно и упорядочено собирает их в списки с размером в два раза больше. Сложность по времени в стандартной реализации O(nlogn), в данной O(nlog^2n), сложность по памяти в стандартной реализации O(n), в данной O(1).
Заполните таблицу с указанием вклада каждого из участников в проект.
Примечание. Преподаватель может определить вклад любого из участников команды по истории коммитов.
| Фамилия Имя | Вклад (%) | Прозвище |
|---|---|---|
| Давлятов Эмиль | 100 | босс |
Девиз команды
С самого начала у меня была какая-то тактика и я её придерживался.
*Проект состоит из следующих частей:
src/include- реализация структуры данных (исходный код и заголовочные файлы);benchmark- контрольные тесты производительности структуры данных (операции добавления, удаления, поиска и пр.);dataset/data- наборы данных для запуска контрольных тестов и их генерация;dataset/out- результаты бенчмарков
Рекомендуемые требования:
- С++ компилятор c поддержкой стандарта C++17 (например, GNU GCC 8.1.x и выше).
- Система автоматизации сборки CMake (версия 3.12.x и выше).
- Рекомендуемый объем оперативной памяти - не менее 6 ГБ.
- Свободное дисковое пространство объемом ~ 3 ГБ (набор данных для контрольных тестов).
Склонируйте проект к себе на устройство через Git for Windows (либо используйте возможности IDE):
git clone https://github.com/Algorithms-and-Data-Structures-2021/semester-work-merge-and-insertion-sort.gitДля ручной сборки проекта в терминале введите:
# переход в папку с проектом
cd C:\Users\username\asd-projects\semester-work-merge-and-insertion-sort
# создание папки для файлов сборки (чтобы не засорять папку с проектом)
mkdir -p build && cd build
# сборка проекта
cmake .. -DCMAKE_BUILD_TYPE=RelWithDebInfo && cmake --config RelWithDebInfo --build . Тестовые данные хранятся в формате CSV, сгенерировать их вы можете при помощи приложенного в google drive .jar файла, либо же взять уже готовые.
Для генерации данных при помощи jar файла вы должны скачать файл из папки google drive
После двойного клика по загруженному файлу, откроется следующее окно, куда вы должны будете ввести путь до папки, где собираетесь хранить тестовые данные^
После нажатия на кнопку Generate! и пятисекундного ожидания в указанной вами папки появятся сгенерированные случайно значения.
Генерация тестового набора данных в формате comma-seperated values (CSV):
Папка с тестовыми данными и файлом java
Для запуска контрольных тестов необходимо предварительно сгенерировать или скачать готовый набор тестовых данных.
| Название | Описание | Метрики |
|---|---|---|
merge_sort_benchmark |
тестирование временной сложности Merge sort | время |
timsort_benchmark |
тестирование временной сложности Timsort | время |
Генерируете набор тестовых данных, либо скачиваете с google drive. Процесс генерации описан выше.
Помещаете его по пути dataset\data
Открываете .cpp файл нужного бенчмарка двойным нажатием на него
Запускаете метод main
Результаты будут сохранены в отдельный csv файл по пути dataset\data для merge sort в файле merge\res.csv, для timsort - tim\res.csv
Список использованных при реализации алгоритма источников.
Merge sort on wiki
Merge sort on GFG
Timsort on GFG
Timsort on wiki
Timsort on habr