Counting Sort and Radix Sort

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

• Реализуются сортировка подсчётом и поразрядная сортировка
• Относятся к устойчивым сортировкам, основанным не на сравнении элементов
• Об использовании:
  • Использование сортировки подсчётом целесообразно, когда диапазон возможных значений входного массива меньше, чем длина массива
  • Сортировка подсчётом используется в качестве подпрограммы для поразрядной сортировки
  • Поразрядную сортировку выгоднее использовать, когда количество разрядов не слишком большое. В таком случае сложность стремится к линейной
• О теоретической сложности:
  • Сортировка подсчётом: O(n + k), где k - диапазон возможных значений массива
  • Поразрядная сортировка: O(d(n + k)), где d - число разрядов максимального числа, k - максимальная цифра в числах массива + 1

Команда "NotForeverAlone"

Группа: 11-104

Фамилия Имя	Вклад (%)	Прозвище
Зорин Виталий	50	Кинг, медвежий грех лени
Ведерникова Дарья	50	дабл принт

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

Наш девиз - всего три слова: "Питонистом быть прикольно"

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

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

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

Требования

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

1. Интерпретатор Python (версия 3.7.x и выше).
2. Рекомендуемый объем оперативной памяти - не менее 4 ГБ.
3. Свободное дисковое пространство объемом ~ 1 ГБ (для входного набора данных).

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

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

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

git clone https://github.com/Addefan/semester-project-radix-sort.git

Сборка и запуск проекта осуществляется через среду разработки.

Видео-инструкция по сборке проекта

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

Формат данных: comma-seperated values (CSV).

Инструкции по генерации:

# переход в папку генерации набора данных
cd dataset

# запуск Python-скрипта
python generate_csv_dataset.py <output> --samples 100 --sort counting --boundary 100

• <output> - выходной файл;
• --samples - количество генерируемых элементов;
• --sort - вид сортировки (counting или radix);
• --boundary - граница генерируемых чисел

Тестовые данные представлены в CSV формате (см. dataset/data/counting_sort/01/100.csv:

35
308
260
...

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

Пример. Генерация CSV-файла для поразрядной сортировки со ста элементами из промежутка [100, 1000):

cd dataset
python generate_csv_dataset.py data/radix_sort/01/100.csv --samples 100 --sort radix --boundary 1000

где <output> = data/radix_sort/01/100.csv

Видео-инструкция по генерации данных

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

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

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

• нажав кнопку "СКАЧАТЬ ВСЕ" в правом верхнем углу, если вы не авторизованы в Google
• нажав ПКМ по папке data и далее нажав на кнопку "Скачать", если вы авторизованы в Google

Скачанный архив необходимо разархивировать в dataset

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

Название	Описание	Метрики
counting_sort	сортировка подсчётом	время
radix_sort	поразрядная сортировка	время

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

python benchmark/<control-test> <input> <output> --trials 50

• `' - название контрольного теста (например, counting_sort_benchmark);
• <input> - входной файл с набором данных в формате CSV;
• <output> - выходной файл с результатами контрольного теста;
• --trials - количество прогонов на наборе данных

Пример. Поразрядная сортировка 10000 случайных элементов (повторить операцию 50 раз и записать время):

python benchmark/radix_sort_benchmark.py dataset/data/radix_sort/01/10000.csv benchmark/metrics.txt --trials 10

где <input> = dataset/data/radix_sort/01/10000.csv и <output> = benchmark/metrics.txt.

Видео-инструкция по запуску контрольных тестов

Источники

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

• Статья на Википедии о сортировке подсчётом (ru)
• Видео от Фоксфорда о сортировке подсчётом
• Статья на Википедии о поразрядной сортировке (en)
• Видео от Фоксфорда о поразрядной сортировке

Это не плагиат, это уважение чужого труда и помощь своим сокурсникам более подробно разобраться в теме.