Сортировка по радиксу

Сортировка по радиксу

Сорт	Алгоритм сортировки
Структура данных	Множество
Худший вариант производительности	${\displaystyle O(w\cdot n)}$, где — количество ключей, — длина ключа.${\displaystyle n}$${\displaystyle w}$
Наихудшая сложность пространства	${\displaystyle O(w+n)}$
Оптимальный	совершенно верно

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

Радикальную сортировку можно применять к данным, которые можно отсортировать лексикографически , будь то целые числа, слова, перфокарты, игральные карты или почта .

Радикальная сортировка появилась еще в 1887 году, когда Герман Холлерит работал над табуляторами . ^[1] Алгоритмы радиксной сортировки стали широко использоваться в качестве способа сортировки перфокарт еще в 1923 году. ^[2]

Первый эффективный по памяти компьютерный алгоритм для этого метода сортировки был разработан в 1954 году в Массачусетском технологическом институте Гарольдом Х. Сьюардом . Компьютеризированные радиксные сортировки ранее были отклонены как непрактичные из-за предполагаемой необходимости переменного распределения блоков неизвестного размера. Инновация Сьюарда заключалась в использовании линейного сканирования для предварительного определения требуемых размеров и смещений блоков, что позволяло выполнить единое статическое распределение вспомогательной памяти. Линейное сканирование тесно связано с другим алгоритмом Сьюарда — сортировкой подсчетом .

В современную эпоху радиксные сортировки чаще всего применяются к коллекциям двоичных строк и целых чисел . В некоторых тестах производительности было показано, что они быстрее других более универсальных алгоритмов сортировки, иногда на 50% или в три раза быстрее. ^{[3] [4] [5]}

Сортировки Radix могут быть реализованы так, чтобы начинаться либо с самой старшей цифры (MSD), либо с самой младшей цифры (LSD). Например, в случае с 1234 можно начать с 1 (MSD) или 4 (LSD).

Сортировки LSD radix обычно используют следующий порядок сортировки: короткие ключи идут перед более длинными ключами, а затем ключи той же длины сортируются лексикографически . Это совпадает с обычным порядком целочисленных представлений, например, последовательностью [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] . Сортировки LSD обычно являются стабильными сортировками .

Сортировки MSD radix наиболее подходят для сортировки строк или целочисленных представлений фиксированной длины. Последовательность типа [b, c, e, d, f, g, ba] будет отсортирована как [b, ba, c, d, e, f, g] . Если лексикографическое упорядочение используется для сортировки целых чисел переменной длины в десятичной системе счисления, то числа от 1 до 10 будут выведены как [1, 10, 2, 3, 4, 5, 6, 7, 8, 9] , как если бы более короткие ключи были выровнены по левому краю и дополнены справа пробелами, чтобы сделать более короткие ключи такими же длинными, как и самый длинный ключ. Сортировки MSD не обязательно стабильны, если исходный порядок дубликатов ключей должен всегда сохраняться.

За исключением порядка обхода, сортировки MSD и LSD различаются в обработке входных данных переменной длины. Сортировки LSD могут группировать по длине, сортировать по основанию каждую группу, а затем объединять группы в порядке размера. Сортировки MSD должны эффективно «расширять» все более короткие ключи до размера самого большого ключа и сортировать их соответствующим образом, что может быть сложнее группировки, требуемой LSD.

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

Список входных данных:

[170, 45, 75, 90, 2, 802, 2, 66]

Начиная с самой правой (последней) цифры, отсортируйте числа по этой цифре:

[{17 0 , 9 0 }, { 2 , 80 2 , 2 }, {4 5 , 7 5 }, {6 6 }]

Сортировка по следующей слева цифре:

[{ 0 2, 8 0 2, 0 2}, { 4 5}, { 6 6}, {1 7 0, 7 5}, { 9 0}]

Обратите внимание, что к двум двоекам добавлена ​​неявная цифра 0 , так что 802 сохраняет свое положение между ними.

И наконец, самая левая цифра:

[{ 0 0 2, 0 0 2, 0 45, 0 66, 0 75, 0 90}, { 1 70}, { 8 02}]

Обратите внимание, что ко всем 1- или 2-значным числам добавляется 0 .

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

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

Хотя всегда можно заранее определить границы сегмента с помощью счетчиков, некоторые реализации предпочитают вместо этого использовать динамическое распределение памяти.

Входной список, числовые строки фиксированной ширины с ведущими нулями:

[170, 045, 075, 025, 002, 024, 802, 066]

Первая цифра, в скобках указаны ведра:

[{ 0 45, 0 75, 0 25, 0 02, 0 24, 0 66}, { 1 70}, { 8 02}]

Обратите внимание, что 170 и 802 уже завершены, поскольку это все, что осталось в их сегментах, поэтому дальнейшая рекурсия не нужна.

