Войти
| Класс | Алгоритм сортировки |
|---|---|
| Структура данных | Массив |
| наихудший случай производительность |  , где w - количество требуемых битов для хранения каждого ключа. |
| наихудший случай сложность пространства |  |
В информатике, radix sort - алгоритм сортировки, отличный от сравнительного . Он избегает сравнения за счет создания и распределения элементов по сегментам в соответствии с их основанием. Для элементов с более чем одной значащей цифрой этот процесс группирования повторяется для каждой цифры с сохранением порядка предыдущего шага, пока не будут учтены все цифры. По этой причине Radix sort также называется bucket sort, а цифровая сортировка .
Radix сортировка может применяться к данным, которые могут быть отсортированы. лексикографически, будь то целые числа, слова, перфокарты, игральные карты или почта.
Радиксная сортировка восходит к прошлому вплоть до 1887 г. до работ Германа Холлерита над счетными машинами. Алгоритмы сортировки Radix стали широко использоваться как способ сортировки перфокарт еще в 1923 году.
Первый компьютерный алгоритм с эффективным использованием памяти был разработан в 1954 году в MIT Автор Гарольд Х. Сьюард. Компьютеризированная радиальная сортировка ранее отвергалась как непрактичная из-за предполагаемой потребности в переменном распределении сегментов неизвестного размера. Нововведение Сьюарда заключалось в использовании линейного сканирования для предварительного определения требуемых размеров сегментов и смещений, что позволяло единственное статическое распределение вспомогательной памяти. Линейное сканирование тесно связано с другим алгоритмом Сьюарда - сортировкой со счетом.
В современную эпоху поразрядные сортировки чаще всего применяются к коллекциям двоичных строк и целых чисел. В некоторых тестах было показано, что он быстрее других более универсальных алгоритмов сортировки, иногда от 50% до трех раз быстрее.
Сортировщик карт IBM выполняет сортировку по основанию на большом наборе перфокарты. Карты загружаются в бункер под подбородком оператора и сортируются в одну из 13 выходных корзин машины на основе данных, введенных в один столбец на картах. Кривошип возле входного бункера используется для перемещения считывающей головки к следующему столбцу по мере выполнения сортировки. На задней стенке находятся карты с предыдущего прохода сортировки. Радикс-сортировка может начинаться либо с старшей цифры (MSD), либо с наименьшей значащая цифра (LSD). Например, с 1234 можно начать с 1 (MSD) или 4 (LSD).
LSD-сортировка по основанию счисления обычно использует следующий порядок сортировки: короткие ключи предшествуют более длинным, а затем ключи одинаковой длины сортируются лексикографически. Это совпадает с нормальным порядком целочисленных представлений, например с последовательностью [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] . LSD-сортировки обычно являются стабильными..
MSD-сортировки наиболее подходят для сортировки строк или целочисленных представлений фиксированной длины. Последовательность вида [b, c, e, d, f, g, ba] будет отсортирована как [b, ba, c, d, e, f, g] . Если для сортировки целых чисел переменной длины по основанию 10 используется лексикографический порядок, то числа от 1 до 10 будут выводиться как [1, 10, 2, 3, 4, 5, 6, 7, 8, 9], как если бы более короткие клавиши были выровнены по левому краю и дополнены справа пустыми символами, чтобы сделать более короткие клавиши такими же длинными, как и самая длинная. Сортировка MSD не обязательно стабильна, если всегда необходимо сохранять исходный порядок повторяющихся ключей.
Помимо порядка обхода, сортировки MSD и LSD отличаются обработкой входных данных переменной длины. LSD-сортировки могут группироваться по длине, сортировать каждую группу по основанию, а затем объединять группы по размеру. Сортировка MSD должна эффективно «расширять» все более короткие ключи до размера самого большого ключа и соответственно сортировать их, что может быть сложнее, чем группировка, требуемая LSD.
Однако сортировки MSD более поддаются разделению и рекурсии. Каждая корзина, созданная на шаге MSD, может сама быть отсортирована по основанию с использованием следующей наиболее значимой цифры без ссылки на какие-либо другие корзины, созданные на предыдущем шаге. Как только будет достигнута последняя цифра, объединение сегментов - это все, что требуется для завершения сортировки.
Список ввода (основание 10):
Начиная с крайней правой (последней) цифры, отсортируйте числа на основе этой цифры:
Сортировка по следующей левой цифре:
И, наконец, самой левой цифрой:
Для каждого шага требуется всего один проход по данным, поскольку каждый элемент может быть помещен в свою корзину без сравнения с любым другим элементом.
Некоторые реализации поразрядной сортировки выделяют пространство для сегментов, сначала подсчитывая количество ключей, принадлежащих каждому сегменту, прежде чем перемещать ключи в эти сегменты. Количество раз, которое встречается каждая цифра, сохраняется в массиве .
. Хотя всегда можно заранее определить границы сегмента с помощью счетчиков, в некоторых реализациях вместо этого используется динамическое распределение памяти.
Список ввода, числовые строки фиксированной ширины с ведущими нулями:
Первая цифра, в скобках указаны сегменты:
Следующая цифра:
Окончательный цифра:
Остается только конкатенация :
Радиксная сортировка работает за O (nw) время, где n - количество ключей, а w - длина ключа. Варианты LSD могут достичь нижней границы w «средней длины ключа» при разделении ключей переменной длины на группы, как описано выше.
Оптимизированная сортировка по основанию счисления может выполняться очень быстро при работе в домене, который им подходит. Они ограничены лексикографическими данными, но для многих практических приложений это не ограничение. Большие размеры ключей могут препятствовать реализации LSD, когда индуцированное количество проходов становится узким местом.
Бинарная основанная сортировка MSD, также называется двоичной быстрой сортировкой, может быть реализована на месте путем разделения входного массива на две ячейки - ячейку 0 и ячейку 1. Бин 0s увеличивается с начала массива, тогда как интервал 1s увеличивается с конца массива. Граница бина 0s помещается перед первым элементом массива. Граница ячейки размером 1 с помещается после последнего элемента массива. Проверяется старший бит первого элемента массива. Если этот бит равен 1, то первый элемент заменяется элементом перед границей ячейки 1s (последний элемент массива), а ячейка 1s увеличивается на один элемент за счет уменьшения индекса массива границы 1s. Если этот бит равен 0, то первый элемент остается в своем текущем местоположении, а интервал 0s увеличивается на один элемент. Следующим исследуемым элементом массива является тот, который находится перед границей бина 0 с (т. Е. Первый элемент, который не находится в ячейке 0 или ячейке 1). Этот процесс продолжается до тех пор, пока ячейки нулей и единиц не достигнут друг друга. Бункер 0s и интервал 1s затем рекурсивно сортируются на основе следующего бита каждого элемента массива. Рекурсивная обработка продолжается до тех пор, пока для сортировки не будет использован младший бит. Обработка целых чисел со знаком требует обработки самого старшего бита с противоположным смыслом, а затем беззнаковой обработки остальных битов.
Сортировку по двоичной системе счисления MSD на месте можно расширить до большей системы счисления и сохранить возможность на месте. Подсчетная сортировка используется для определения размера каждой ячейки и их начального индекса. Перестановка используется для помещения текущего элемента в его корзину с последующим расширением границы корзины. Когда элементы массива сканируются, ячейки пропускаются, и обрабатываются только элементы между ячейками, пока не будет обработан весь массив и все элементы не окажутся в своих соответствующих ячейках. Количество ячеек такое же, как и используемая система счисления, например 16 ячеек для системы счисления 16. Каждый проход основан на одной цифре (например, 4 бита на цифру в случае 16-кратной системы счисления), начиная с старшей цифры. Затем каждая ячейка обрабатывается рекурсивно с использованием следующей цифры, пока все цифры не будут использованы для сортировки.
Ни местная двоичная сортировка, ни n-разрядная сортировка, описанные в параграфах выше, не являются стабильные алгоритмы.
Радиксная сортировка MSD может быть реализована как стабильный алгоритм, но требует использования буфера памяти того же размера, что и входной массив. Эта дополнительная память позволяет сканировать входной буфер от первого элемента массива до последнего и перемещать элементы массива в целевые ячейки в том же порядке. Таким образом, одинаковые элементы будут помещены в буфер памяти в том же порядке, в котором они были во входном массиве. Алгоритм на основе MSD использует дополнительный буфер памяти в качестве вывода на первом уровне рекурсии, но меняет местами ввод и вывод на следующем уровне рекурсии, чтобы избежать накладных расходов на копирование результата вывода обратно во входной буфер. Каждый из бинов рекурсивно обрабатывается, как это делается для сортировки по основанию MSD на месте. После завершения сортировки по последней цифре выходной буфер проверяется, чтобы увидеть, является ли он исходным входным массивом, и если это не так, выполняется единичная копия. Если размер цифр выбран так, что размер ключа, деленный на размер цифры, является четным числом, копии в конце избегают.
Радиксная сортировка, например, двухпроходная метод, в котором сортировка подсчета используется во время первого прохода каждого уровня рекурсии, имеет большие постоянные накладные расходы. Таким образом, когда ячейки становятся маленькими, следует использовать другие алгоритмы сортировки, такие как сортировка вставкой. Хорошая реализация сортировки вставкой является быстрой для небольших массивов, стабильной, на месте и может значительно ускорить сортировку по основанию.
Обратите внимание, что этот алгоритм рекурсивной сортировки имеет особое приложение для параллельных вычислений, поскольку каждый из интервалов может быть отсортирован независимо. В этом случае каждая ячейка передается следующему доступному процессору. Один процессор будет использоваться в начале (старшая цифра). По второй или третьей цифре, вероятно, будут задействованы все доступные процессоры. В идеале, когда каждое подразделение полностью отсортировано, будет использоваться все меньше и меньше процессоров. В худшем случае все ключи будут идентичны или почти идентичны друг другу, в результате чего не будет преимуществ от использования параллельных вычислений для сортировки ключей.
На верхнем уровне рекурсии возможность параллелизма находится в части алгоритма сортировка подсчета. Подсчет очень параллелен, подчиняется шаблону parallel_reduce и хорошо распределяет работу между несколькими ядрами до достижения предела пропускной способности памяти. Эта часть алгоритма имеет независимый от данных параллелизм. Однако обработка каждого бина на последующих уровнях рекурсии зависит от данных. Например, если бы все ключи имели одно и то же значение, тогда была бы только одна ячейка с любыми элементами в ней, и параллелизм был бы недоступен. Для случайных входных данных все ячейки будут заполнены почти одинаково, и будет доступно большое количество возможностей параллелизма.
Обратите внимание, что доступны более быстрые алгоритмы параллельной сортировки, например оптимальная сложность O (log (n)) - это те трех венгров и Ричарда Коула и Батчера сортировка битонным слиянием имеет алгоритмическую сложность O (log (n)), все из которых имеют более низкую алгоритмическую временную сложность для основания сортировка на ЭКИПАЖЕ- PRAM. Самые быстрые из известных сортов PRAM были описаны в 1991 году Дэвидом Пауэрсом с помощью параллельной быстрой сортировки, которая может работать за время O (log (n)) в CRCW-PRAM с n процессорами, выполняя неявное разбиение, а также радикальную сортировку, которая работает с использованием тот же трюк в O (k), где k - максимальная длина ключа. Однако ни архитектура PRAM, ни отдельный последовательный процессор на самом деле не могут быть построены таким образом, чтобы можно было масштабировать без увеличения количества постоянных разветвленных задержек ворот за цикл на O (log (n)), поэтому что на самом деле конвейерная версия битонной сортировки слияния Batcher и сортировки O (log (n)) PRAM - все O (log (n)) с точки зрения тактовых циклов, при этом Пауэрс признает, что Batcher будет иметь более низкую константу с точки зрения задержек ворот чем его параллельная быстрая сортировка и поразрядная сортировка или сортировка слиянием Коула для независимой от длины ключа сортировочной сети из O (nlog (n)).
Радиксная сортировка также может быть выполнена путем построения trie (или radix tree ) из входного набора и выполнения предварительный заказ обход. Это похоже на взаимосвязь между heapsort и структурой данных heap. Это может быть полезно для определенных типов данных, см. burstsort.
 | Викибук Реализация алгоритма имеет страницу по теме: Радиксная сортировка |
