Timsort explicado

TimSort es un algoritmo de clasificación que combina clasificación por fusión y clasificación por inserción, y en realidad tiene buena eficiencia. Tim Peters diseñó este algoritmo en 2002 y lo usó en Python (la implementación predeterminada de list.sort en Python). Python usa el algoritmo Timsort para ordenar a partir de la versión 2.3, y ahora Java SE7 y Android también usan el algoritmo Timsort para ordenar matrices.

Directorio

1 Operación

2 Rendimiento

3 Código fuente JDK

Proceso central de Timsort

p>

Para minimizar la retroalimentación de la parte ascendente y la degradación del rendimiento de la parte descendente, el algoritmo TimSort divide y clasifica la entrada según sus características ascendentes y descendentes. Cada fusión combina dos ejecuciones en una. El resultado combinado se guarda en la pila. La fusión continúa hasta que se agotan todas las ejecuciones, momento en el cual las ejecuciones restantes en la pila se fusionan hasta que solo queda una ejecución. Esta ejecución restante es el resultado ordenado.

En resumen, el algoritmo Timsort incluye

(0) Cómo hacer que la longitud de la matriz sea menor que un cierto valor y usar directamente el algoritmo de clasificación por inserción binaria

(1) Encuentre cada ejecución y combínelas en la pila

(2) Encuentre ejecuciones y combínelas en la pila. Apilar

(2) Fusionar y ejecutar según las reglas

1 operación

En realidad, la mayoría de los datos suelen estar parcialmente ordenados y Timsort aprovecha esta característica. En lugar de clasificar las unidades de entrada en números individuales, Timsort las clasifica en particiones. Cada partición se denomina "ejecución" (Figura 1). Para esta secuencia de ejecuciones, se elimina y fusiona una ejecución a la vez. timesor separa cada ejecución en orden ascendente y descendente: si la ejecución es ascendente, el siguiente elemento de la ejecución debe ser mayor o igual que el elemento anterior (a[lo]lt; = a[lo 1]lt; = a[ lo 2 ] lt; = .........); Si la ejecución es en orden ascendente, entonces el siguiente elemento de la ejecución debe ser mayor o igual que el elemento anterior (a [lo] lt; = a [lo 1] lt; = a [lo 1] lt; = a [lo 1] lt = ...); (a [lo] gt; a [ lo 1]gt; a [lo 2]gt; ... Si desea voltear los elementos en ejecución (tenga en cuenta que la parte descendente debe ser en orden descendente "estricto" para voltear), entonces debe invertir los elementos en ejecución (la parte descendente debe ser "Estrictamente" en orden descendente, esto se debe a que un objetivo importante de TimSort es mantener la estabilidad. Si se invierte en este caso, el algoritmo se volverá inestable).

1.1 Longitud mínima de las ejecuciones

Las ejecuciones son fragmentos ordenados de particiones. Las ejecuciones pueden tener diferentes longitudes y Timesort elige una estrategia de clasificación basada en la duración de la ejecución. Por ejemplo, si la duración de la ejecución es inferior a un determinado valor, se elige el algoritmo de clasificación por inserción para la clasificación. La longitud mínima de la ejecución (minrun) depende del tamaño de la matriz. Cuando la matriz tiene menos de 64 elementos, minrun es la longitud de la matriz, ordenada por Timsort utilizando el algoritmo de clasificación por inserción. Cuando la matriz tiene 63 o más elementos, se elige un número llamado minrun de 32 a 65 para matrices más grandes, de modo que el tamaño de la matriz dividido por el tamaño mínimo de ejecución sea igual o ligeramente menor que una potencia de 2.

El algoritmo final solo toma los 6 bits significativos más altos del tamaño de la matriz, agrega uno si los bits restantes están configurados y proporciona el resultado como una ejecución mínima. Este algoritmo funciona en todos los casos, incluidos los tamaños de matriz inferiores a 64.

Según la teoría de la información, la velocidad promedio de clasificación por comparación no excederá O (n log n). Dado que el algoritmo Timsort aprovecha el hecho de que, en realidad, hay algunas áreas de clasificación en la mayoría de los datos, Timsort será más rápido que

O Para números aleatorios que no tienen un área de clasificación disponible, Timsort La complejidad temporal de será log(n!). La siguiente tabla compara la complejidad del tiempo (complejidad del tiempo) de Timsort y otros algoritmos de clasificación de comparación.