Поразрядная сортировка

Алгоритм поразрядной сортировки достаточно популярен, но не все существующие его программные реализации оптимальны по структуре и эффективности. Многие авторы выполняют его реализацию с расчётом на практически универсальное применение, что приводит к значительному снижению быстродействия. По этой причине многие пользователи полагают, что алгоритм поразрядной сортировки представляет чисто академический интерес. Но на самом деле есть очень достойные выполнения этого алгоритма. Рассмотрим один из вариантов.

Алгоритм поразрядной сортировки

Рассмотрим алгоритм поразрядной сортировки, именуемый burst::radix_sort, с позиции удобства его использования и скорости его работы. Ниже приведён график сравнения скорости работы алгоритма burst::radix_sort со стандартными алгоритмами std::sort и boost::integer_sort при восьми битной разрядности и количестве элементов 100000 —100000.

Статья: Поразрядная сортировка

Найди решение своей задачи среди 1 000 000 ответов

Найти решение задачи

Рисунок 1. Алгоритм поразрядной сортировки. Автор24 — интернет-биржа студенческих работ

Сравнение проводилось на компьютере с процессором Core i7 3.40GHz. Если взять ноутбук, то там превосходство burst::radix_sort ещё больше.

В качестве интерфейса взят стандартный алгоритм std::sort. В качестве исходного варианта принимаются лишь два итератора. Они задают диапазон сортировки, а составляющие компоненты диапазона определяются отношением порядка оператор «меньше». Для осуществления сортировки этих данных хватает:

Рисунок 2. Код. Автор24 — интернет-биржа студенческих работ

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

Рисунок 3. Код. Автор24 — интернет-биржа студенческих работ

В случае, когда все компоненты исходного диапазона сортировки являются целыми числами, то рассматриваемый алгоритм практически совпадает с std::sòrt:

Рисунок 4. Код. Автор24 — интернет-биржа студенческих работ

Если же исходные компоненты не являются числами, необходимо задавать представление этих компонентов в числовом формате. Это представление станет отображаться как третий аргумент функции:

Рисунок 5. Код. Автор24 — интернет-биржа студенческих работ

Данный интерфейс не включает в свой состав возможность выделения числовых разрядов. Предполагается, что это делается отдельно другим алгоритмом.

Дополнительная память

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

1. Для массива промежуточных итогов сортировки одного разряда.
2. Для массива количества компонентов.

Сохранить промежуточные итоги вычислений можно двумя способами:

1. Выделение памяти для массива в составе функции.
2. Передача буфера наружу.

Оптимальным решением для пользователя будет передача буфера снаружи. При этом буфер задаётся как итератор на начальный адрес участка памяти, размером больше, чем размер диапазона сортировки. Преимущества такого способа:

1. Он более гибкий, поскольку пользователю нет необходимости выделять участок памяти в точности соответствующий размеру диапазона сортировки. Можно определить разово достаточно большой участок памяти и применять его по мере необходимости для различных объёмов сортировки.
2. Этот способ наиболее эффективный, поскольку при многократных сортировках требуется однократное выделение памяти для буфера с последующей передачей его для сортировки. И программа сортировки не затрачивает время на эти процедуры. С учётом вышеизложенного, следующая версия интерфейса будет такой:

Рисунок 6. Код. Автор24 — интернет-биржа студенческих работ

Очевидно, что проблема вычисления объёмов и числа разрядов, заданию требуемых размеров массивов для счётчиков и трансляция этих счётчиков в функцию сортировки, является очень непростой задачей и простому пользователю она далеко не всегда по силам.

Выделение разрядов из чисел

Наиболее простым, но не самым лучшим, является метод передачи в функцию основания, являющегося целым числом. Остаток от деления на это основание и будет одним разрядом. Естественно, что самым ходовым основанием является число десять. Несколько лучшие результаты может дать применение степени числа два как основания. Вернее, основанием является двойка, а в аргументе функции идёт её степень, но и это не идеал. Иногда пользователю предлагается самому задавать разрядность, а также минимум и максимум числового веса одного разряда. Это тоже не очень хорошо, так как есть вероятность задания пользователем недопустимых значений параметров.

Для выбора оптимального решения, необходимо учитывать следующие моменты:

1. В идеале пользователь должен иметь возможность сортировать все разряды. То есть, как правило, сортировка начинается с первого разряда и выполняется поочерёдно до последнего разряда. Иногда может потребоваться в виде исключения пропуск отдельных разрядов, но это редко бывает и решаемо.
2. Наилучшим типом разряда будем считать один байт, поскольку его используют все компьютеры. Хотя, если брать сверхмалые сортировки, с числом элементов не более двадцати чисел с размером один байт, то там удобнее брать разрядом половину байта. Но это скорее исключение, чем правило.

Исходя из вышеизложенного и следует формировать окончательную версию программы.