Introsort

Introsort ou introspective sort est un algorithme de tri par comparaisons. C'est une variante du tri rapide inventée par David Musser en 1997. Par rapport au tri rapide, Introsort a l'avantage d'avoir une complexité $O(n\log n)$ dans le pire cas.

Principe

L'algorithme de tri rapide est 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 à un tri par sélection. Mais en moyenne, le tri rapide est 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 un tri par tas ou un Smoothsort.

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).

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)