Timsort est l'algorithme de tri principal de Python et d'Android. Son principal avantage est d'utiliser les suites monotones de la séquence initiale pour alléger la charge de travail. Ainsi, sur une entrée déjà partiellement triée, son temps de calcul pourra être réduit en conséquence.
On peut schématiser l'algorithme en trois phases :
Ici, l'algorithme de fusion est exactement le même que celui du tri par fusion.
La partie la plus complexe est l'étape intermédiaire : il faut pouvoir repérer très rapidement des séquences de longueurs similaires. Ceci est réalisé en gardant une liste des séquences triée par longueur croissante.
L'algorithme d'origine est impératif : il trie des tableaux en utilisant d'autres tableaux tout en essayant de ne pas avoir une trop grande empreinte en mémoire. Nous allons écrire une version fonctionnelle : pas de tableaux, mais aussi nous n'essayerons pas d'optimiser l'utilisation de la mémoire.
Nous voulons de plus construire une fonction de tri de même type que la fonction de tri de la librairie standard :
Les fonctions que nous allons écrire auront donc pour la plupart un argument compare : 'elt -> 'elt -> int, l'opérateur de comparaison.
Écrire une fonction qui calcule le plus long préfixe croissant d'une liste, retourne ce préfixe et le suffixe complémentaire.
En déduire une fonction qui calcule le plus long préfixe décroissant :
Utiliser ces deux fonctions pour écrire une fonction partitionnant une liste en sous-séquences croissantes (les séquences décroissantes seront renversées). Seule la dernière séquence pourra être de longueur 1 .
Écrire l'algorithme de fusion de deux listes croissantes.
Pour repérer les séquences de longueurs similaires, nous utilisons une liste de séquences triées par ordre de longueur croissante. Ainsi, deux séquences de longueurs proches seront successives.
Plus exactement, nous allons avoir une liste de séquences $l_1,l_2,l_3,\ldots,l_k$ telles que :
En effet, si $|l_i| + |l_{i+1}| \geq |l_{i+2}|$ c'est que $|l_{i+1}| \leq |l_{i+2}| \leq 2 |l_{i+1}|$, donc $l_{i+1}$ et $l_{i+2}$ sont de longueurs similaires et on peut les fusionner.
Si le deuxième invariant est violé, il suffit de réordonner les listes localement jusqu'à correction des deux invariants.
Notre but est donc, étant donné une telle liste, d'insérer une séquence supplémentaire tout en préservant les deux invariants, si nécessaire en fusionnant des listes de longueurs similaires.
Pour cela, on utilise un algorithme récursif. Si la séquence à insérer est plus longue que la première séquence de la liste, on l'insère dans la queue, puis on vérifie le deuxième invariant. Sinon on l'insère en début de liste et on vérifie aussi le deuxième invariant.
Lorsque le deuxième invariant est faux, on fusionne le deuxième et le troisième élément et on insère le résultat dans le reste.
Afin de ne pas recalculer la longueur des séquences chaque fois, la liste doit contenir des couples (séquence, longueur).
Implémenter cette stratégie à l'aide de deux fonctions mutuellement récursives.
Après insertion de toutes les séquences, il ne reste plus qu'à effectuer des opérations de fusion sur toutes les séquences, en partant des plus courtes, jusqu'à n'en avoir plus qu'une.
Coder une fonction de réduction selon ce principe :
Les principales parties de l'algorithme sont maintenant écrites, il ne reste plus qu'à écrire la fonction de tri :
Pour cela, on découpe la liste en séquences croissantes, qu'on insère une à une dans une liste de séquences gràce à la fonction appropriée, puis on réduit la liste de séquences et on retourne le résultat de la réduction.
Comparer votre fonction de tri avec celle de la librairie standard :
Pour cela, vous pouvez utiliser la fonction suivante de module Unix :
Essayer avec des listes bien mélangées, peu mélangées, etc.
