La clasificación por radix es teóricamente muy rápida cuando se sabe que las claves están en un cierto rango limitado, digamos valores en el rango por ejemplo. Si simplemente convierte los valores a base que lleva tiempo , realice una clasificación de base radix y luego vuelva a convertir a su base original para obtener un algoritmo global .[ 0 … n k - 1 ] k < lg n n Θ ( n ) n Θ ( n k )
Sin embargo, he leído que, en la práctica, la ordenación de radix suele ser mucho más lenta que hacer, por ejemplo, un ordenamiento rápido aleatorio :
Para matrices grandes, la clasificación de radix tiene el recuento de instrucciones más bajo, pero debido a su rendimiento de caché relativamente pobre, su rendimiento general es peor que las versiones optimizadas de memoria de mergesort y quicksort.
¿Radix sort es solo un buen algoritmo teórico o tiene usos prácticos comunes?
fuente
vector
). Pero no lo sé, ya que no he leído los periódicos de Lamarca.@Robert: Su enlace es bastante sorprendente (en realidad no pude encontrar la oración citada). Mi experiencia personal es de entrada aleatoria, la clasificación de radix es mucho más rápida que la STL
std::sort()
, que utiliza una variante de quicksort. Solía hacer un algoritmo un 50% más rápido reemplazándolostd::sort()
por una ordenación de raíz inestable. No estoy seguro de cuál es la "versión con memoria optimizada" de quicksort, pero dudo que pueda ser el doble de rápido que la versión STL.Esta publicación de blog evaluó la clasificación de radix junto con varios otros algoritmos de clasificación. Brevemente, en esta evaluación,
std::sort()
toma 5.1 segundos ordenar 50 millones de enteros, mientras que la clasificación de radios in situ / inestable toma 2.0 segundos. La clasificación estable de radix debería ser aún más rápida.La clasificación por radix también se usa ampliamente para clasificar cadenas de forma estable. A veces se ven variantes de clasificación de radix para construir matrices de sufijos, BWT, etc.
fuente
La clasificación por radix también es una forma natural de ordenar palabras de longitud fija sobre un alfabeto fijo, por ejemplo, en el algoritmo Kärkkäinen & Sanders ( http://www.cs.cmu.edu/~guyb/realworld/papersS04/KaSa03.pdf )
fuente