¿Por qué el método Arrays.sort de Java utiliza dos algoritmos de clasificación diferentes para diferentes tipos?

El método Arrays.sort de Java usa Quicksort para matrices de primitivas y ordenación por fusión para matrices de objetos. Creo que la mayoría de las veces Quicksort es más rápido que fusionar y cuesta menos memoria. Mis experimentos respaldan eso, aunque ambos algoritmos son O (n log (n)). Entonces, ¿por qué se utilizan diferentes algoritmos para diferentes tipos?¿Por qué el método Arrays.sort de Java utiliza dos algoritmos de clasificación diferentes para diferentes tipos?

Fuente

2010-09-14 zjffdu

+11

El peor caso de Quicksort es N^2 no NlogN. – codaddict

Espera, ¿qué ocurre si tienes una matriz de 'Entero' o algo así? –

¿No se explica esto * en * la fuente que leyó? –

146

La razón más probable: quicksort no es estable, es decir, las entradas iguales pueden cambiar su posición relativa durante el ordenamiento; entre otras cosas, esto significa que si ordena una matriz ya ordenada, puede que no permanezca sin cambios.

Como los tipos primitivos no tienen identidad (no hay manera de distinguir dos entradas con el mismo valor), esto no tiene importancia para ellos. Pero para los tipos de referencia, podría causar problemas para algunas aplicaciones. Por lo tanto, se usa un tipo de combinación estable para esos.

OTOH, una razón para no usar el tipo de fusión (garantizado n * log (n)) para los tipos primitivos podría ser que requiere hacer una copia de la matriz. Para los tipos de referencia, donde los objetos referidos usualmente ocupan mucha más memoria que la matriz de referencias, esto generalmente no importa. Pero para los tipos primitivos, la clonación completa de la matriz duplica el uso de la memoria.

Fuente

2010-09-14 08:33:18

Otra razón para usar quicksort es que en el caso promedio, quicksort es más rápido que mergesort. Aunque quicksort hace más se compara que mergesort, hace mucho menos accesos a la matriz. El modo quicksort de 3 vías también puede lograr un tiempo lineal si la entrada contiene muchas entradas duplicadas, lo cual no es inusual en aplicaciones prácticas (mi suposición es que la ordenación rápida de doble pivote también tiene esta propiedad). –

Una razón que se me ocurre es que tiene una clasificación rápida peor caso complejidad del tiempo de O (n^2 ), mientras que conserva mergesort peor caso el tiempo de O (n log n ). Para las matrices de objetos hay una expectativa justa de que habrá varias referencias de objetos duplicados, que es un caso en el que la ordenación rápida funciona peor.

Hay un número decente visual comparison of various algorithms, preste especial atención al gráfico de la derecha para diferentes algoritmos.

Fuente

2010-09-14 08:33:36 msw

+1 para mi sitio favorito en Internet por hoy. –

El quicksort java es un quicksort modificado que no descifra O (n^2), de los documentos "Este algoritmo ofrece el rendimiento n * log (n) en muchos conjuntos de datos que hacen que otros quicksorts se degraden al rendimiento cuadrático" – sbridges

" En muchos conjuntos de datos "no es lo mismo que" en todos "... – Puce

que estaba tomando clases Coursera sobre algoritmos y en una de las conferencias el profesor Bob Sedgewick mencionan la evaluación para el sistema de Java para ordenar:

"Si un programador está utilizando objetos, puede que el espacio no es una crítica importante la consideración y el espacio extra utilizado por un tipo de fusión tal vez no es un problema. Y si un programador está utilizando tipos primitivos, tal vez el rendimiento es lo más importante, por lo que utilizan el ordenamiento rápido ".

Fuente

2014-02-20 19:16:54 kukido

No es la razón principal. Justo después de esa frase había una pregunta, incrustada en el video sobre "¿Por qué para los tipos de referencia se utiliza MergeSort?" (porque es estable). Creo que Sedgewick no mencionó eso en video para dejarlo en cuestión. – likern

Según Java docs 7 API citadas en this answer, Arrays#Sort() para matrices de objetos ahora utiliza TimSort, que es un híbrido de mergesort y InsertionSort. Por otro lado, Arrays#sort() para matrices primitivas ahora usa Dual-Pivot QuickSort. Estos cambios se implementaron comenzando en Java SE 7.

Fuente

2015-05-08 05:48:26

El método de Java Arrays.sort usa quicksort, insertion sort y mergesort. Incluso hay un quicksort de pivote único y doble implementado en el código OpenJDK. El algoritmo de clasificación más rápido depende de las circunstancias y los ganadores son: clasificación de inserción para matrices pequeñas (47 elegidas actualmente), mergesort para matrices ordenadas en su mayoría y quicksort para las matrices restantes, por lo que Array.sort() de Java intenta elegir el mejor algoritmo para aplicar basado en esos criterios.

Fuente

2017-11-23 16:14:00

¿Por qué el método Arrays.sort de Java utiliza dos algoritmos de clasificación diferentes para diferentes tipos?

Respuesta

Cuestiones relacionadas