¿Por qué la clasificación rápida es más popular que el radix-tipo?

Question

¿Por qué la clasificación rápida (o introsort), o cualquier algoritmo de ordenación basada en la comparación es más común que el radix-tipo? Especialmente para los números de clasificación.

Radix-tipo no es comparación basada, 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 el número de cubos para su uso, y la memoria requerida puede ser inferior a los requisitos de la ordenación por fusión.

¿Tiene que ver con el caché? O tal vez para acceder a los bytes aleatorios de números enteros en la matriz?

Answer 1

Dos argumentos vienen a la mente:

1. Quicksort / Introsort es más flexible:

   ordenación rápida y Introsort funcionan bien con todo tipo de datos. Todo lo que necesita para la clasificación es la posibilidad de comparar los productos. Esto es trivial con los números, pero se puede ordenar también otros datos.

   Radix sort por el contrario simplemente ordena las cosas por su representación binaria. Nunca se compara elementos uno contra el otro.

2. Radix necesita especie más memoria.

   Todas las implementaciones Radix sort que he visto el uso de un segundo búfer para almacenar resultados parciales de clasificación. Esto aumenta los requisitos de memoria del algoritmo de ordenación. Eso no puede ser un problema si única clase un par de kilobytes, pero si usted entra en el rango de gigabytes que hace una gran diferencia.

   Si no recuerdo un derecho en su lugar existen algoritmo radix-tipo en el papel sin embargo.

Answer 2

Una respuesta obvia es que pueda tipos arbitrarios tipo utilizando la clasificación rápida (es decir, todo lo que es comparable), mientras que se limitan a los números sólo con la raíz. Y la OMI ordenación rápida es mucho más intuitivo.

Answer 3

Radix sort es más lento para (la mayoría) los casos de uso del mundo real.

Una de las razones es la complejidad del algoritmo:

Si los artículos son únicos, k> = log (n). Incluso con los elementos duplicados, el conjunto de problemas donde k

Otra es la aplicación:

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

creo que es seguro decir que muchas bibliotecas, como la biblioteca estándar, utilice la ordenación rápida, ya que tiene un mejor rendimiento en la mayoría de los casos. No creo que "difícil aplicación" o "menos intuitivo" son factores importantes.

Answer 4

Como se ha mencionado en Wikipedia

  

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. Ya sea Radix sort es igualmente eficiente, menos eficiente o más eficiente que los mejores algoritmos basados ??en la comparación depende de los detalles de las suposiciones hechas. eficiencia especie 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 Radix sort mejor (para n suficientemente grande) que los mejores algoritmos de clasificación basados ??en la comparación, que son todos O (n · (n) log) número de comparaciones necesarias. Sin embargo, en general d no puede considerarse una constante. En particular, bajo el común (pero a veces implícita) de que todas las claves son distintos, entonces D debe ser al menos del orden de log (n), lo que da en el mejor (con teclas densamente empaquetadas) una complejidad O tiempo (n · log (n)) . Eso parecería que Radix sort como máximo igual de eficiente como el mejor tipo a base de comparación (y peor si las claves son mucho más largas que log (n)).

     

El argumento en contra es los algoritmos basados ??en la comparación se miden en número de comparaciones, no complejidad en tiempo real. Bajo ciertas suposiciones las comparaciones serán constante de tiempo de media, bajo otras no lo harán. Las comparaciones de las claves generadas aleatoriamente lleva tiempo constante en promedio, como teclas difieren en el primer bit en la mitad de los casos, y se diferencian en el segundo bit en la mitad de la mitad restante, y así sucesivamente, lo que resulta en un promedio de dos bits que que compararse. En un algoritmo de ordenación de las primeras comparaciones hechas satisface la condición de aleatoriedad, pero a medida que avanza el tipo de las teclas en comparación claramente no son elegidos al azar más. Por ejemplo, considere una combinación de abajo hacia arriba tipo. El primer paso será comparar pares de claves aleatorias, pero el último pase comparará teclas que están muy cerca en el orden de clasificación.

     