Следующая цифра:

[{ {0 0 2}, {0 2 5, 0 2 4}, {0 4 5}, {0 6 6}, {0 7 5} }, 170, 802]

Последняя цифра:

[ 002, { {02 4 }, {02 5 } }, 045, 066, 075, 170, 802]

Остается только конкатенация:

[002, 024, 025, 045, 066, 075, 170, 802]

Сортировка Radix работает во времени, где — количество ключей, а — длина ключа. Варианты LSD могут достигать нижней границы для «средней длины ключа» при разделении ключей переменной длины на группы, как обсуждалось выше.${\displaystyle O(n\cdot w)}$${\displaystyle n}$${\displaystyle w}$${\displaystyle w}$

Оптимизированные радиксные сортировки могут быть очень быстрыми, если работают в подходящей для них области. ^[6] Они ограничены лексикографическими данными, но для многих практических приложений это не является ограничением. Большие размеры ключей могут помешать реализации LSD, когда индуцированное число проходов становится узким местом. ^[2]

Двоичная сортировка MSD radix, также называемая двоичной быстрой сортировкой, может быть реализована на месте путем разделения входного массива на два контейнера — контейнер 0s и контейнер 1s. Контейнер 0s увеличивается с начала массива, тогда как контейнер 1s увеличивается с конца массива. Граница контейнера 0s помещается перед первым элементом массива. Граница контейнера 1s помещается после последнего элемента массива. Проверяется старший бит первого элемента массива. Если этот бит равен 1, то первый элемент меняется местами с элементом перед границей контейнера 1s (последний элемент массива), а контейнер 1s увеличивается на один элемент путем уменьшения индекса массива границы 1s. Если этот бит равен 0, то первый элемент остается на своем текущем месте, а контейнер 0s увеличивается на один элемент. Следующий элемент массива, который проверяется, находится перед границей ячейки 0 (т. е. первый элемент, который не находится в ячейке 0 или 1). Этот процесс продолжается до тех пор, пока ячейка 0 и ячейка 1 не достигнут друг друга. Ячейка 0 и ячейка 1 затем сортируются рекурсивно на основе следующего бита каждого элемента массива. Рекурсивная обработка продолжается до тех пор, пока для сортировки не будет использован младший бит. ^{[7] [8]} Обработка целых чисел со знаком в дополнительном коде требует обработки старшего бита с противоположным значением, за которой следует беззнаковая обработка остальных битов.

Сортировка по двоичному основанию MSD на месте может быть расширена до большего основания и сохранена возможность сортировки на месте. Сортировка подсчетом используется для определения размера каждого бина и его начального индекса. Обмен используется для помещения текущего элемента в его бину с последующим расширением границы бина. По мере сканирования элементов массива бины пропускаются, и обрабатываются только элементы между бинами, пока весь массив не будет обработан и все элементы не окажутся в своих соответствующих бинах. Количество бинов совпадает с используемым основанием — например, 16 бинов для 16-ридинга. Каждый проход основан на одной цифре (например, 4 бита на цифру в случае 16-ридинга), начиная с самой значимой цифры . Затем каждый бин обрабатывается рекурсивно с использованием следующей цифры, пока все цифры не будут использованы для сортировки. ^{[9] [10]}

Ни двоичная сортировка на месте, ни сортировка по основанию n-бит, обсуждавшиеся в параграфах выше, не являются стабильными алгоритмами .

Сортировка по системе счисления MSD может быть реализована как стабильный алгоритм, но требует использования буфера памяти того же размера, что и входной массив. Эта дополнительная память позволяет сканировать входной буфер от первого элемента массива до последнего и перемещать элементы массива в ячейки назначения в том же порядке. Таким образом, равные элементы будут помещены в буфер памяти в том же порядке, в котором они были во входном массиве. Алгоритм на основе MSD использует дополнительный буфер памяти в качестве выходных данных на первом уровне рекурсии, но меняет местами входные и выходные данные на следующем уровне рекурсии, чтобы избежать накладных расходов на копирование выходного результата обратно во входной буфер. Каждый из ячеек обрабатывается рекурсивно, как это делается для сортировки по системе счисления MSD на месте. После завершения сортировки по последней цифре выходной буфер проверяется, является ли он исходным входным массивом, и если нет, то выполняется одна копия. Если размер цифры выбран таким образом, что размер ключа, деленный на размер цифры, является четным числом, копирование в конце исключается. ^[11]

Сортировка по радиксу, например, двухпроходный метод, где сортировка подсчетом используется во время первого прохода каждого уровня рекурсии, имеет большие постоянные накладные расходы. Таким образом, когда ячейки становятся маленькими, следует использовать другие алгоритмы сортировки, например сортировку вставкой . Хорошая реализация сортировки вставкой быстра для небольших массивов, стабильна, работает на месте и может значительно ускорить сортировку по радиксу.

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

