Выбор Radix: версии LSD и MSD

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

Ответ 1

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

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

Ответ 2

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

Ответ 3

Как читается в книге Алгоритмы, 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.