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, ainsi que par Android et GNU Octave. Une variante de l'algorithme, Adaptive Shivers Sort, a été proposée par Vincent Jugé
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.
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
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.
En informatique, le tri rapide ou tri pivot (en anglais quicksort) est un algorithme de tri inventé par C.A.R. Hoare en 1961 et fondé sur la méthode de conception diviser pour régner. Il est généralement utilisé sur des tableaux, mais peut aussi être adapté aux listes. Dans le cas des tableaux, c'est un tri en place mais non stable. La complexité moyenne du tri rapide pour n éléments est proportionnelle à n log n, ce qui est optimal pour un tri par comparaison, mais la complexité dans le pire des cas est quadratique.
A comparison sort is a type of sorting algorithm that only reads the list elements through a single abstract comparison operation (often a "less than or equal to" operator or a three-way comparison) that determines which of two elements should occur first in the final sorted list. The only requirement is that the operator forms a total preorder over the data, with: if a ≤ b and b ≤ c then a ≤ c (transitivity) for all a and b, a ≤ b or b ≤ a (connexity). It is possible that both a ≤ b and b ≤ a; in this case either may come first in the sorted list.
Le TP de physiologie introduit les approches expérimentales du domaine biomédical, avec les montages de mesure, les capteurs, le conditionnement des signaux, l'acquisition et traitement de données.
Le
Le TP de physiologie introduit les approches expérimentales du domaine biomédical, avec les montages de mesure, les capteurs, le conditionnement des signaux, l'acquisition et traitement de données.
Le
Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics a
Couvre l'analyse des chiffres d'ergométrie à l'aide d'Excel et l'interprétation des paramètres respiratoires et cardiovasculaires.
Couvre l'induction, la récursion, les algorithmes de tri, et la complexité du tri de fusion en informatique.