El factor decisivo es cómo se distribuyen las llaves. El mejor caso para Radix sort es que se toman como patrones de bits consecutivos. Esto hará que las teclas tan corto como pueden ser, aún suponiendo que son distintos. Esto hace Radix sort O (n · log (n)), pero el tipo de comparación basados ??no será tan eficiente, ya que las comparaciones no serán constante de tiempo bajo este supuesto. Si en lugar de asumir que las claves son patrones de bits de longitud k · log (n) para una constante k> 1 y la base 2 de registro, y que son uniformemente aleatorio, entonces radix tipo todavía será O (n · log (n) ), pero también lo hará el tipo de comparación basados, como la longitud "extra" hace que incluso las claves que son consecutivos en el resultado ordenado diferir suficiente que las comparaciones son la constante de tiempo de media. Si las claves son más largas que O (log (n)), pero al azar, a continuación, Radix sort será inferior. Hay muchos otros supuestos que se pueden hacer también, y la mayoría requieren un cuidadoso estudio para hacer una comparación correcta.

Answer 5

Puntos hechas en otras respuestas son válidas, pero por lo que la preocupación de los suyos se mencionan en varios comentarios

  

... el hecho de que el valor por defecto algoritmos de ordenación para los números se implementan utilizando la clasificación rápida. Especialmente las implementaciones en las bibliotecas ...

ordenación rápida es la opción 'segura'. El tiempo de ejecución potencial de una especie radix basado en una especie de recuento es muy atractivo, sí, pero Radix sort es subsceptible a un mal desempeño en conjuntos de datos maliciosos / desafortunado. Si el número de dígitos de las teclas están ordenados se acerca al número de teclas sea clasificado, realiza Radix sort en n ^ 2, junto con una complejidad espacio no despreciable, y que tiende a tener constantes de tiempo de ejecución bastante alto interno que no sea el de la serie de dígitos de las teclas están ordenados.
Mergesort es atractivo debido a que su comportamiento es, en cierto modo, análogo a una clasificación rápida que recoge un giro óptimo en cada oportunidad (la mediana). Sin embargo, viene con una complejidad espacio apreciable. No es tan subsceptible a los datos maliciosos / desafortunadas como base, sino también no ofrece el tiempo de ejecución atractiva posible. A realiza básicos quicksort muy bien en la mayoría de los conjuntos de datos, excepto casi (o totalmente) ordenados queridos, y viene con un pequeño espacio complejidad.
La vulnerabilidad de la ordenación rápida es fácil de tratar mediante la conversión a una clasificación rápida aleatorizado. La vulnerabilidad de Radix sort se resuelve mediante la colocación de las restricciones sobre las teclas están ordenados, lo que inherentemente limitar a los usuarios de la biblioteca. Ordenación rápida es más rendimiento inferior de mezcla en pequeños conjuntos de datos, y realiza razonablemente cuando fusión podría ser más rápido.
Al implementar una biblioteca, que desea que sea genéricamente útil. Tome estos ejemplos, una aplicación web y un pequeño dispositivo con un microcontrolador muy restringida. Las aplicaciones web tienen que tratar con datos maliciosos de forma regular, y también tienen una amplia variedad de necesidades. Una biblioteca con las restricciones previamente acondicionados es menos probable que sea útil. En el caso del microcontrolador, que puede ser restrictiva limitada en el espacio y no puede renunciar a la menor parte en la que uno puede ser salvo. Ordenación rápida ahorra espacio, y sólo se completará más lento por un multiplicador constante si surge una situación que es más lento.
En suma -
1.) Las bibliotecas a menudo se codifican por tanto la facilidad de uso genérico posible
2.) El buen desempeño en todo es aceptable, especialmente si es en muchos casos, el mejor rendimiento
3.) El espacio no es siempre un tema principal, pero cuando lo es, a menudo es tan restrictiva explícitamente

Answer 6

eficiencia = de Radix tipo O (c.n) donde c = el más alto número de dígitos entre el conjunto de claves de entrada. n = número de llaves en conjunto de teclas de entrada.

mejor de los casos de Quick sort = O (n. Log n) donde n = número de llaves en conjunto de teclas de entrada.

Suponga 16 números a clasificar con 6 dígitos cada uno:

Radix = Ordenar 16 unidades * 6 = 96 tiempo. Quick sort = 16 * 4 = 64 unidades de tiempo.

lección: Cuando 'c' es menor, Radix no ganar. Cuando es alta, pierde. Quick Sort es independiente del número de dígitos de una llave y eso hace que sea un poco mejor y más prácticamente aceptable