Introsort

Introsort

Découvreur ou inventeur	David Musser (en)[1]
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	${\displaystyle O(n\log n)}$
Moyenne	${\displaystyle O(n\log n)}$

modifier - modifier le code - modifier Wikidata

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é ${\displaystyle O(n\log n)}$ dans le pire cas.

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 ${\displaystyle O(n)}$ et le temps total en ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle K\log n}$ où K est une constante, on trie le sous-tableau restant avec un algorithme dont la complexité est ${\displaystyle 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).

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)

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

v · m Algorithmes de tri
Tris par comparaisons	Sans hypothèse autre Complexité moyenne ${\displaystyle {\mathcal {O}}(n\log n)}$ Tri rapide Tri fusion Tri par tas Introsort Smoothsort Timsort Tri arborescent Tri à peigne (?) Tri de Shell (?) Complexité moyenne ${\displaystyle {\mathcal {O}}(n^{2})}$ Tri à bulles Tri par insertion Tri par sélection Tri cocktail Complexité moyenne moins bonne que ${\displaystyle {\mathcal {O}}(n^{2})}$ Tri spaghetti Tri stupide Tri faire-valoir Avec hypothèse supplémentaire Tri comptage Tri par base Tri par paquets Réseau de tri Tri bitonique Tri pair-impair
Tri utilisant d'autres opérations	Tri de crêpes Algorithme de tri externe Tri topologique
Applications	Problème du drapeau hollandais Recherche dichotomique

• Portail des mathématiques
• Portail de l’informatique