sorting - complexity - ¿Por qué el quicksort es más popular que radix-sort?

radix sort pseudocode (6)

Como se menciona en Wikipedia

El tema de la eficiencia de la ordenación de radix en comparación con otros algoritmos de clasificación es algo complicado y está sujeto a muchos 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 (pero a veces implícita) de que todas las claves son distintas, entonces d debe ser al menos del orden de log (n), que da en el mejor de los casos (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 contrario 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á 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 son aleatorias, 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.

¿Por qué el quicksort (o introsort) o cualquier algoritmo de clasificación basado en comparación es más común que radix-sort? Especialmente para ordenar números.

Radix-sort no se basa en la comparación, por lo tanto, puede ser más rápido que O (n logn). De hecho, es O (k n), donde k es el número de bits utilizados para representar cada elemento. Y la sobrecarga de la memoria no es crítica, ya que puede elegir la cantidad de cubos que se utilizarán y la memoria requerida puede ser menor que los requisitos de mergesort.

¿Tiene que ver con el almacenamiento en caché? ¿O tal vez acceder a bytes aleatorios de enteros en la matriz?

Dos argumentos vienen a mi mente:

Quicksort / Introsort es más flexible:
Quicksort e Introsort funcionan bien con todo tipo de datos. Todo lo que necesita para ordenar es la posibilidad de comparar artículos. Esto es trivial con los números pero también puedes ordenar otros datos.
Radix sort por otro lado simplemente ordena las cosas por su representación binaria. Nunca compara elementos uno contra el otro.
El ordenamiento de Radix necesita más memoria.
Todas las implementaciones de clasificación de radix que he visto usan un buffer secundario para almacenar resultados parciales de clasificación. Esto aumenta los requisitos de memoria del algoritmo de clasificación. Puede que no sea un problema si solo ordena un par de kilobytes, pero si entra en el rango de gigabytes, hace una gran diferencia.
Si recuerdo bien, existe un algoritmo de ordenamiento de radix en el papel.

Eficiencia de clasificación de Radix = O (cn) donde c = número más alto de dígitos entre la clave de entrada establecida. n = número de teclas en la configuración de la clave de entrada.

Mejor caso de clasificación rápida = O (n log n) donde n = número de teclas en la clave de entrada establecida.

Suponga que se deben ordenar 16 números con 6 dígitos cada uno:

Tipo de raíz = 16 * 6 = 96 unidades de tiempo. Clasificación rápida = 16 * 4 = 64 unidades de tiempo.

Lección: Cuando ''c'' es menor, Radix sí gana. Cuando es alto, pierde. La ordenación rápida es independiente del número de dígitos en una clave y eso la hace algo mejor y más aceptable desde el punto de vista práctico.

La clasificación de radix es más lenta para (la mayoría) de los casos de uso del mundo real.

Una razón es la complejidad del algoritmo:

Si los elementos son únicos, k> = log (n). Incluso con elementos duplicados, el conjunto de problemas donde k <log (n) es pequeño.

Otra es la implementación:

El requisito de memoria adicional (que en sí mismo es una desventaja), afecta el rendimiento de la memoria caché de forma negativa.

Creo que es seguro decir que muchas bibliotecas, como la biblioteca estándar, usan Quicksort porque funciona mejor en la mayoría de los casos. No creo que la "implementación difícil" o "menos intuitiva" sean factores importantes.

Los puntos hechos en otras respuestas son válidos, pero en cuanto a la preocupación suya mencionada en varios comentarios

... el hecho de que los algoritmos de clasificación por defecto para los números se implementan usando quicksort. Especialmente las implementaciones en bibliotecas ...

Quicksort es la opción ''segura''. El tiempo de ejecución potencial de un ordenamiento de radix basado en un tipo de recuento es muy atractivo, sí, pero el tipo de ordenación de raíz es susceptible de tener un rendimiento pobre en conjuntos de datos maliciosos / desafortunados. Si el número de dígitos de las claves que se ordenan se acerca al número de claves que se ordenan, la ordenación de radix se realiza en n ^ 2 junto con una complejidad de espacio no despreciable, y tiende a tener constantes de tiempo de ejecución compiladas bastante elevadas distintas de las del número de los dígitos de las claves que se ordenan
Mergesort es atractivo porque su comportamiento es, en cierto modo, análogo a un quicksort que elige un pivote óptimo en cada oportunidad (la mediana). Sin embargo, viene con una complejidad de espacio apreciable. No es tan susceptible a datos maliciosos / desafortunados como radix, pero tampoco ofrece el atractivo tiempo de ejecución posible. Un QuickSort básico funciona muy bien en la mayoría de los conjuntos de datos excepto casi (o completamente) clasificados, y viene con una pequeña complejidad de espacio.
La vulnerabilidad de Quicksort se resuelve fácilmente convirtiéndola en una colección rápida aleatorizada. La vulnerabilidad de Radix sort se resuelve colocando restricciones en las claves que se ordenan, lo que limitaría inherentemente a los usuarios de la biblioteca. Quicksort es más eficiente que fusionarse en pequeños conjuntos de datos, y tiene un rendimiento razonable cuando la fusión puede ser más rápida.
Al implementar una biblioteca, desea que sea genéricamente útil. Tome estos ejemplos, una aplicación web y un dispositivo pequeño con un microcontrolador extremadamente restringido. Las aplicaciones web necesitan tratar con datos maliciosos de forma regular, y también tienen una gran variedad de necesidades. Es menos probable que una biblioteca con restricciones preacondicionadas sea útil. En el caso del microcontrolador, puede estar restringido de forma restrictiva en el espacio y no puede renunciar al menor bit donde se puede guardar. Quicksort ahorra espacio, y se completará solo más lentamente con un multiplicador constante SI surge la situación de que es más lento.
En suma -
1.) Las bibliotecas a menudo se codifican para tanta usabilidad genérica como sea posible
2.) El buen rendimiento es aceptable, especialmente si es en muchos casos el mejor rendimiento
3.) El espacio no siempre es un problema principal, pero cuando lo es, a menudo es explícitamente restrictivo por lo que

Una respuesta obvia es que puede ordenar tipos arbitrarios usando quicksort (es decir, cualquier cosa que sea comparable), mientras que está restringido a números solo con radix. Y el quicksort de IMO es mucho más intuitivo.