java - por - metodos de ordenamiento estructura de datos
¿Por qué el método Arrays.sort de Java utiliza dos algoritmos de clasificación diferentes para diferentes tipos? (5)
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?
El método Arrays.sort de Java 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.
Estaba tomando una clase de Coursera en Algoritmos y en una de las conferencias el Profesor Bob Sedgewick mencionó la evaluación para el sistema Java:
"Si un programador usa objetos, tal vez el espacio no es una consideración críticamente importante y el espacio extra utilizado por una fusión puede no ser un problema. Y si un programador usa tipos primitivos, tal vez el rendimiento sea lo más importante para que lo use ordenación rápida."
La razón más probable: el quicksort no es estable , es decir, las entradas iguales pueden cambiar su posición relativa durante el género; 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 tipos primitivos podría ser que requiere hacer un clon 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.
Según los documentos API de Java 7 citados en esta respuesta , Arrays#Sort() para matrices de objetos ahora usa TimSort , que es un híbrido de MergeSort e InsertionSort. Por otro lado, Arrays#sort() para matrices primitivas ahora usa Dual-Pivot QuickSort . Estos cambios se implementaron comenzando en Java SE 7.
Una razón por la que puedo pensar es que quicksort tiene una peor complejidad de tiempo de O ( n ^ 2 ) mientras que mergesort conserva el peor 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 una comparación visual decente de varios algoritmos , preste especial atención al gráfico más a la derecha para diferentes algoritmos.