Сортировка по основанию: версии LSD и MSD

В книге "Введение в алгоритмы" упоминается версия поразрядной сортировки LSD (наименее значащая цифра). Однако, как указывали другие здесь в stackoverflow, также существует версия MSD (самая значащая цифра). Поэтому я хочу знать плюсы и минусы каждого из них. Я предполагаю, что версия LSD имеет некоторые преимущества перед версией MSD, но я не уверен. Отсюда вопрос.


sorting algorithm radix-sort
person Geek    schedule 13.08.2012    source источник
comment
Это некорректный вопрос, потому что оба варианта существуют, но имеют немного разные свойства.   -  person unkulunkulu    schedule 13.08.2012
comment
Хорошо, но это не меняет вопроса. Вы должны изложить это в духе «в чем разница между MSD и LSD, плюсы и минусы» и т. д.   -  person unkulunkulu    schedule 13.08.2012
comment
Что ж, теперь я считаю, что вопрос хороший.   -  person unkulunkulu    schedule 13.08.2012
comment
Плюсы и минусы, вероятно, будут сильно зависеть от вашей проблемной области и ожидаемого использования. Например, сортировка по основанию списка целых чисел от 1000 до 3000, вероятно, будет лучше выполняться с версией LSD, поскольку LSD имеет больший набор возможных значений, что позволяет разбить проблему на большее количество подзадач меньшего среднего размера. чем метод MSD.   -  person twalberg    schedule 13.08.2012
comment
@twalberg, насколько я понимаю, сортировка Radix, каждый проход равен O (n), поэтому размер каждой подзадачи не имеет значения. Можете ли вы расширить это?   -  person Mark Ransom    schedule 03.01.2016
comment
@MarkRansom Если каждый проход действительно O (n), то просто с точки зрения временной сложности вы правы. Тем не менее, IIRC, учитывая 3,5 года, прошедшие с тех пор, как я написал этот комментарий, я предполагал большие наборы данных, которые повлекут за собой накладные расходы на подкачку/подкачку, и в этом случае было бы лучше разделить проблему на 10 O (N / 10) подзадач. проблем, что, возможно, устраняет дополнительные затраты из-за того, что не помещается в основную память, вместо 2 подзадач O (N / 2), которые все еще могут иметь проблемы с емкостью. Аналогичные комментарии относятся к производительности кэша L1/L2/L3 для небольших подзадач...   -  person twalberg    schedule 03.01.2016

Ответы (3)


arrow_upward
11
arrow_downward

Взято из ссылки, может быть полезно: http://www.eternallyconfuzzled.com/tuts/algorithms/jsw_tut_sorting.aspx (в самом низу)

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

person Roman Dzhabarov    schedule 14.08.2012

arrow_upward
6
arrow_downward

Как написано в книге Алгоритмы, LSD и MSD являются алгоритмами сортировки строковых массивов, основанными на так называемый ключевой индексированный подсчет, а не сравнения. Следовательно, LSD и MSD имеют разное время работы по сравнению с традиционной быстрой сортировкой или сортировкой слиянием.

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

В таблице ниже показаны части различий между быстрой сортировкой, LSD и MSD.

algorithm    running time              extra space
quicksort    N(lgN)^2                  1
LSD          NW                        N
MSD          between N and NW          N + WR

где N — длина массива, W — длина строки, а R — размер системы счисления.

PS: как упоминалось в книге, системная сортировка Java использует общий алгоритм сортировки с быстрым сравнением строк, а не LSD или MSD.

person Spectral    schedule 03.01.2016
comment
Быстрая сортировка использует lg(n) дополнительного пространства для стека рекурсии (или эквивалентного). MSD Radix Sort может использовать только дополнительное пространство рекурсивного стека (или его эквивалента), поскольку ему не требуется быть стабильным для корректности, поэтому он может использовать меньше места, чем LSD Radix Sort. - person ReneSac; 23.07.2018

arrow_upward
5
arrow_downward

LSD быстрее, чем MSD, когда есть фиксированная длина. MSD слишком медленный для небольших файлов и требует огромного количества рекурсивных вызовов для небольших файлов.

person M.J.Watson    schedule 27.02.2016