Introsort

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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[modifier | modifier le code]

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[modifier | modifier le code]

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[modifier | modifier le code]