Qualcuno sa di un'implementazione di timsort pulita in C/C++?implementazione veloce, pulita, C, timsort?
Le origini Python contengono uno description e code per il timsort originale, ma è comprensibilmente pieno di chiamate specifiche di Python.
Grazie!
ho scritto, versione veloce modello simile in C:
http://github.com/swenson/sort
Esso include anche un sacco di altri algoritmi di ordinamento. Timsort sembra battere l'ordinamento veloce del 5% circa.
Questa implementazione da Android non è in C, ma è molto più semplice da capire dell'originale presente su SVN di Python.
http://gee.cs.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/src/main/java/util/TimSort.java?view=co
Speriamo che sia relativamente facile da tradurre in codice C.
Ho scritto una porta C++ con la stessa interfaccia di std :: sort(), con alcuni test di benchmark e unità.
https://github.com/gfx/cpp-TimSort
Noe che perché l'implementazione originale è in OpenJDK e la sua licenza è GPL, la licenza della mia esecuzione è anche GPL. Ora è distribuito nella licenza MIT.
Ho notato che il tuo readme dice che è un ordinamento "O (n^2)", ma nella pagina Wikipedia di Timsort il caso peggiore è O (nlog n). –
Grazie, è un mio errore. fisso! –
FWIW la licenza del codice è stata modificata in MIT poiché questa risposta è stata pubblicata. – rotoglup