¿Alguien sabe de una implementación limpia de C/C++ de timsort?implementación rápida, limpia, C, timsort?
Las fuentes de Python contienen un description y code para el timsort original, pero comprensiblemente está lleno de llamadas específicas de python.
Gracias!
me escribió una versión rápida, plantilla-como en C:
http://github.com/swenson/sort
También incluye un montón de otros algoritmos de ordenación. Timsort parece superar el orden rápido en un 5% más o menos.
Esta implementación de Android no está en C, pero es mucho más fácil de entender que la original que está en el SVN de Python.
http://gee.cs.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/src/main/java/util/TimSort.java?view=co
Es de esperar que es relativamente fácil de traducir a código C.
Escribí un puerto C++ con la misma interfaz que std :: sort(), con algunas pruebas comparativas y unitarias.
https://github.com/gfx/cpp-TimSort
Noe que debido a la aplicación original está en OpenJDK y su licencia es GPL, la licencia de mi aplicación es también GPL. Ahora se distribuye en la licencia de MIT.
Me di cuenta de que su léame dice que es del tipo "O (n^2)", pero la página de Wikipedia de Timsort dice que su peor caso es O (nlog n). –
Gracias, es mi error. ¡fijo! –
FWIW la licencia de código se ha cambiado a MIT desde que se publicó esta respuesta. – rotoglup