Algoritmos de ordenación son una incómoda combinación de, fundamentalmente, necesario, y muy polémico. Desde los nuevos ingenieros que buscan impresionar en una entrevista hasta los ingenieros más antiguos que buscan una solución o una base de datos de escalado rápido, hay innumerables factores a tener en cuenta. ¿Cuál es la velocidad de comparación entre dos objetos? ¿Cuál es la hora del intercambio? ¿Qué tamaño tiene la base de datos? ¿Qué tipo de objetos contiene? ¿Ya está semi-ordenado? ¿Es necesario que los resultados sean estables?

Cada una de estas preguntas puede sacar argumentos a favor de un algoritmo u otro. ¿Los datos de origen son grandes y complejos? La mayoría de los idiomas tienen por defecto la clasificación rápida estándar con su complejidad de tiempo O( n log n). Es más pequeño? La clasificación de inserción funciona de maravilla en ellos. En su mayoría ordenados? Diablos, el tipo de burbuja casi podría funcionar para eso. Si desea leer / visualizar los méritos de cada uno, consulte esta comparación por toptal.com.

Un algoritmo de ordenación que no encontrarás en ese sitio, o en casi ningún otro, es Tim Sort. Esta clasificación oscura es actualmente exclusiva de Python, y se utiliza como su algoritmo de clasificación predeterminado. Llame a array.sort en Python, y Tim Sort es lo que se ejecuta. A pesar de esto, es raro encontrar ingenieros que conozcan y entiendan a Tim Sort. Entonces, ¿qué es?

Tim Sort fue implementado por primera vez en 2002 por Tim Peters para su uso en Python. Supuestamente surgió del entendimiento de que la mayoría de los algoritmos de clasificación nacen en las aulas escolares y no están diseñados para uso práctico en datos del mundo real. Tim Sort aprovecha los patrones comunes en los datos y utiliza una combinación de Ordenación de fusión y Ordenación de inserción junto con cierta lógica interna para optimizar la manipulación de datos a gran escala.

¿por Qué Tim Tipo?

Mirando la figura 2, podemos ver inmediatamente algo interesante. En su mejor momento, Tim Sort supera a Merge Sort y Quick Sort. En el peor de los casos, funciona a una velocidad comparable de ordenación combinada y, en realidad, supera a la Ordenación rápida. En otras palabras, es inesperadamente rápido.

En términos de espacio, Tim Sort se encuentra en el extremo peor del espectro, pero la consideración de espacio para la mayoría de los algoritmos de ordenación es bastante escasa. O (n) no es demasiado áspero en la mayoría de los casos; vale la pena señalarlo como una posible deficiencia, y el único lugar donde Quick Sort realmente eclipsa a Tim Sort.

El elemento final en el que a menudo se juzgan los algoritmos de ordenación es la estabilidad. La estabilidad es el concepto de que, cuando se ordenan, los objetos de igual valor mantienen su orden original. Ahora, se preguntarán por qué nos importa eso. Los artículos son de igual valor, ¿por qué nos importa cómo se ordenan?

La respuesta simple es que la estabilidad importa para las clases apiladas. Es decir, primero se ordena en función de un criterio, luego en función de un segundo. Si hace esto en un algoritmo inestable, perderá instantáneamente la fiabilidad de su primera clasificación cuando ejecute la segunda. Como referencia, la ordenación rápida es inestable y la ordenación combinada es estable.

Tim Sort también es estable, sin mencionar rápido si es ligeramente pesado (en comparación con Quick Sort solamente). Si bien los algoritmos de ordenación pueden (y deben) juzgarse por otras consideraciones, estas son las tres grandes.

La Implementación En Tres Pasos

Tim Sort es compleja, incluso por estándares algorítmicos. La implementación se divide mejor en partes.

Búsqueda binaria

Lo primero que necesita para implementar una clasificación Tim es un método de búsqueda binario. Esto solo se usa para implementar su Ordenación de inserción más adelante.

Para referencia: Algoritmos de búsqueda binarios

Ordenación por inserción & Ordenación combinada

En segundo lugar, debe codificar Ordenación por inserción y Ordenación combinada. Estos son algoritmos familiares, y deberían estar en el bolsillo trasero de la mayoría de los ingenieros, pero repasaremos los fundamentos de cómo funcionan y por qué son valiosos para nosotros aquí.

