Aller au contenu

Timsort

Un article de Wikipédia, l'encyclopédie libre.
Timsort
Découvreur ou inventeur
Tim Peters (en)Voir et modifier les données sur Wikidata
Date de découverte
Problèmes liés
Algorithme de tri, tri stable (en), tri par comparaison, hybrid algorithm (en), adaptive sort (en)Voir et modifier les données sur Wikidata
Structure des données
Basé sur
Complexité en temps
Pire cas
[1],[2]Voir et modifier les données sur Wikidata
Moyenne
Voir et modifier les données sur Wikidata
Meilleur cas
[3]Voir et modifier les données sur Wikidata
Complexité en espace
Pire cas
Voir et modifier les données sur Wikidata

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[4], ainsi que par Android[5] et GNU Octave[6]. Une variante de l'algorithme, Adaptive Shivers Sort, a été proposée par Vincent Jugé[7],[8]

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 concernant 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[9] que la formulation initiale de l'algorithme ne garantissait pas toujours le maintien des invariants[10]. 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[11].

  1. Tim Peters (d), « http://mail.python.org/pipermail/python-dev/2002-July/026837.html »,  : « [Timsort] also has good aspects: It's stable (items that compare equal retain their relative order, so, e.g., if you sort first on zip code, and a second time on name, people with the same name still appear in order of increasing zip code; this is important in apps that, e.g., refine the results of queries based on user input). ... It has no bad cases (O(N log N) is worst case; N−1 compares is best). »
  2. « http://drops.dagstuhl.de/opus/volltexte/2018/9467/ » : « TimSort is an intriguing sorting algorithm designed in 2002 for Python, whose worst-case complexity was announced, but not proved until our recent preprint. »
  3. (en) Badrish Chandramouli et Jonathan Goldstein, « Patience is a virtue: revisiting merge and sort on modern processors », SIGMOD conference,‎ , p. 731-742 (DOI 10.1145/2588555.2593662).Voir et modifier les données sur Wikidata
  4. (en) « [#JDK-6804124] (coll) Replace "modified mergesort" in java.util.Arrays.sort with timsort » (consulté le )
  5. (en) Android Gingerbread Documentation, « Class: java.util.TimSort<T> », sur Documentation Android (consulté le )
  6. (en) « liboctave/util/oct-sort.cc », sur Dépôt Mercurial d'Octave (consulté le )
  7. Jugé 2020.
  8. « Vincent Jugé améliore l’algorithme au cœur de Python, Java et Android » sur CNRS Actualités INS2I.
  9. (en) Projet KeY (consulté le )
  10. (en) « Proving that Android’s, Java’s and Python’s sorting algorithm is broken (and showing how to fix it) »
  11. (en) « Python Issue Tracker - Issue 23515: Bad logic in timsort's merge_collapse »

Bibliographie

[modifier | modifier le code]

Liens externes

[modifier | modifier le code]

Implémentations

[modifier | modifier le code]