Primeros pasos en programación con Python

El algoritmo de ordenamiento en Python que está detrás de list.sort()

Lo has utilizado, pero no sabes cómo está implementado… Defines tu lista y luego aplicas ordenamiento

miLista = [1,2,61,89,56,97,6]

miLista.sort() # ordena miLista

print(miLista) # imprime [1,2,6,56,61,89,97]

¿Cómo funciona? ¿Qué clase de brujería es esta? Es un algoritmo de ordenamiento que nació fuera del entorno académico y que se llama TimSort. Se implementó nativamente en Python y ha resultado se tan eficiente que se usa también como algoritmo base para ordenamiento en Java. Veremos a continuación cómo funciona y por qué lo hemos reservado para el gran final.

Timsort es un algoritmo de clasificación que es eficiente para los datos del mundo real y no creado en un laboratorio académico. Tim Peters creó Timsort para el lenguaje de programación Python en 2001. Timsort primero analiza la lista que está tratando de ordenar y luego elige un enfoque basado en el análisis de la lista.

Su creador Tim, esta feliz de haberlo creado, aunque no lo parezca.

El tiempo de clasificación de Timsort es el mismo que Mergesort, que es más rápido que la mayoría de los otros tipos que podrías conocer. Timsort en realidad hace uso de la Insertion Sort y Merge sort.

Peters diseñó Timsort para utilizar elementos ya ordenados que existen en la mayoría de los conjuntos de datos del mundo real. Llama a estos elementos ya ordenados “corridas naturales”. Recorre en iteración los datos que recopilan los elementos en ejecuciones y los fusiona simultáneamente en uno.

 

Si quieres saber más sobre cómo implementar Timsort se sugiere ingresar a la liga del final de artículo ahí hay una implementación completa de Timsort, que en resumen usas todo el tiempo a través de lista.sort()

Con información a partir de material recuperado el 26 de mayo de hackernoon.com

https://hackernoon.com/timsort-the-fastest-sorting-algorithm-youve-never-heard-of-36b28417f399

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *