sorting algorithms java

Comparación entre timsort y quicksort

Question

¿Por qué es que escucho principalmente que el quicksort es el algoritmo de clasificación global más rápido cuando el timsort (de acuerdo con la wikipedia) parece funcionar mucho mejor? Google no pareció mostrar ningún tipo de comparación.

Answer 1

Aquí hay números de referencia de mi máquina (i7-6700 CPU, 3.4GHz, Ubuntu 16.04, gcc 5.4.0, parámetros: SIZE = 100000 y RUNS = 3):

$ ./demo 
Running tests
stdlib qsort time:                 12246.33 us per iteration
##quick sort time:                  5822.00 us per iteration
merge sort time:                    8244.33 us per iteration
...    
##tim sort time:                    7695.33 us per iteration
in-place merge sort time:           6788.00 us per iteration    
sqrt sort time:                     7289.33 us per iteration    
...
grail sort dyn buffer sort time:    7856.67 us per iteration

El punto de referencia proviene del proyecto de sort de Swenson en el que implementó varios algoritmos de clasificación en C. Presumiblemente , sus implementaciones son lo suficientemente buenas como para ser representativas, pero no las he investigado.

Entonces realmente no puedes decir. Los números de referencia solo son relevantes durante un máximo de dos años y luego debe repetirlos. Posiblemente, timsort venció qsort waaay en 2011 cuando se formuló la pregunta, pero los tiempos han cambiado. O qsort siempre fue el más rápido, pero timsort lo superó con datos no aleatorios. O el código de Swenson no es tan bueno y un programador mejor cambiaría la tendencia a favor de timsort. O tal vez yo chupo y no CFLAGS los CFLAGS correctos al compilar el código. O ... Entiendes el punto.

Answer 2

En general, el quicksort es el mejor algoritmo para la matriz primitiva. Esto se debe a la localidad de memoria y al caché.

JDK7 usa TimSort para matriz de objetos. La matriz de objetos solo contiene la referencia del objeto. El objeto en sí se almacena en Heap. Para comparar el objeto, necesitamos leer el objeto del montón. Esto es como leer de una parte del montón para un objeto, luego leer al azar el objeto de otra parte del montón. Habrá una gran cantidad de errores de caché. Supongo que por esta razón la localidad de memoria ya no es importante. Esta puede ser la razón por la cual JDK solo utiliza TimSort para matriz de objetos en lugar de matriz primitiva.

Esta es solo mi suposición.

Answer 3

Más o menos, tiene que ver con el hecho de que Timsort es un algoritmo de clasificación híbrido. Esto significa que, si bien los dos tipos subyacentes que utiliza (clasificación Mergesort e Insertion) son peores que Quicksort para muchos tipos de datos, Timsort solo los usa cuando es ventajoso hacerlo.

En un nivel ligeramente más profundo, como dice Patrick87 , el quicksort es el algoritmo O (n ² ) del peor de los casos. Elegir un buen pivote no es hard , pero garantizar un servicio rápido de O (n log n) tiene como resultado una clasificación generalmente más lenta en promedio.

Para obtener más detalles sobre Timsort, consulte esta respuesta y la publicación de blog vinculada. Básicamente, asume que la mayoría de los datos ya están parcialmente ordenados, y construye "corridas" de datos ordenados que permiten fusiones eficientes utilizando mergesort.

Answer 4

No puedo usar la ordenación estándar de Java en las competencias de programación de las fuerzas de código, porque Java usa el enlace rápido de doble pivote para las matrices de números enteros y dobles, por lo que existen las matrices que requieren O (n ^ 2) tiempo para ejecutarse. Y algunos datos de prueba a menudo se componen con estas matrices, por lo que el programa tarda demasiado tiempo y falla. Así que tengo que cambiar a mi propia mergeSort en su lugar. No puede suceder con el algoritmo timsort.

Answer 5

TimSort es un mergesort de alta optimización, es estable y más rápido que el viejo mergesort.

cuando se compara con quicksort, tiene dos ventajas:

1. Es increíblemente rápido para la secuencia de datos casi ordenados (incluidos los datos ordenados inversos);
2. El peor caso sigue siendo O (N * LOG (N)).

Para ser sincero, no creo que el # 1 sea una ventaja, pero sí me impresionó.

Aquí están las ventajas de QuickSort

1. QuickSort es muy simple, incluso una implementación altamente ajustada, podemos escribir sus códigos pseduo en 20 líneas;
2. QuickSort es el más rápido en la mayoría de los casos;
3. El consumo de memoria es LOG (N).

Actualmente, Java 7 SDK implementa timsort y una nueva variante de quicksort: es decir, Dual Pivot QuickSort.

Si necesita una ordenación estable, intente con timsort, de lo contrario comience con la ruta rápida.