Timsort

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche

Timsort
Problème lié Algorithme de tri
Structure des données Tableau (informatique)
Temps d'exécution pire-cas

Timsort est un algorithme de tri hybride dérivé du tri fusion et du tri par insertion, stable et conçu pour fonctionner de manière efficace sur des données réelles. Il a été mis au point par Tim Peters en 2002 pour le langage de programmation Python.

L'algorithme procède en cherchant des monotonies, c'est-à-dire des parties de l'entrée déjà correctement ordonnées, et peut de cette manière trier efficacement l'ensemble des données en procédant par fusions successives. Pour des entrées de petites tailles, il revient à effectuer un tri fusion.

Timsort est l'algorithme standard de tri utilisé par Python depuis la version 2.3. Il est également utilisé pour trier des données de types non-primitifs en Java 7[1], ainsi que par Android[2] et GNU Octave[3].

Principe de fonctionnement[modifier | modifier le code]

Timsort a été conçu pour tenir compte de l'ordre initial des éléments à trier ; il est en effet possible que ceux-ci soient en pratique déjà partiellement ordonnés.

L'algorithme procède en parcourant le tableau à la recherche de monotonies, c'est-à-dire dans ce cas de suites d'au moins deux éléments consécutifs croissantes ou strictement décroissantes − les monotonies décroissantes sont simplement renversées, le caractère strict est donc indispensable pour garantir la stabilité de l'algorithme.

Pour des raisons de performance, une taille minimum est fixée pour la longueur des monotonies recherchées : si la monotonie en cours de construction a en pratique une taille inférieure à , c'est-à-dire si la suite des éléments présents à cet endroit du tableau n'est pas monotone, une monotonie est artificiellement construite en effectuant un tri par insertion stable sur les éléments consécutifs présents à l'endroit en question du tableau.

Une pile est utilisée pour mémoriser les monotonies (adresse mémoire et longueur) déjà identifiées. L'algorithme parcourt le tableau en même temps que les monotonies mémorisées dans la pile sont fusionnées deux à deux. Il n'est pas optimal de fusionner une monotonie dès qu'elle est trouvée avec la précédente, car il peut être plus intéressant de prendre en considération les tailles des monotonies suivantes. Toutefois, attendre d'avoir ajouté toutes les monotonies à la pile avant de commencer à les fusionner réduirait également les performances, car fusionner les monotonies le plus rapidement possible permet de tirer profit de la persistance des données dans les couches hautes de la hiérarchie mémoire ; de plus, il est coûteux en espace de mémoriser toutes les monotonies. Dans tous les cas, seules deux monotonies consécutives dans la pile peuvent être fusionnées afin de garantir la stabilité de l'algorithme.

Fusions de monotonies[modifier | modifier le code]

En pratique, l'algorithme procède aux fusions qui permettent de garantir les propriétés suivantes sur les tailles , et des trois monotonies du dessus de la pile :

Par exemple, si la propriété (1.) n'est pas satisfaite, la seconde monotonie de la pile va être fusionnée avec la plus petite des première et troisième monotonies, et d'autres fusions peuvent être effectuées par la suite tant que les propriétés ne sont pas vérifiées. L'idée est d'essayer de favoriser les fusions entre monotonies de tailles similaires.

La fusion est effectuée au moyen d'un tableau temporaire, dont la taille est celle de la plus petite des deux monotonies à fusionner.

Choix de la taille minimale des monotonies[modifier | modifier le code]

Si le nombre d'éléments à trier est inférieur à 64, la taille minimale des monotonies est fixée à et cela revient à effectuer un tri par insertion sur l'ensemble des données. Si ce n'est pas le cas, les valeurs utilisées sont typiquement 16, 32, 64 ou 128. Le choix d'une puissance de 2 est important pour la phase de fusion.

Complexité[modifier | modifier le code]

Timsort a une complexité en temps dans le pire des cas en . Dans le meilleur cas, qui survient par exemple si la liste est déjà triée, la complexité est linéaire.

La complexité en espace dans le pire des cas est également linéaire en la taille de l'entrée.

Bug concerant le maintien des invariants[modifier | modifier le code]

Des chercheurs ont montré en utilisant des méthodes formelles, et plus précisément l'outil KeY[4] que la formulation initiale de l'algorithme ne garantissait pas toujours le maintien des invariants[5]. Le bug n'a pas été jugé critique car il ne concernait que des entrées de tailles bien supérieures à ce que l'on peut traiter en pratique, mais a toutefois été corrigé rapidement[6].

Annexes[modifier | modifier le code]

Notes[modifier | modifier le code]

  1. (en) « [#JDK-6804124] (coll) Replace "modified mergesort" in java.util.Arrays.sort with timsort » (consulté le 30 novembre 2015)
  2. (en) Android Gingerbread Documentation, « Class: java.util.TimSort<T> », sur Documentation Android (consulté le 30 novembre 2015)
  3. (en) « liboctave/util/oct-sort.cc », sur Dépôt Mercurial d'Octave (consulté le 30 novembre 2015)
  4. (en) Projet KeY (consulté le 7 décembre 2015)
  5. (en) « Proving that Android’s, Java’s and Python’s sorting algorithm is broken (and showing how to fix it) »
  6. (en) « Python Issue Tracker - Issue 23515: Bad logic in timsort's merge_collapse »

Bibliographie[modifier | modifier le code]

  • (en) Nicolas Auger, Cyril Nicaud et Carine Pivoteau, Merge Strategies: from Merge Sort to TimSort [« Stratégies de fusion : du tri-fusion à Timsort »], (lire en ligne)

Liens externes[modifier | modifier le code]

Théorie[modifier | modifier le code]

Implémentations[modifier | modifier le code]