Название семестровой работы

Краткое описание семестрового проекта. Следует отразить информацию по следующим пунктам:

• Какая структура данных реализуется?
• Что она из себя представляет (сбалансированное дерево, линейный список и пр.)?
• Где и как она используется (приложения)?
• Какие операции над ней можно выполнять (поиск, удаление, добавление, вставка и пр.)?
• Какова теоретическая сложность операций (поиск за O(log(n)), вставка за O(n^2) и т.д.)?
• Какая-то другая справочная информация о проекте.

Merge sort - сортировка слиянием. Упорядочивает списки, либо любые другие структуры данных, которые можно получать только последовательно, в нужном порядке. Основана на принципе "разделяй и властвуй". Есть несколько вариантов реализации: top-down и bottom-up. Первый вариант рекурсивно разделяет список на списки состоящие из половин исходного, сортирует их и потом объединяет. Второй вариант сначала разделяет исходный список на списки длины 1, а затем последовательно и упорядочено собирает их в списки с размером в два раза больше. Сложность по времени в стандартной реализации O(nlogn), в данной O(nlog^2n), сложность по памяти в стандартной реализации O(n), в данной O(1).

Timsort - алгоритм основанный на Merge и Insertion sort, сложность по времени в стандартной реализации O(nlogn), в данной O(nlog^2n), сложность по памяти в стандартной реализации O(n), в данной O(1). Опубликован в 2002 году Тимом Петерсом. Является стандартным алгоритмом сортировки в некоторых популярных языках программирования (Python, Swift и т.д.)

Команда "Oriental fairy tales"

Заполните таблицу с указанием вклада каждого из участников в проект.

Примечание. Преподаватель может определить вклад любого из участников команды по истории коммитов.

Фамилия Имя	Вклад (%)	Прозвище
Суржиков Ярослав	33.3(3)	Писатель, в простонародие бухгалтер
Сивачев Никита	33.3(3)	Властелин кода
Яковлев Алмаз	33.3(3)	Тестировщик

Девиз команды

Что-то делаем, надеемся делаем правильно.

Структура проекта

Пример. Проект состоит из следующих частей:

• src/include - реализация структуры данных (исходный код и заголовочные файлы);
• benchmark - контрольные тесты производительности структуры данных (операции добавления, удаления, поиска и пр.);
• examples - примеры работы со структурой данных;
• dataset - наборы данных для запуска контрольных тестов и их генерация;

Требования (Prerequisites)

Рекомендуемые требования:

1. С++ компилятор c поддержкой стандарта C++17 (например, GNU GCC 8.1.x и выше).
2. Система автоматизации сборки CMake (версия 3.12.x и выше).
3. Интерпретатор Python (версия 3.7.x и выше).
4. Рекомендуемый объем оперативной памяти - не менее 4 ГБ.
5. Свободное дисковое пространство объемом ~ 3 ГБ (набор данных для контрольных тестов).

Сборка и запуск

Инструкция по сборке проекта, генерации тестовых данных, запуска контрольных тестов и примеров работы.

Постарайтесь написать инструкцию так, чтобы незнакомый с проектом человек смог самостоятельно всё запустить.

Пример (Windows)

Сборка проекта

Склонируйте проект к себе на устройство через Git for Windows (либо используйте возможности IDE):

git clone https://github.com/Algorithms-and-Data-Structures-2021/semester-work-template.git

Для ручной сборки проекта в терминале введите:

# переход в папку с проектом
cd C:\Users\username\asd-projects\semester-work-template

# создание папки для файлов сборки (чтобы не засорять папку с проектом) 
mkdir -p build && cd build 

# сборка проекта
cmake .. -DCMAKE_BUILD_TYPE=RelWithDebInfo && cmake --config RelWithDebInfo --build . 

Генерация тестовых данных

Тестовые данные хранятся в формате txt, сгенерировать их вы можете при помощи приложенного генератора на языке Python.

По названию директории /dataset/data/add можно понять, что здесь хранятся наборы данных для контрольных тестов по добавлению элементов в структуру данных. Названия файлов 100.csv. 5000000.csv и т.д. хранят информацию о размере набора данных (т.е. количество элементов).

Контрольные тесты (benchmarks)

Для запуска контрольных тестов необходимо предварительно сгенерировать или скачать готовый набор тестовых данных.

Примечание. Во избежание "захламления" репозитория большим объёмом данных рекомендуется указать ссылку на архив с набором данных, который при необходимости можно скачать по ссылке. Наборы данных должны находиться в папке семестровой работы на Google Drive.

Список контрольных тестов

Название	Описание	Метрики
demo_benchmark	Тестирование временной сложности Merge и Timsort	время

Примеры запуска

Генерируем набор случайных данных в cpp файле, запускаем метод main. Complete! Легче лёгкого. Результаты хранятся в txt файле под названием result(N)

Источники

Список использованных при реализации структуры данных источников.

_https://en.wikipedia.org/wiki/Merge_sort#Use_with_tape_drives

https://www.geeksforgeeks.org/merge-sort/

https://ru.wikipedia.org/wiki/Timsort

https://habr.com/ru/company/infopulse/blog/133303/