На верхнем уровне рекурсии возможность для параллелизма находится в части сортировки подсчетом алгоритма. Подсчет является высокопараллельным, поддается шаблону parallel_reduce и хорошо разделяет работу между несколькими ядрами до достижения предела пропускной способности памяти. Эта часть алгоритма имеет независимый от данных параллелизм. Однако обработка каждого бина на последующих уровнях рекурсии зависит от данных. Например, если бы все ключи имели одинаковое значение, то был бы только один бин с любыми элементами в нем, и никакой параллелизм не был бы доступен. Для случайных входных данных все бины были бы почти одинаково заполнены, и было бы доступно большое количество возможностей параллелизма. ^[12]

Существуют более быстрые параллельные алгоритмы сортировки, например, оптимальная сложность O(log( n )) у Three Hungarys и Richard Cole ^{[13] [14]} , а битоническая сортировка слиянием Batcher имеет алгоритмическую сложность O(log ² ( n )), все из которых имеют более низкую алгоритмическую временную сложность по сравнению с радиксной сортировкой на CREW- PRAM . Самые быстрые известные сортировки PRAM были описаны в 1991 году Дэвидом М. В. Пауэрсом с помощью распараллеленной быстрой сортировки, которая может работать за время O(log(n)) на CRCW-PRAM с n процессорами, выполняя неявное разбиение, а также радиксной сортировки, которая работает с использованием того же трюка за O( k ), где k — максимальная длина ключа. ^[15] Однако ни архитектура PRAM, ни один последовательный процессор на самом деле не могут быть построены таким образом, чтобы масштабироваться без увеличения числа постоянных задержек вентилей разветвления на цикл как O(log( n )), так что по сути конвейерная версия битонной сортировки слиянием Батчера и сортировки PRAM O(log( n )) все имеют O(log ² ( n )) с точки зрения тактовых циклов, при этом Пауэрс признает, что у Батчера будет более низкая константа с точки зрения задержек вентилей, чем у его параллельной быстрой сортировки и радиксной сортировки или сортировки слиянием Коула для независимой от длины ключа сети сортировки O(nlog ² ( n )). ^[16]

Сортировка Radix также может быть выполнена путем построения дерева (или radix tree ) из входного набора и выполнения обхода в предварительном порядке . Это похоже на связь между пирамидальной сортировкой и структурой данных кучи . Это может быть полезно для определенных типов данных, см. burstsort .

• Сортировщики карт IBM серии 80
• Другие виды распределения
• Сортировка Киркпатрика-Рейша
• Префиксная сумма

Реализация алгоритма Wikibook имеет страницу по теме: Сортировка по радиксу

• Объяснение, псевдокод и реализация на C и Java
• Высокопроизводительная реализация сортировки LSD Radix на JavaScript
• Высокопроизводительная реализация сортировки LSD и MSD Radix на языке C# с исходным кодом на GitHub
• Видеоурок по сортировке MSD Radix
• Демонстрация и сравнение сортировки Radix с пузырьковой сортировкой , сортировкой слиянием и быстрой сортировкой , реализованной на JavaScript
• Статья о радиксной сортировке чисел с плавающей точкой IEEE с реализацией.

  Более быстрая сортировка с плавающей точкой и множественное гистограммирование с реализацией на языке C++

• Указатели на визуализации радиксной сортировки
• Библиотека USort, архивированная 7 августа 2011 г. на Wayback Machine, содержит настроенные реализации радиксной сортировки для большинства числовых типов C (C99).
• Дональд Кнут . Искусство программирования , том 3: Сортировка и поиск , третье издание. Addison-Wesley, 1997. ISBN 0-201-89685-0 . Раздел 5.2.5: Сортировка по распределению, стр. 168–179. 
• Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Стайн . Введение в алгоритмы , второе издание. MIT Press и McGraw-Hill, 2001. ISBN 0-262-03293-7 . Раздел 8.3: Сортировка по основанию, стр. 170–173. 
• Исходный код BRADSORT v1.50, Эдвард Ли. BRADSORT v1.50 — это алгоритм сортировки по основанию, который объединяет бинарную структуру trie с кольцевым двусвязным списком.
• Эффективная сортировка больших наборов строк на основе Trie, Ранджан Синха и Джастин Зобель. В этой статье описывается метод создания попыток блоков, которые образно распадаются на под-попытки, когда блоки содержат больше строк, чем заданная емкость, отсюда и название «Burstsort».
• Открытые структуры данных — Java Edition — Раздел 11.2 — Сортировка подсчетом и сортировка по основанию, Пэт Морин
• Открытые структуры данных - издание C++ - Раздел 11.2 - Сортировка подсчетом и сортировка по основанию, Пэт Морин