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

121

El Arrays.sortmétodo de Java 6 utiliza Quicksort para matrices de primitivas y fusionar ordenación para matrices de objetos. Creo que la mayoría de las veces la ordenación rápida es más rápida que la ordenación combinada y cuesta menos memoria. Mis experimentos apoyan eso, aunque ambos algoritmos son O (n log (n)). Entonces, ¿por qué se utilizan diferentes algoritmos para diferentes tipos?

zjffdu
fuente
14
El peor caso de Quicksort es N ^ 2 no NlogN.
codaddict
Espera, ¿qué pasa si tienes una matriz de Integerso algo?
Tikhon Jelvis
1
¿No se explica esto en la fuente que leíste?
Humphrey Bogart
5
Esta información ya no está actualizada. A partir de Java SE 7, MergeSort ha sido reemplazado por TimSort y QuickSort ha sido reemplazado por Dual-Pivot QuickSort . Consulte mi respuesta a continuación para obtener enlaces a los documentos de la API de Java.
Will Byrne
Consulte también stackoverflow.com/questions/15154158/… y para JDK 7+ consulte stackoverflow.com/questions/32334319/…
rogerdpack

Respuestas:

200

La razón más probable: la clasificación rápida no es estable , es decir, las entradas iguales pueden cambiar su posición relativa durante la clasificación; Entre otras cosas, esto significa que si ordena una matriz ya ordenada, es posible que no permanezca sin cambios.

Dado que los tipos primitivos no tienen identidad (no hay forma de distinguir dos ints con el mismo valor), esto no les importa. Pero para los tipos de referencia, podría causar problemas para algunas aplicaciones. Por lo tanto, se utiliza una clasificación de combinación estable para esos.

OTOH, una razón para no usar el tipo de fusión estable (n * log (n) garantizado) 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 de la matriz duplica el uso de memoria.

Michael Borgwardt
fuente
1
Otra razón para usar la ordenación rápida es que en el caso promedio, la ordenación rápida es más rápida que la ordenación combinada. Aunque quicksort hace más comparaciones que mergesort, tiene muchos menos accesos a la matriz. La ordenación rápida 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 (supongo que la ordenación rápida de doble pivote también tiene esta propiedad).
Jingguo Yao
Para los tipos primitivos que no clona la matriz, se puede ordenar en su lugar, así que creo que la única razón es el contrato de estabilidad, básicamente ...
rogerdpack
27

De acuerdo con los documentos de la API de Java 7 citados en esta respuesta , Arrays#Sort()para las matrices de objetos ahora se usa TimSort , que es un híbrido de MergeSort e InsertionSort. Por otro lado, Arrays#sort()para las matrices primitivas ahora se usa Dual-Pivot QuickSort . Estos cambios se implementaron a partir de Java SE 7.

Will Byrne
fuente
2
No es una respuesta, por qué se han elegido 2 algoritmos diferentes.
Alexandr
12

Una razón en la que puedo pensar es que quicksort tiene una complejidad de tiempo en el peor de los casos de O ( n ^ 2 ) mientras que mergesort retiene el tiempo del peor de los casos de O ( n log n ). Para las matrices de objetos, existe una expectativa razonable de que habrá múltiples referencias de objetos duplicadas, que es un caso en el que el ordenamiento rápido funciona peor.

Hay una comparación visual decente de varios algoritmos , preste especial atención al gráfico de la derecha para diferentes algoritmos.

msw
fuente
2
La clasificación rápida de Java es una clasificación rápida modificada que no se degrada a O (n ^ 2), de los documentos "Este algoritmo ofrece un rendimiento n * log (n) en muchos conjuntos de datos que hacen que otras
clasificaciones rápidas se
7

Estaba tomando la clase de Coursera sobre algoritmos y en una de las conferencias, el profesor Bob Sedgewick mencionaba la evaluación para el sistema Java:

"Si un programador está usando objetos, tal vez el espacio no sea una consideración de importancia crítica y el espacio adicional usado por un tipo de combinación tal vez no sea un problema. Y si un programador está usando tipos primitivos, tal vez el rendimiento sea lo más importante, por lo que usan ordenación rápida."

kukido
fuente
4
No es la principal razón. Inmediatamente después de esa oración había una pregunta incrustada en el video sobre "¿Por qué para los tipos de referencia se usa MergeSort?" (porque es estable). Creo que Sedgewick no mencionó eso en el video para dejarlo en duda.
likern
1

java.util.Arrays usa quicksort para tipos primitivos como int y mergesort para objetos que implementan Comparable o usan un Comparator . La idea de usar dos métodos diferentes es que si un programador usa objetos, tal vez el espacio no sea una consideración de importancia crítica y, por lo tanto, el espacio adicional usado por mergesort tal vez no sea un problema y si el programador usa tipos primitivos, tal vez el rendimiento sea lo más importante, así que use la clasificación rápida .

Por ejemplo: este es el ejemplo cuando la clasificación de la estabilidad es importante.

ingrese la descripción de la imagen aquí

Es por eso que los tipos estables tienen sentido para los tipos de objetos, especialmente los tipos de objetos mutables y los tipos de objetos con más datos que solo la clave de clasificación, y mergesort es un tipo de ese tipo. Pero para los tipos primitivos, la estabilidad no solo es irrelevante. No tiene sentido.

Fuente: INFO

Dinesh Kumar
fuente
0

El Arrays.sortmétodo de Java utiliza clasificación rápida, clasificación por inserción y clasificación por fusión. Incluso hay una ordenación rápida de pivote simple y doble implementada en el código OpenJDK. El algoritmo de ordenación más rápido depende de las circunstancias y los ganadores son: ordenación por inserción para arreglos pequeños (47 elegidos actualmente), ordenación por fusión para arreglos en su mayoría ordenados y ordenamiento rápido para los arreglos restantes para que Array.sort () de Java intente elegir el mejor algoritmo para aplicar en base a esos criterios.

David McManamon
fuente