Merge sort and Insertion sort

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

Insertion sort - алгоритм сортировки, в котором элементы входной последовательности просматриваются по одному, и каждый новый поступивший элемент размещается в подходящее место среди ранее упорядоченных элементов.

Команда "Die Lit"

Фамилия Имя	Вклад (%)	Прозвище
Рузавин Георгий	=> 100	mob psycho

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

Just to feel like this it took a long time, yeah

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

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

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

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

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

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

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

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

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

Пример (Windows)

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

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

git clone https://github.com/Algorithms-and-Data-Structures-2021/semester-work-merge-and-insertion-sort-DL

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

Генерация тестового набора данных в формате comma-seperated values (CSV):

Инструкция по запуску скрипта:

Номер шага	Папки и файлы
1) Перейдите в папку генерации набора данных.	dataset
2) Откройте файл.	generate_csv_dataset.cpp
3) Запустите метод.	main()
4) В папке dataset есть папка data	data
5) После запуска скрипта, в этих папках появятся папки, внутри которых будут наборы данных для контрольного тестирования.	heap_sort, selection_sort, 01, 02, 03, и т.д.`

Тестовые данные представлены в CSV формате (см. dataset/data/dataset-example.csv):

623,24,35,231,2,10,64,463,4,893

По названию папок, например: /dataset/data/merge_sort, можно понять, что здесь хранятся наборы данных для контрольного тестирования сортировки слиянием. В папке есть дополнительные папки: 01,02,03 и т.д., в каждой из них лежат наборы для контрольного тестирования. Названия файлов 100.csv, 100000.csv, 1000000.csv и т.д. хранят информацию о размере набора данных (т.е. количество элементов).

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

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

Примечание. Вы можете скачать наборы данных для контрольного тестирования, перейдя по ссылке на Google Drive.

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

Название	Описание	Метрики
merge_sort_benchmark	сортировка массива слиянем	время
insertion_sort_benchmark	сортировка массива вставками	время

Инструкция по запуску контрольных тестов:

Номер шага	Папки и файлы
1) Перейдите в папку с контрольными тестами.	benchmark
2) В папке есть 2 файла с контрольными тестами.	merge_sort_benchmark.cpp, insertion_sort_benchmark.cpp
3) Запустите метод main().	main(). Из-за большого объема данных, метод выполняется довольно долго, пожалуйста, подождите какое-то время.
4) В папке results после запуска бенчмарков будут появляться .csv файлы с результатами замеров.	results, insertion_sort_result.csv, merge_sort_result.csv

В файлы записываются 4 числа через запятую:

1. Номер набора данных (от 01 до 10)
2. Количество данных в наборе (от 100 до 50 тыс.)
3. Номер прогона на наборе данных (от 1 до 10)
4. Затраченное время (измеряется в наносекундах)

Источники

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

1.Википедия

2.Университет ИТМО

3.Habr

4.YouTube

Insertion sort:

1.Википедия

2.Habr

3.YouTube

4.ИТМО