Outils :Vous avez un site web ? Un blog ?
 Technorati reactions rencontre |
Introsort ou introspective sort est un algorithme de tri en O(nlogn) quelles que soient les données de départ. C'est une amélioration du tri rapide trouvée par David Musser en 1997.
L'algorithme quicksort est ralenti lorsque le pivot choisi est à chaque fois à la fin ou au début de la sous-liste triée. Dans ce cas, le nombre de récursion est en O(n) et le temps total en O(n2), ce qui est un temps comparable à un tri par sélection. Mais, mis à part le cas de récursion linéaire, le tri rapide, comme son nom l'indique est rapide, c'est-à-dire en O(nlogn).
Introsort pour pallier cet inconvénient, utilise un compteur de récursion. Ainsi il mesure au fur et à mesure la profondeur de récursion en cours (d'où le nom de l'algorithme). Quand la profondeur dépasse Klogn où K est un constante, un algorithme en O(nlogn) est utilisé pour trier les sous-listes restantes : un tri par tas, un Smoothsort etc.
Tout comme le tri rapide, Introsort peut être optimisé en triant les sous-listes de moins de 15 éléments avec un tri par insertion ou un tri de Shell, au fur et à mesure, ou à la fin (principe de Sedgesort).
Avec A: Tableau et n = Longueur(A)
Faire Introsort(A, 2*PartieEntière(Log2(n)) )
