El tema de la eficiencia de Radix sort en comparación con otros algoritmos de clasificación es un tanto complicado y sujeto a un buen montón de malentendidos.Si el tipo de radix es igual de eficiente, menos eficiente o más eficiente que los mejores algoritmos basados en la comparación depende de los detalles de las suposiciones realizadas. La eficiencia de clasificación de radix es O (d · n) para n teclas que tienen d o menos dígitos. A veces d se presenta como una constante, lo que haría que radix se clasifique mejor (para n suficientemente grande) que los mejores algoritmos de clasificación basados en la comparación, que son todos O (n · log (n)) número de comparaciones necesarias. Sin embargo, en general, d no se puede considerar una constante. En particular, bajo la suposición común (aunque a veces implícita) de que todas las claves son distintas, entonces d debe ser al menos del orden de log (n), que da como máximo (con claves densamente empaquetadas) una complejidad de tiempo O (n · Log (n)). Eso parecería hacer que la ordenación de radix sea igual de eficiente que las mejores ordenaciones basadas en la comparación (y peor si las claves son mucho más largas que log (n)).
El argumento del contador es que los algoritmos basados en la comparación se miden en el número de comparaciones, no en la complejidad del tiempo real. Según algunas suposiciones, las comparaciones serán un tiempo constante en promedio, mientras que otras no lo harán. Las comparaciones de claves generadas aleatoriamente toman un tiempo constante en promedio, ya que las claves difieren en el primer bit en la mitad de los casos, y difieren en el segundo bit en la mitad restante, y así sucesivamente, lo que da como resultado un promedio de dos bits que necesita ser comparado En un algoritmo de clasificación, las primeras comparaciones realizadas satisfacen la condición de aleatoriedad, pero a medida que avanza la clasificación, las claves comparadas ya no se eligen al azar. Por ejemplo, considere un tipo de combinación ascendente. El primer pase comparará pares de claves aleatorias, pero el último pase comparará las claves que están muy cerca en el orden de clasificación.
El factor decisivo es cómo se distribuyen las claves. El mejor caso para ordenar radix es que se toman como patrones de bits consecutivos. Esto hará que las claves sean lo más cortas posible, sin dejar de asumir que son distintas. Esto hace que radix ordene O (n · log (n)), pero los géneros basados en la comparación no serán tan eficientes, ya que las comparaciones no serán constantes bajo este supuesto. Si, en cambio, suponemos que las claves son patrones de bits de longitud k · log (n) para una constante k> 1 y base 2 log, y que son uniformemente aleatorios, entonces la ordenación de radix seguirá siendo O (n · log (n)), pero también lo harán las clases basadas en la comparación, ya que la longitud "adicional" hace que incluso las claves que son consecutivas en el resultado ordenado difieran lo suficiente como para que las comparaciones sean de tiempo constante en promedio. Si las claves son más largas que O (log (n)), pero al azar, la ordenación de radix será inferior. Hay muchas otras suposiciones que también se pueden hacer, y la mayoría requiere un estudio cuidadoso para hacer una comparación correcta.
El segundo argumento es medio incorrecto. Es cierto que la ordenación de radix necesita más memoria, pero la memoria requerida depende de la cantidad de bits que utilice en cada pasada (cantidad de segmentos). Por lo tanto, la memoria requerida puede ser menor que los requisitos de mergesort, por ejemplo. – Daniyar
El primer argumento es cierto, pero estoy más interesado por el hecho de que los algoritmos de clasificación predeterminados para los números se implementan usando quicksort. Especialmente las implementaciones en bibliotecas. Y el hecho de que el ordenamiento de radix nunca compare elementos entre sí es algo bueno, ya que de lo contrario su complejidad estaría limitada O (n * logn). – Daniyar
Es posible realizar una operación de particionamiento bidireccional estable en el tiempo de lgN con espacio constante. Por lo tanto, uno podría hacer un ordenamiento de radix en el lugar en el espacio constante con el tiempo bNlgN, donde 'b' es el número de bits de radix. – supercat