Pregunta ¿Por qué Collections.sort utiliza merge sort en lugar de quicksort? [cerrado]


Sabemos que el ordenamiento rápido es el algoritmo de clasificación más rápido.

Collectionages utilizó algoritmo de ordenación por fusión en lugar de clasificación rápida. Pero Arrays.sort usa ordenamiento rápido.

¿Cuál es la razón por la que Collections.sort utiliza el tipo de combinación en lugar de la ordenación rápida?


76
2018-03-01 09:12


origen


Respuestas:


Muy probable de Josh Bloch §:

Escribí estos métodos, así que supongo que estoy calificado para responder. Es   es cierto que no existe un único algoritmo de clasificación mejor. QuickSort tiene   dos deficiencias principales cuando se compara con mergesort:

  1. No es estable (como señaló el analizador).

  2. No lo hace garantía n log n rendimiento; puede degradarse a un rendimiento cuadrático en las entradas patológicas.

La estabilidad no es un problema para los tipos primitivos, ya que no hay ninguna noción de   identidad como distinta de (valor) igualdad. Y la posibilidad de   comportamiento cuadrático se consideró que no era un problema en la práctica para   La implementación de Bentely y McIlroy (o posteriormente para Dual Pivot   Ordenación rápida), por lo que estas variantes de QuickSort se usaron para   los géneros primitivos.

La estabilidad es un gran problema cuando se ordenan objetos arbitrarios. Por ejemplo,   supongamos que tiene objetos que representan mensajes de correo electrónico y ordena   primero por fecha, luego por remitente. Esperas que estén ordenados por   fecha dentro de cada remitente, pero eso solo será cierto si el tipo es   estable. Es por eso que elegimos proporcionar un tipo estable (Merge Sort)   para ordenar referencias de objetos (Hablando técnicamente, secuencial   los géneros estables dan como resultado un orden lexicográfico en las teclas en el   orden inverso de los géneros: el género final determina más   subclave significativa)

Es un beneficio secundario agradable que Merge Sort garantías n log n (tiempo)   rendimiento sin importar la entrada. Por supuesto, hay un inconveniente:   El ordenamiento rápido es una clasificación "en el lugar": requiere solo log n espacio externo   (para mantener la pila de llamadas). Fusionar, ordenar, por otro lado,   requiere O (n) espacio externo. La variante TimSort (presentada en Java   SE 6) requiere sustancialmente menos espacio (O (k)) si la matriz de entrada es   casi ordenado

También el siguiendo es relevante:

El algoritmo utilizado por java.util.Arrays.sort e (indirectamente) por   java.util.Collections.sort para ordenar referencias de objetos es un "modificado   mergesort (en el que la fusión se omite si el elemento más alto en el   la sublista baja es menor que el elemento más bajo en la sublista alta).   es un tipo estable razonablemente rápido que garantiza O (n log n)   rendimiento y requiere O (n) espacio extra. En su día (fue escrito   en 1997 por Joshua Bloch), fue una buena elección, pero hoy, pero podemos   hacer mucho mejor.

Desde 2003, el tipo de lista de Python ha utilizado un algoritmo conocido como timsort   (después de Tim Peters, quien lo escribió). Es un estable, adaptativo, iterativo   mergesort que requiere mucho menos que n comparaciones log (n) cuando   ejecutándose en arreglos parcialmente ordenados, mientras ofrece rendimiento   comparable a un mergesort tradicional cuando se ejecuta en matrices aleatorias. Me gusta   todos los mergesorts apropiados timsort es estable y se ejecuta en el tiempo O (n log n)   (peor de los casos). En el peor de los casos, timsort requiere almacenamiento temporal   espacio para n / 2 referencias de objetos; en el mejor de los casos, solo requiere una   pequeña cantidad constante de espacio. Contraste esto con la corriente   implementación, que siempre requiere espacio extra para n objeto   referencias, y pulsa n log n solo en listas casi ordenadas.

Timsort se describe en detalle aquí:    http://svn.python.org/projects/python/trunk/Objects/listsort.txt.

La implementación original de Tim Peters está escrita en C. Joshua Bloch   portado desde C a Java y probado, evaluado y afinado   código resultante extensivamente. El código resultante es un drop-in   reemplazo de java.util.Arrays.sort. En datos altamente ordenados, esto   El código puede ejecutarse hasta 25 veces más rápido que la implementación actual (en   la máquina virtual del servidor HotSpot). En datos aleatorios, las velocidades de lo viejo y lo nuevo   las implementaciones son comparables. Para listas muy cortas, el nuevo   la implementación es sustancialmente más rápida que la anterior, incluso al azar   datos (porque evita la copia innecesaria de datos).

Ver también ¿Está Java 7 usando Tim Sort para las matrices de métodos?.

No hay una sola "mejor" opción. Como con muchas otras cosas, se trata de compensaciones.


156
2018-03-01 09:20