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

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

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

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

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

История

Сортировка по системе счисления возникла в 1887 году, когда Герман Холлерит работал над табулирующими машинами . Алгоритмы сортировки по основанию стали широко использоваться как способ сортировки перфокарт еще в 1923 году.

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

В современную эпоху поразрядная сортировка чаще всего применяется к коллекциям двоичных строк и целых чисел . В некоторых тестах было показано, что он быстрее, чем другие алгоритмы сортировки более общего назначения, иногда на 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, сам по себе может быть отсортирован по основанию с использованием следующей по значимости цифры без ссылки на другие сегменты, созданные на предыдущем шаге. Как только будет достигнута последняя цифра, для завершения сортировки достаточно объединить сегменты.

Примеры

Младшая значащая цифра

Список ввода:

[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}]

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

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

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

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

Самая значащая цифра, прямая рекурсия

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

[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]

Сложность и производительность

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

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

Специализированные варианты

Реализации поразрядной сортировки MSD на месте

Бинарная поразрядная сортировка MSD, также называемая быстрой двоичной сортировкой, может быть реализована на месте путем разделения входного массива на два интервала — интервал 0 и интервал 1. Интервал 0 увеличивается с начала массива, тогда как интервал 1 увеличивается с конца массива. Граница интервала 0s размещается перед первым элементом массива. Граница интервала 1 с размещается после последнего элемента массива. Проверяется старший бит первого элемента массива. Если этот бит равен 1, то первый элемент заменяется элементом перед границей интервала 1s (последний элемент массива), а интервал 1s увеличивается на один элемент путем уменьшения индекса массива границы 1s. Если этот бит равен 0, то первый элемент остается в своем текущем местоположении, а интервал 0 увеличивается на один элемент. Следующий исследуемый элемент массива находится перед границей ячейки 0 (т. е. первый элемент, который не находится в ячейке 0 или ячейке 1). Этот процесс продолжается до тех пор, пока интервалы 0 и 1 не достигнут друг друга. Затем ячейки 0 и 1 сортируются рекурсивно на основе следующего бита каждого элемента массива. Рекурсивная обработка продолжается до тех пор, пока для сортировки не будет использован младший бит. Обработка целых чисел, дополняющих знаковые два, требует обработки старшего бита с противоположным смыслом, а затем обработки без знака остальных битов.

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

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

Стабильные реализации поразрядной сортировки MSD

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

Гибридные подходы

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

Приложение к параллельным вычислениям

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

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

Доступны более быстрые алгоритмы параллельной сортировки, например, оптимальная сложность O(log( n )) — это алгоритмы Трех венгров и Ричарда Коула. а имеет Бэтчера битоническая сортировка слиянием алгоритмическую сложность O(log ² ( n )), все из которых имеют меньшую алгоритмическую сложность поразрядной сортировки в CREW- PRAM . Самые быстрые известные виды PRAM были описаны в 1991 году Дэвидом М.В. Пауэрсом с помощью параллельной быстрой сортировки, которая может работать за время O(log(n)) на CRCW-PRAM с n процессорами, выполняя неявное разделение, а также поразрядную сортировку, которая работает с использованием тот же трюк в O( k ), где k — максимальная длина ключа. Однако ни архитектура PRAM, ни один последовательный процессор на самом деле не могут быть построены таким образом, чтобы их можно было масштабировать без увеличения количества постоянных задержек разветвления вентилей за цикл, увеличивающихся как O(log( n )), так что, по сути, это конвейерная версия. битонической сортировки слиянием Бэтчера и сортировки PRAM O(log( n )) — это O(log ² ( n )) с точки зрения тактовых циклов, причем Пауэрс признал, что константа Бэтчера будет иметь меньшую константу с точки зрения задержек на воротах, чем его параллельная быстрая сортировка Коула и поразрядная сортировка или сортировка слиянием для независимой от длины ключа сети сортировки O(nlog ² ( н )).

Древовидная поразрядная сортировка

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

См. также

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

Внешние ссылки

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

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

• Указатели на визуализации поразрядной сортировки
• Библиотека USort. Архивировано 7 августа 2011 г. на Wayback Machine. Содержит настроенные реализации поразрядной сортировки для большинства числовых типов C (C99).
• Дональд Кнут . Искусство компьютерного программирования , Том 3: Сортировка и поиск , Третье издание. Аддисон-Уэсли, 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» , Ранджан Синха и Джастин Зобель. В этой статье описывается метод создания попыток сегментов, которые образно распадаются на подпопытки, когда сегменты содержат больше заданной емкости строк, отсюда и название «Пакетная сортировка».
• Структуры открытых данных – Java Edition – Раздел 11.2 – Сортировка подсчетом и поразрядная сортировка , Пэт Морин
• Структуры открытых данных — C++ Edition — Раздел 11.2 — Сортировка подсчётом и поразрядная сортировка , Пэт Морин