de Ordenación por Inserción es muy sencillo algoritmo de ordenamiento. Se ejecuta a través de la matriz, y cada vez que encuentra un elemento que está fuera de orden (estrictamente menos/más que el elemento anterior), lo mueve a la posición adecuada en la matriz ya ordenada. La ordenación por inserción es conocida por trabajar muy rápidamente en matrices ya ordenadas, así como en matrices más pequeñas. De hecho, podemos ver en la Figura 2 que la clasificación por inserción tiene un impresionante tiempo de ejecución en el mejor de los casos de O(n). Tenga en cuenta seguir adelante con la ordenación de Tim: el mejor caso para la Ordenación por inserción es una matriz ya ordenada. Puede sonar tonto, pero eso será relevante.

Combinar de alguna manera en el otro lado funciona por un principio básico: es muy fácil de combinar ya matrices ordenadas. Por lo tanto, divide una matriz inicial por la mitad una y otra vez hasta que no es más que elementos individuales. Luego reconstruye lentamente la matriz principal fusionando esos elementos en orden ordenado. Debido a que comenzamos a construir bloques de tamaño uno, fue muy fácil construir matrices ordenadas iniciales. Entonces, es fácil fusionarlos. Al final, pasamos O (n log n) tiempo, y (lo que es más importante) lo hacemos de una manera que está garantizada para ser estable.

Por ejemplo, ver implementaciones:

Merge Sort: https://www.geeksforgeeks.org/merge-sort/

Ordenación de inserción: https://www.geeksforgeeks.org/insertion-sort/

Implementar Ordenación de tim

La clave para comprender la implementación de Ordenación de Tim es comprender su uso de ejecuciones. Tim Sort aprovecha los datos pre clasificados de origen natural para su ventaja. Con preseleccionado simplemente queremos decir que todos los elementos secuenciales están aumentando o disminuyendo (no nos importa cuáles).

Primero configuramos un tamaño minrun. Lo que queremos decir con esto es que queremos asegurarnos de que todas nuestras carreras tengan al menos una cierta longitud. Tenga en cuenta que no estamos garantizando que encontraremos carreras de este tamaño, ya hablaremos de esto más adelante. Simplemente estamos diciendo que una carrera debe tener al menos una cierta longitud.

Cuando nos encontramos con una carrera, la dejamos a un lado. Cuando encontramos la carrera más larga dentro de un rango minrun. Ahora tenemos una estructura de datos familiar: una matriz pequeña y ordenada. Si tiene al menos minrun de longitud, ¡hurra! Estamos bien para seguir adelante. Si no lo es, ponemos en juego la Clasificación de inserción.

Puede recordar que la ordenación por inserción es especialmente eficaz en dos tipos de matrices: las pequeñas y las ya ordenadas. Lo que acabamos de hacer es una pequeña matriz ordenada. Si no tiene al menos minrun en longitud, avanzamos y tomamos suficientes elementos para completar la ejecución, luego usamos la Clasificación de inserción para introducirlos en nuestra matriz ordenada, rápida y fácil. Obviamente, si una carrera se encuentra con el final de la matriz, puede dejar que sea un poco corta.

Una vez que haya creado todas sus carreras (es decir, subarrays ordenados), utilice su Orden de fusión para unirlas. En el mejor de los casos, toda la matriz ya está ordenada y Tim Sort es lo suficientemente inteligente como para saber que no necesita hacer nada más. Otras veces, tiende a ser extremadamente eficiente. Como beneficio adicional, tanto la ordenación por inserción como la Ordenación por fusión son estables, por lo que la matriz resultante es estable.

Para aquellos que prefieren las balas:

1. Establezca un minrun tamaño que tenga una potencia de 2 (generalmente 32, nunca más de 64 o su Clasificación de inserción perderá eficiencia)
2. Encuentre una ejecución en el primerminrun de datos.
3. Si la duración de la ejecución no es, al menos, minrun, utilice la clasificación por inserción para capturar elementos anteriores o posteriores e insertarlos en la ejecución hasta que tenga el tamaño mínimo correcto.
4. Repetir hasta que todo el array esté dividido en subsecciones ordenadas.
5. Utilice la segunda mitad de Merge Sort para unir las matrices ordenadas.

Conclusión

Tim Sort es potente. Es rápido y estable, pero quizás lo más importante es que aprovecha los patrones del mundo real y los utiliza para construir un producto final. ¿Es para cada situación? Probablemente no. Buena suerte programándolo en una pizarra durante una entrevista, y si solo necesita un algoritmo de clasificación rápido y simple en un apuro, probablemente no quiera molestarse en implementar algo tan complejo. Sin embargo, para los científicos de datos que hacen cálculos numéricos, vale la pena echarle un vistazo.

Para los curiosos, puedes consultar todo el código de ordenación de Tim en github.

Gracias

Gracias a todos mis lectores. Aprecio su tiempo, y sinceramente espero que haya encontrado el contenido informativo. Si tiene alguna pregunta o respuesta, no dude en dejar una a continuación.