algorithm - cormen - radix sort geek
Tipo de radix: versiones LSD versus MSD (3)
El libro "Introducción a los algoritmos" menciona la versión LSD (dígito menos significativo) de la clase de radix. Sin embargo, como otros han señalado aquí en stackoverflow, también existe una versión de MSD (Dígito más significativo). Así que quiero saber los pros y los contras de cada uno de estos. Supongo que la versión de LSD tiene algunos beneficios sobre el de MSD, pero no estoy seguro. De ahí la pregunta.
Como se lee en el libro Algorithms , LSD y MSD son algoritmos de ordenación de matriz de cadenas, basados en el llamado conteo indexado de claves en lugar de en comparaciones. Por lo tanto, LSD y MSD tienen un tiempo de ejecución diferente en comparación con la ordenación rápida tradicional o la ordenación por fusión.
Como mencionó Dzhabarov, la mayor diferencia entre LSD y MSD es que MSD considera primero el dígito o carácter más significativo, que por naturaleza ordena las cadenas sin iterar a través de todos los dígitos de las cadenas. Esta es una ventaja. Sin embargo, una implementación recursiva de MSD usa más espacio que LSD.
La siguiente tabla ilustra partes de la diferencia entre la ordenación rápida, LSD y MSD.
algorithm running time extra space
quicksort N(lgN)^2 1
LSD NW N
MSD between N and NW N + WR
donde N es la longitud de la matriz, y W es la longitud de la cadena, y R es el tamaño de la raíz.
PD: como se menciona en el libro, la clasificación del sistema Java utiliza un algoritmo de clasificación general con una rápida comparación de cadenas y no LSD o MSD.
LSD es más rápido que MSD cuando hay una longitud fija. MSD es demasiado lento para archivos pequeños y necesita una gran cantidad de llamadas recursivas en archivos pequeños.
Tomado del enlace, podría ser útil: http://www.eternallyconfuzzled.com/tuts/algorithms/jsw_tut_sorting.aspx (en la parte inferior)
El mayor problema con la clasificación de radix LSD es que comienza en los dígitos que hacen la menor diferencia. Si pudiéramos comenzar con los dígitos más significativos, la primera pasada sería de gran ayuda para clasificar todo el rango, y cada pasada después de eso simplemente manejaría los detalles. La idea de la clasificación de MSD radix es dividir todos los dígitos con un valor igual en su propio grupo, y luego hacer lo mismo con todos los grupos hasta que se clasifique la matriz. Naturalmente, esto sugiere un algoritmo recursivo, pero también significa que ahora podemos ordenar los elementos de longitud variable y no tenemos que tocar todos los dígitos para obtener una matriz ordenada. Esto hace que la clasificación de MSD radix sea considerablemente más rápida y más útil.