Timsort

Paso 1. Dividir en subarreglos y ordenarlos.

• El puntero del elemento actual se coloca al principio de la matriz de entrada.
• Comenzando en el elemento actual, se busca en este arreglo la corrida ordenada del subarreglo. Por definición, ejecutar incluirá únicamente el elemento actual y el siguiente. Si el subarreglo resultante se ordena en orden descendente, los elementos se reorganizan para que vayan en orden ascendente.
• Si el tamaño de la ejecución actual es menor que minrun, los elementos que siguen a la ejecución encontrada se seleccionan en la cantidad de minrun-size (ejecución). Por lo tanto, la salida será un subarreglo de tamaño minrun o más, parte del cual (e idealmente todo) está ordenado.
• La ordenación por inserción se aplica a este subarreglo. Dado que el tamaño del subarreglo es pequeño y parte de él ya está ordenado, la clasificación es rápida y eficiente.
• El puntero del elemento actual se coloca en el elemento que sigue al subarreglo.
• Si no se alcanza el final de la matriz de entrada, vaya al paso 2; de lo contrario, finalice este paso.

Paso 2. Combinar.

Si los datos de la matriz de entrada eran casi aleatorios, entonces el tamaño de los subarreglos ordenados está cerca de minrun; si los datos contenían rangos ordenados, los subarreglos ordenados tienen un tamaño mayor que minrun.

Necesitamos fusionar estos subarreglos para obtener el arreglo resultante completamente ordenado. Para ser efectiva, una asociación debe cumplir con dos requisitos:

• Combinar subarreglos de aproximadamente el mismo tamaño
• Mantenga la estabilidad del algoritmo, es decir, no haga permutaciones sin sentido.

Algoritmo:

• Se crea una pila vacía de pares <subarray start index>-<subarray size>. Se toma el primer subarreglo ordenado.
• El par de datos <índice de inicio>-<tamaño> para el subarreglo actual se agrega a la pila.
• Se determina si es necesario fusionar el subarreglo actual con los anteriores. Para hacer esto, se verifican dos reglas (sean X, Y y Z los tamaños de los tres primeros subarreglos de la pila):

• Si se viola una de las reglas, la matriz Y se fusiona con la más pequeña de las matrices X y Z. Se repite hasta que se cumplen ambas reglas o los datos están completamente ordenados.
• Si todavía quedan subarreglos sin considerar, se toma el siguiente y se pasa al paso 2. De lo contrario, fin.

El propósito de este procedimiento es mantener el equilibrio. Los cambios se verán como en la imagen de la derecha, lo que significa que los tamaños de los subarreglos en la pila son efectivos para una ordenación por combinación adicional. En el caso ideal: hay subarreglos de tamaño 128, 64, 32, 16, 8, 4, 2, 2. En este caso, no se realizarán fusiones hasta que se encuentren los últimos 2 subarreglos, después de lo cual se realizarán 7 fusiones perfectamente equilibradas. realizado.

Procedimiento para fusionar subarreglos

El procedimiento de fusión atraviesa y compara dependiendo de cómo estén dispuestos los subarreglos, por lo que el algoritmo requiere procedimientos transversales de izquierda a derecha (si el arreglo más pequeño está a la izquierda) y de derecha a izquierda (si el arreglo más pequeño está a la derecha). En la práctica, generalmente nos limitamos al primer procedimiento y seleccionamos la matriz izquierda, independientemente de su tamaño; esto casi no tiene efecto en la velocidad de clasificación.

1. Se crea una matriz temporal del tamaño del menor de los subarreglos unidos.
2. El más pequeño de los subarreglos se copia en un arreglo temporal
3. Los punteros a la posición actual se colocan en los primeros (últimos) elementos de una matriz más grande y temporal.
4. En cada paso siguiente, se considera el valor de los elementos actuales en las matrices más grandes y temporales, el más pequeño (más grande) de ellos se toma y se copia en una nueva matriz ordenada. El puntero del elemento actual se mueve en la matriz de la que se tomó el elemento.
5. El paso 4 se repite hasta que finaliza una de las matrices.
6. Todos los elementos de la matriz restante se agregan al final de la nueva matriz.

Modificación del procedimiento de fusión de subarreglos (Modo Galopante)

Imagine el procedimiento para fusionar las siguientes matrices:

El procedimiento anterior funcionará para ellos, pero cada vez en su cuarto paso deberá realizar una comparación y una copia. Como resultado, 10.000 comparaciones y 10.000 copias. El algoritmo de Timsort ofrece una modificación en este punto, que él llama "galope". Algoritmo:

• Comienza el procedimiento de fusión, como se muestra arriba.
• En cada operación de copiar un elemento de un subarreglo temporal o más grande al resultante, se recuerda de qué subarreglo era el elemento.
• Si ya se ha tomado un cierto número de elementos (en esta implementación del algoritmo este número es 7) de la misma matriz, se supone que continuaremos tomando datos de ella. Para confirmar esta idea, el algoritmo entra en el modo de “galope”, es decir, se mueve a través de la matriz candidata para el suministro de la siguiente gran porción de datos por búsqueda binaria (se ordena la matriz) del elemento actual del segundo. matriz a unir.
• En el momento en que los datos de la matriz de proveedores actual ya no son adecuados (o se ha llegado al final de la matriz), los datos se copian en su totalidad.

Modo de galope, por ejemplo:

Las primeras 7 iteraciones comparan los números 1, 2, 3, 4, 5, 6 y 7 de la matriz A con el número 20000, ya que 20000 es mayor: los elementos de la matriz A se copian en la resultante. A partir de la siguiente iteración, el algoritmo cambia al modo “galope”: compara secuencialmente los elementos 8, 10, 14, 22, 38, n+2^i, …, 10000 de la matriz A con el número 20000 (~log2 N comparaciones). Una vez que se alcanza el final de la matriz A y se sabe que es menor que B, los datos necesarios de la matriz A se copian en la matriz resultante.

Notas

1. ↑ Función de clasificación incorrecta en Android, Rust, Java y Python . "Hacker". Consultado el 5 de diciembre de 2015. Archivado desde el original el 8 de diciembre de 2015. (indefinido)
2. ↑ jjb Commit 6804124: Reemplazar "mergesort modificado" en java.util.Arrays.sort con timsort . Kit de desarrollo de Java 7 Hg repositorio . Consultado el 24 de febrero de 2011. Archivado desde el original el 4 de septiembre de 2012. (indefinido)
3. ↑ Clasificación rápida de Apple  . GitHub . Consultado el 5 de mayo de 2021. Archivado desde el original el 24 de junio de 2021.
4. ↑ Clase: java.util.TimSort<T> . Documentación de Android JDK 1.5 . Consultado el 24 de febrero de 2011. Archivado desde el original el 4 de septiembre de 2012. (indefinido)
5. ↑ Hetland, 2010 .

Literatura

• Peter McIlroy "Clasificación optimista y complejidad teórica de la información", Actas del cuarto simposio anual ACM-SIAM sobre algoritmos discretos, ISBN 0-89871-313-7 , capítulo 53, páginas 467-474, enero de 1993. [1]
• Magnus Lie Hetland. Algoritmos de Python: Dominio de algoritmos básicos en el lenguaje Python. - Apress, 2010. - 336 p. - ISBN 978-1-4302-3237-7 .

Enlaces

• Representación del algoritmo de su creador  (ing.) . Archivado desde el original el 4 de septiembre de 2012.
• Timsort implementado en Python para PyPy  ( py). Archivado desde el original el 4 de septiembre de 2012.
• Visualización de algoritmos  (ing.) . Archivado desde el original el 4 de septiembre de 2012.