Quick Sort

Краткое описание семестрового проекта:

• Quick Sort или Быстрая сортировка - Один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем O(n*log(n)) обменов при упорядочении n элементов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками.
• QuickSort является существенно улучшенным вариантом алгоритма сортировки с помощью прямого обмена (его варианты известны как «Пузырьковая сортировка» и «Шейкерная сортировка»), известного в том числе своей низкой эффективностью. Принципиальное отличие состоит в том, что в первую очередь производятся перестановки на наибольшем возможном расстоянии и после каждого прохода элементы делятся на две независимые группы. (Таким образом улучшение самого неэффективного прямого метода сортировки дало в результате один из наиболее эффективных улучшенных методов.)

Общий алгоритм сортировки: Быстрая сортировка относится к алгоритмам «разделяй и властвуй».

Алгоритм состоит из трёх шагов:

• Выбрать из массива элемент, называемый опорным. Это может быть любой из элементов массива. От выбора опорного элемента не зависит корректность алгоритма, но в отдельных случаях может сильно зависеть его эффективность (см. ниже).
• Сравнить все остальные элементы с опорным и переставить их в массиве так, чтобы разбить массив на три непрерывных отрезка, следующих друг за другом: «элементы меньшие опорного», «равные» и «большие».
• Для отрезков «меньших» и «больших» значений выполнить рекурсивно ту же последовательность операций, если длина отрезка больше единицы.

На практике массив обычно делят не на три, а на две части: например, «меньшие опорного» и «равные и большие»; такой подход в общем случае эффективнее, так как упрощает алгоритм разделения

• Теоретическое время работы алгоритма:

  • Худшее время O(n2).
  • Лучшее время O(n log n) (обычное разделение) или O(n) (разделение на 3 части).
  • Среднее время O(n log n).

• Затраты памяти:

  • O(n) вспомогательных.
  • O(log n) вспомогательных (Седжвик 1978).

Индивидуальный участник "Выживаю"

Фамилия Имя	Вклад (%)	Прозвище	Роль
Шкалин Вячеслав	100	Человек-full	Код, реализация, бенчмарки, readme, график

Девиз

ога

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

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

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

Системные требования

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

1. С++ компилятор c поддержкой стандарта C++17 (например, GNU GCC 8.1.x и выше).

2. Система автоматизации сборки CMake (версия 3.12.x и выше).

3. Рекомендуемый объем оперативной памяти - не менее 12 ГБ.

4. Свободное дисковое пространство объемом ~ 1,5 ГБ (набор данных для контрольных тестов).

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

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

Пример (Windows)

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

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

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

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

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

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

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

Тестовые данные представлены в CSV формате.

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

Контрольные тесты

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

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

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

Название	Описание	Метрики
quick_benchmark	сортировка массива определенного размера	время

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

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

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

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

Источники

• Википедия (RU)
• Википедия (EN)
• Хабр 1
• Хабр 2
• Статья 1
• Статья 2