Introsort — Wikipédia
Découvreur ou inventeur | |
---|---|
Date de découverte | |
Problèmes liés | Algorithme de tri, hybrid algorithm (en) |
Structure des données |
Pire cas | |
---|---|
Moyenne |
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é 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 et le temps total en , ce qui est un temps comparable à un tri par sélection. Mais en moyenne, le tri rapide est efficace : sa complexité est .
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 où K est une constante, on trie le sous-tableau restant avec un algorithme dont la complexité est 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)
- Initialiser
Voir aussi
[modifier | modifier le code]- Tri rapide (quicksort)
- Tri par tas (heapsort)
Notes et références
[modifier | modifier le code]- (en) David R. Musser, « Introspective Sorting and Selection Algorithms », Software: Practice and Experience, Wiley-Blackwell, vol. 27, no 8, , p. 983-993 (ISSN 1097-024X et 0038-0644, DOI 10.1002/(SICI)1097-024X(200005)30:6<617::AID-SPE311>3.0.CO;2-A).