LSD-sort

Идея алгоритма.

LSD сортировка - вариант поразрядной сортировки. На вход алгоритма поступает множество элементов, на котором задано отношение линейного порядка. При lsd сортировки двигаемся от младшего разряда к старшему, группирую элементы с одинаковыми цифрами в разряде. Алгоритм использует каждую цифру в качестве ключа и реализует подсчет. Затем элементы возвращаются в последовательность в порядке, в котором они попали в группы при распределении.

Анализ алгоритма.

Подробнее об анализе можно прочитать в файле Анализ сложности алгоритма LSD-сортировки(n).docx

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

Реализация алгоритма.

Реализация представлена в файле lsd-sort.cpp

Входные данные

На вход алгоритма подаётся массив, состоящий из n элементов. Размер массива в диапазоне от 50 до 400. Каждый элемент массива имеет 3 разряда.

Единицы измерения трудоёмкости

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

Способ генерации входных данных

Для генерации входных данных используется встроенная функция C++ - rand(). Для разных n генерируется новый массив в диапазоне от 10 до 500 с шагом 20.**