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?
Respuesta
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.
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.
+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 ".
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.
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.
- 1. ¿Qué diferentes algoritmos de clasificación están disponibles en Java 6?
- 2. set_intersection para dos tipos diferentes de conjuntos
- 3. ¿Por qué diferentes tipos de puntero para diferentes tipos de datos en c?
- 4. Java: Arrays.sort clasificación rápida y mergesort
- 5. ¿Utiliza enums de Java de diferentes clases?
- 6. ¿Por qué gdb muestra dos resultados diferentes?
- 7. ¿Lista de diferentes tipos?
- 8. ¿por qué diferentes respuestas?
- 9. Ordene diferentes grupos utilizando diferentes órdenes de clasificación en solr
- 10. ¿Qué algoritmo de clasificación utiliza el método Array.Sort() de .NET?
- 11. Seguimiento de dos tipos de usuarios diferentes con Google Analytics?
- 12. Los diferentes tipos de propuestas de terminación de Java Eclipse
- 13. ¿Los miembros estáticos de una clase genérica son diferentes para diferentes tipos en Java?
- 14. Terminología para diferentes tipos de funciones
- 15. ¿Por qué diferentes etags para diferentes representaciones del mismo recurso?
- 16. Diferentes métodos de Java para diferentes niveles de API
- 17. ¿Para qué sirven los diferentes tipos de muestras HLSL?
- 18. ¿Pueden dos métodos Java tener el mismo nombre con diferentes tipos de devolución?
- 19. Concatenación de dos listas de diferentes tipos con LINQ
- 20. Cómo usar Java Arrays.sort
- 21. Diferencia de dos listas con diferentes tipos usando LINQ
- 22. Linq: excepto en dos tipos diferentes de diccionarios
- 23. ¿Por qué estos dos ejemplos de código producen salidas diferentes?
- 24. ¿Por qué las direcciones de dos objetos diferentes deberían ser diferentes?
- 25. matriz bidimensional de diferentes tipos
- 26. .Net Consuming Web Service: tipos idénticos en dos servicios diferentes
- 27. Unir dos variables IQueryable de diferentes tipos utilizando LINQ
- 28. ¿Por qué el mismo valor de DateTime arrojaría diferentes horas de visualización para diferentes usuarios?
- 29. Django - Perfiles de usuario de diferentes tipos
- 30. ¿Por qué Arrays.sort toma Object [] en lugar de Comparable []?
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ó? –