Introsort

Introsort

Découvreur ou inventeur	David Musser(en)
Date de découverte	1997
Problèmes liés	Algorithme de tri,hybrid algorithm(en)
Structure des données	Tableau

Complexité en temps

Pire cas	$O(n\log n)$
Moyenne	$O(n\log n)$

Introsortouintrospective sortest unalgorithme de tripar comparaisons. C'est une variante dutri rapideinventée parDavid Musseren 1997. Par rapport au tri rapide, Introsort a l'avantage d'avoir unecomplexité$O(n\log n)$dans le pire cas.

Principe

L'algorithme detri rapideest ralenti lorsque le pivot choisi se retrouve souvent au début ou à la fin du sous-tableau trié. Dans ce cas, la profondeur de récursion est en$O(n)$et le temps total en$O(n^{2})$,ce qui est un temps comparable à untri par sélection.Mais en moyenne, letri rapideest efficace: sa complexité est$O(n\log n)$.

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$K\log n$où K est une constante, on trie le sous-tableau restant avec un algorithme dont la complexité est$O(n\log n)$dans tous les cas, par exemple untri par tasou unSmoothsort.

Tout comme letri rapide,Introsort peut être optimisé en triant les sous-listes de moins de 15 éléments avec untri par insertionou untri de Shell,au fur et à mesure, ou à la fin (principe deSedgesort).

Algorithme

Avec A: Tableau et n = Longueur(A)

Faire Introsort(A, 2*PartieEntière(Log2(n)) )

• Procédure Introsort (A: Tableau[Min..Max], ProfondeurLimite: Entier > 0)
  • Initialiser
    • CurMin:= Min et CurMax:= Max
    • Pivot:= A[PartieEntière((Min + Max) / 2)]
  • Répéter jusqu'à ce que CurMin > CurMax
    • Tant que A[CurMin] < Pivot, CurMin:= CurMin + 1
    • Tant que A[CurMax] > Pivot, CurMax:= CurMax - 1
    • Si CurMin < CurMax alors Echanger(A[CurMin], A[CurMax])
    • CurMin = CurMin + 1
    • CurMax = CurMax - 1
  • Si CurMax > Min
    • Si ProfondeurLimite = 1 alors faire Heapsort(A[Min..CurMax])
    • Sinon faire Introsort(A[Min..CurMax], ProfondeurLimite - 1)
  • Si CurMin < Max
    • Si ProfondeurLimite = 1 alors faire Heapsort(A[CurMin..Max])
    • Sinon faire Introsort(A[CurMin..Max], ProfondeurLimite - 1)

Voir aussi

• Tri rapide(quicksort)
• Tri par tas(heapsort)