Voir la source de Algorithme de tri

{{confusion | tri topologique}}
[[Fichier:Merge sort animation2.gif|vignette|Tri d'une liste aléatoire à l'aide du tri par fusion.]]
Un '''algorithme de tri''' est, en [[informatique]] ou en [[mathématiques]], un [[algorithme]] qui permet d'organiser une collection d'objets selon une [[relation d'ordre]] déterminée. Les objets à trier sont des éléments d'un [[ensemble]] muni d'un [[ordre total]]. Il est par exemple fréquent de trier des [[entier naturel|entiers]] selon la relation d'ordre usuelle « est inférieur ou égal à ». Les algorithmes de tri sont utilisés dans de très nombreuses situations. Ils sont en particulier utiles à de nombreux algorithmes plus complexes dont certains [[algorithme de recherche|algorithmes de recherche]], comme la [[recherche dichotomique]]. Ils peuvent également servir pour mettre des données sous forme [[canonique (informatique)|canonique]] ou les rendre plus lisibles pour l'utilisateur.

La collection à trier est souvent donnée sous forme de [[tableau (structure de données)|tableau]], afin de permettre l'[[accès direct]] aux différents éléments de la collection, ou sous forme de [[liste (informatique)|liste]], ce qui peut se révéler être plus adapté à certains algorithmes et à l'usage de la [[programmation fonctionnelle]].

Bon nombre d'algorithmes de tri procèdent par comparaisons successives, et peuvent donc être définis indépendamment de l'ensemble auquel appartiennent les éléments et de la [[Relation d'ordre|relation d’ordre]] associée. Un même algorithme peut par exemple être utilisé pour trier des [[Nombre réel|réels]] selon la relation d'ordre usuelle « est inférieur ou égal à » et des [[Chaîne de caractères|chaînes de caractères]] selon l'[[ordre lexicographique]]. Ces algorithmes se prêtent naturellement à une implémentation [[polymorphisme (informatique)|polymorphe]].

Les algorithmes de tri sont souvent étudiés dans les cours d'[[algorithmique]] pour introduire des notions comme la [[complexité en temps|complexité algorithmique]] ou la [[Terminaison d'un algorithme|terminaison]].

La [[classification]] des algorithmes de tri est très importante, car elle permet de choisir l’algorithme le plus adapté au problème traité, tout en tenant compte des contraintes imposées par celui-ci. Les principales caractéristiques qui permettent de différencier les algorithmes de tri, outre leur principe de fonctionnement, sont la [[complexité en temps|complexité temporelle]], la [[complexité en espace|complexité spatiale]] et le caractère stable.

== Principe de fonctionnement ==
[[File:Hollerith punch-card sorter (2586173692).jpg|thumb|Une trieuse de [[Carte perforée|cartes perforées]] [[Herman Hollerith|Hollerith]]]]
On distingue les algorithmes procédant par comparaisons successives entre éléments, dits « tris par comparaisons », des algorithmes plus spécialisés faisant des hypothèses restrictives sur la [[structure des données]] à trier (par exemple, le tri par comptage, applicable uniquement si les données sont prises dans un ensemble borné connu à l'avance).

Les algorithmes de tri par comparaison lisent les entrées uniquement au moyen d'une fonction de comparaison [[Code binaire|binaire]] ou [[Système ternaire|ternaire]] (lorsque le cas d'égalité est traité différemment). Il existe encore différents principes de fonctionnement au sein de cette classe : certains algorithmes de tri par comparaison procèdent par insertions successives, d'autres par fusions, d'autres encore par sélection.

En l'absence de précisions, on entend habituellement par « algorithme de tri » un algorithme de tri procédant par comparaisons.

== Complexité algorithmique ==
* La [[complexité en temps|complexité temporelle]] ([[complexité en moyenne|en moyenne]] ou [[complexité dans le pire des cas|dans le pire des cas]]) mesure le nombre d'opérations élémentaires effectuées pour trier une collection d'éléments. C'est un critère majeur pour comparer les algorithmes de tri, puisque c'est une estimation directe du temps d'exécution de l'algorithme. Dans le cas des algorithmes de tri par comparaison, la complexité en temps est le plus souvent assimilable au nombre de comparaisons effectuées, la comparaison et l'échange éventuel de deux valeurs s'effectuant en temps constant.
* La [[complexité en espace|complexité spatiale]] ([[complexité en moyenne|en moyenne]] ou [[complexité dans le pire des cas|dans le pire des cas]]) représente, quant à elle, la quantité de mémoire dont va avoir besoin l'algorithme pour s'exécuter. Celle-ci peut dépendre, comme le temps d'exécution, de la taille de l'entrée. Il est fréquent que les complexités spatiales en moyenne et dans le pire des cas soient identiques. C'est souvent implicitement le cas lorsqu’une complexité est donnée sans indication supplémentaire.

La complexité en temps est souvent notée <math>T</math> et  est exprimée comme une fonction du nombre <math>n</math> d'éléments à trier à l'aide des [[notations de Landau]] <math>O</math> et <math>\Theta</math>. 

Certains algorithmes de tri simples ont une complexité en temps quadratique, ''i.e.'' <math>T(n) = O(n^2)</math>, tandis que d'autres, plus élaborés, ont une complexité quasi linéaire : <math>T(n) = O(n\log(n))</math>.

La complexité temporelle en moyenne d’un algorithme basé sur une fonction de comparaison ne peut pas être meilleure que <math>O(n\log(n))</math>. Les tris qui ne demandent que <math>O(n\log(n))</math> comparaisons en moyenne sont par conséquent dits optimaux. Ce résultat constitue une borne inférieure asymptotique, mais on montre également que le nombre exact de comparaisons nécessaires est minoré par <math>\lceil\log_2(n!)\rceil</math>.

{{démonstration|déroulante=oui|contenu=
Le problème du tri consiste, étant donné une suite <math>u = (u_1, u_2, \dots, u_n)</math> d’éléments d’un ensemble totalement ordonné (par exemple <math>\mathbb{N}</math> muni de l'ordre usuel), à déterminer une permutation <math>\sigma</math> de <math>1, \dots, n</math> telle que <math>(u_{\sigma(1)}, \dots, u_{\sigma(n)})</math> soit triée. 

On suppose pour simplifier que tous les éléments à trier sont distincts, ce qui rend la permutation <math>\sigma</math> unique. Le résultat reste vrai ''a fortiori'' dans le cas général.

Un algorithme de tri par comparaisons successives se modélise comme un [[arbre binaire]]. Chaque nœud de l'arbre correspondant à une comparaison entre deux éléments <math>u_i</math> et <math>u_j</math>, et comportant deux fils représentant les deux comparaisons suivantes possibles selon l'issue de la première. 

À chaque exécution de l'algorithme sur une permutation de <math>u</math> peut être associé le chemin allant de la racine à une feuille correspondant à cette exécution ; deux entrées différentes sont nécessairement associées à deux chemins différents. Le nombre de permutations de <math>n</math> éléments distincts deux à deux étant <math>n!</math>, le nombre de feuilles de l'arbre est supérieur ou égal à cette valeur.

'''Borne inférieure pour la complexité dans le pire cas'''

Notons <math>h</math> la hauteur de l'arbre (''i.e.'' sa profondeur maximale, qui correspond au nombre de comparaisons ''dans le pire des cas''). Le nombre maximal de feuilles dans un arbre binaire de hauteur <math>h</math> est <math>2^h</math>.

Il vient donc : <math>2^h \geq n!</math>. D'une part, <math>h\geq\lceil\log_2(n!)\rceil</math>. D'autre part, en utilisant la [[formule de Stirling]], on obtient asymptotiquement <math>h \geq n \cdot \log_2(n) - n / \ln 2 = \Theta(n\,\log n)</math>.

Le fait qu'il existe des tris en <math>n \cdot \log_2(n)</math> montre d'autre part qu'il est possible d'avoir asymptotiquement <math>h \leq n \cdot \log_2(n)</math>. Cette borne donne donc bien la complexité minimum dans le pire cas d'un algorithme de tri par comparaisons.

'''Borne inférieure pour la complexité en moyenne'''

Étant donné un arbre binaire <math>A</math>, on note <math>F(A)</math> la profondeur moyenne des feuilles de <math>A</math>. Si toutes les permutations des éléments en entrée sont équiprobables, alors le nombre moyen de comparaisons du tri avec un arbre de comparaisons <math>A</math> est <math>F(A)</math>.

Pour un nombre de nœuds fixé, les arbres minimisant <math>F</math> sont les arbres binaires complets (c'est-à-dire ceux dont toutes les feuilles sont au dernier ou à l'avant-dernier niveau). En effet, dans un arbre <math>A</math> non complet, il existe une feuille de profondeur <math>h</math> et une feuille de profondeur au plus <math>h-2</math>. En raccrochant la première feuille à la seconde, on obtient un arbre <math>A'</math> tel que <math>F(A') < F(A)</math>.

La fonction <math>F</math> prend la même valeur pour tous les arbres binaires complets à <math>n!</math> feuilles. Soit <math>A</math> l'un d'entre eux et <math>h</math> sa hauteur. Toutes les feuilles sont de profondeur au moins <math>h-1</math>, donc la profondeur moyenne des feuilles est au moins <math>h-1 = \Omega(n\,\log n)</math> (en utilisant à nouveau la propriété <math>2^h\geq n!</math>).
}}

Pour certains types de données (entiers, chaînes de caractères de taille bornée), il existe cependant des algorithmes plus efficaces au niveau du temps d'exécution, comme le [[tri comptage]] ou le [[tri par base]]. Ces algorithmes n'utilisent pas la comparaison entre éléments (la borne ''n·log(n)'' ne s'applique donc pas pour eux) mais nécessitent des hypothèses sur les objets à trier. Par exemple, le tri comptage et le tri par base s'appliquent à des entiers que l'on sait appartenir à l'ensemble [1, ''m''] avec comme hypothèse supplémentaire pour le tri par base que ''m'' soit une puissance de 2 (c’est-à-dire de la forme 2<sup>k</sup>).

== Critères de classification ==
=== Tri en place ===
Un tri est dit ''en place'' s'il n'utilise qu'un nombre très limité de variables et qu’il modifie directement la structure qu’il est en train de trier. Ceci nécessite l’utilisation d'une structure de donnée adaptée (un tableau par exemple). Ce caractère peut être très important si on ne dispose pas de beaucoup de mémoire.

Toutefois, on ne déplace pas, en général, les données elles-mêmes, mais on modifie seulement des références (ou [[pointeur (programmation)|pointeurs]]) vers ces dernières.

=== Tri stable ===
Un tri est dit ''stable'' s'il préserve l’ordonnancement initial des éléments que l'ordre considère comme égaux. Pour définir cette notion, il est nécessaire que la collection à trier soit ordonnancée d'une certaine manière (ce qui est souvent le cas pour beaucoup de [[structure de données|structures de données]], par exemple pour les listes ou les tableaux).

{{exemple | Définissons la relation d'ordre <math>\preccurlyeq</math> définie sur les couples d'entiers par <math>(a,b)\preccurlyeq(c,d)</math> ssi <math>a\leq c</math>, qui permet de trier deux couples selon leur première valeur.

Soit <math>L = [ (4, 1) ; (3, 2) ; (3, 3) ; (5, 4) ]</math> une liste de couples d'entiers que l'on souhaite trier selon la relation <math>\preccurlyeq</math> préalablement définie.

Puisque <math>(3,2)</math> et <math>(3,3)</math> sont égaux pour la relation <math>\preccurlyeq</math>, appeler un algorithme de tri avec <math>L</math> en entrée peut mener à deux sorties différentes :
* <math>L_1 = [ (3, 2) ; (3, 3) ; (4, 1) ; (5, 4) ]</math>  
* <math>L_2 = [ (3, 3) ; (3, 2) ; (4, 1) ; (5, 4) ]</math> 

<math>L_1</math> et <math>L_2</math> sont toutes les deux triées selon <math>\preccurlyeq</math>, mais seule <math>L_1</math> conserve l'ordre relatif. Dans <math>L_2</math>, <math>(3,3)</math> apparaît avant <math>(3,2)</math>, d'où un algorithme de tri qui aurait pris <math>L</math> en entrée et renvoyé <math>L_2</math> en sortie serait instable.
}}

Les algorithmes de tri instables peuvent être retravaillés spécifiquement afin de les rendre stables, cependant cela peut être aux dépens de la rapidité et/ou peut nécessiter un espace mémoire supplémentaire.

Parmi les algorithmes listés plus bas, les tris stables sont : le [[tri à bulles]], le [[tri par insertion]] et le [[tri fusion]]. Les autres algorithmes nécessitent <math>O(n)</math> mémoire supplémentaire pour stocker l'ordre initial des éléments.

=== Tri interne et externe ===
Un tri interne s'effectue entièrement en mémoire centrale (RAM) tandis qu'un [[algorithme de tri externe|tri externe]] utilise des fichiers sur une [[mémoire de masse]] pour trier des volumes trop importants pour pouvoir tenir en mémoire centrale<ref>{{lien web | auteur =Iluju Kiringa| éditeur =
School of Electrical Engineering and Computer Science | titre = Tri externe |  url=http://www.site.uottawa.ca/~kiringa/courses10/csi3530/ch13_extsort_csi3530-10.ppt}}</ref>. Certains types de tris, comme le [[tri fusion]] ou les tris par distribution, s'adaptent facilement à l'utilisation de mémoire externe. D'autres algorithmes, à l'inverse, accèdent aux données de telle sorte qu'ils ne se prêtent pas à cet usage car cela nécessiterait d'effectuer constamment des lectures/écritures entre les mémoires principale et externe.

=== Tri parallèle ===
Certains algorithmes permettent d'exploiter les capacités [[multitâche]]s de la machine<ref>{{article | 
auteur1 = David R. Helman | 
auteur2 = Joseph F. JáJá| 
auteur3 = David A. Bader|
titre= A New Deterministic Parallel Sorting Algorithm with an Experimental Evaluation |
périodique = ACM J. Exp. Algorithmics |
volume = 3|
numéro = 4 |
année = 1998|
lire en ligne =http://www.umiacs.umd.edu/research/EXPAR/papers/3670.html}}</ref>. Notons également que certains algorithmes, notamment ceux qui fonctionnent par insertion, peuvent être lancés sans connaître l'intégralité des données à trier ; on peut alors trier et produire les données à trier en parallèle.

== Comparaison des algorithmes ==
Le tableau ci-dessous permet de comparer différents algorithmes de tri procédant par comparaisons. <math>n</math> y représente le nombre d'éléments à trier. Toutes les complexités doivent être interprétées à l'aide d'un [[Comparaison_asymptotique#La_famille_de_notations_de_Landau_O.2C_o.2C_.CE.A9.2C_.CF.89.2C_.CE.98.2C_.7E|grand O de Landau]]. Il est supposé que les opérations élémentaires comme les comparaisons et les échanges peuvent être effectués en temps constant.

{|class="wikitable sortable centre"
|+ Tableau comparatif des tris procédant par comparaisons
! Nom !! Cas optimal !! Cas moyen !! Pire des cas !! Complexité spatiale !! Stable
<!-- Signification des index pour le classement
     00 = constant
     05 = log n
     10 = n^c, 0 < c < 1
     15 = n
     20 = n*log n ou log n!
     23 = n*(log n)^2 ou n^c, 1 < c < 2
     25 = n^2
     30 = n^c, c > 2
     40 = c^n, c > 1
     45 = n!
     50 = autres -->
|- align="center"
| [[Tri rapide]]
|style="background:#dfd"| {{Sort|20|<math>n \log n</math>}}
|style="background:#dfd"| {{Sort|20|<math>n \log n</math>}}
|style="background:#fdd"| {{Sort|25|<math>n^2</math>}}
|style="background:#ffd"| {{Sort|05|<math>\log n</math> en moyenne, <math>n</math> dans le pire des cas ;<br/> variante de Sedgewick : <math>\log n</math> dans le pire des cas}}
|style="background:#fdd"| {{Sort|1|Non}}
|- align="center"
| [[Tri fusion]]
|style="background:#dfd"| {{Sort|20|<math>n \log n</math>}}
|style="background:#dfd"| {{Sort|20|<math>n \log n</math>}}
|style="background:#dfd"| {{Sort|20|<math>n \log n</math>}}
|style="background:#fdd"| {{Sort|15|<math>n</math>}}
|style="background:#dfd"| {{Sort|0|Oui}}
|- align="center"
| [[Tri par tas]]
|style="background:#dfd"| {{Sort|20|<math>n \log n</math>}}
|style="background:#dfd"| {{Sort|20|<math>n \log n</math>}}
|style="background:#dfd"| {{Sort|20|<math>n \log n</math>}}
|style="background:#dfd"| {{Sort|00|<math>1</math>}}
|style="background:#fdd"| {{Sort|1|Non}}
|- align="center"
| [[Tri par insertion]]
|style="background:#dfd"| {{Sort|15|<math>n</math>}}
|style="background:#fdd"| {{Sort|25|<math>n^2</math>}}
|style="background:#fdd"| {{Sort|25|<math>n^2</math>}}
|style="background:#dfd"| {{Sort|00|<math>1</math>}}
|style="background:#dfd"| {{Sort|0|Oui}}
|- align="center"
| [[Introsort]]
|style="background:#dfd"| {{Sort|20|<math>n \log n</math>}}
|style="background:#dfd"| {{Sort|20|<math>n \log n</math>}}
|style="background:#dfd"| {{Sort|20|<math>n \log n</math>}}
|style="background:#ffd"| {{Sort|05|<math>\log n</math>}}
|style="background:#fdd"| {{Sort|1|Non}}
|- align="center"
| [[Tri par sélection]]
|style="background:#fdd"| {{Sort|25|<math>n^2</math>}}
|style="background:#fdd"| {{Sort|25|<math>n^2</math>}}
|style="background:#fdd"| {{Sort|25|<math>n^2</math>}}
|style="background:#dfd"| {{Sort|00|<math>1</math>}}
|style="background:#fdd"| {{Sort|1|Non}}
|- align="center"
| [[Timsort]]
|style="background:#dfd"| {{Sort|15|<math>n</math>}}
|style="background:#dfd"| {{Sort|20|<math>n \log n</math>}}
|style="background:#dfd"| {{Sort|20|<math>n \log n</math>}}
|style="background:#fdd"| {{Sort|15|<math>n</math>}}
|style="background:#dfd"| {{Sort|0|Oui}}
|- align="center"
| [[Tri de Shell]]
|style="background:#dfd"| {{Sort|15|<math>n</math>}}
|style="background:#ffd"| {{Sort|23|<math>n \log^2 n</math><br />ou<br /><math>n^{3/2}</math>}}
|style="background:#ffd"| {{Sort|23|<math>n \log^2 n</math> pour la meilleure<br/> suite d'espacements connue}}
|style="background:#dfd"| {{Sort|00|<math>1</math>}}
|style="background:#fdd"| {{Sort|1|Non}}
|- align="center"
| [[Tri à bulles]]
|style="background:#dfd"| {{Sort|15|<math>n</math>}}
|style="background:#fdd"| {{Sort|25|<math>n^2</math>}}
|style="background:#fdd"| {{Sort|25|<math>n^2</math>}}
|style="background:#dfd"| {{Sort|00|<math>1</math>}}
|style="background:#dfd"| {{Sort|0|Oui}}
|- align="center"
| [[Tri arborescent]]
|style="background:#dfd"| {{Sort|20|<math>n \log n</math>}}
|style="background:#dfd"| {{Sort|20|<math>n \log n</math>}}
|style="background:#dfd"| {{Sort|20|<math>n \log n</math> (arbre équilibré)}}
|style="background:#fdd"| {{Sort|15|<math>n</math>}}
|style="background:#dfd"| {{Sort|0|Oui}}
|- align="center"
| [[Smoothsort]]
|style="background:#dfd"| {{Sort|15|<math>n</math>}}
|style="background:#dfd"| {{Sort|20|<math>n \log n</math>}}
|style="background:#dfd"| {{Sort|20|<math>n \log n</math>}}
|style="background:#dfd"| {{Sort|00|<math>1</math>}}
|style="background:#fdd"| {{Sort|1|Non}}
|- align="center"
| [[Tri cocktail]]
|style="background:#dfd"| {{Sort|15|<math>n</math>}}
|style="background:#fdd"| {{Sort|25|<math>n^2</math>}}
|style="background:#fdd"| {{Sort|25|<math>n^2</math>}}
|style="background:#dfd"| {{Sort|00|<math>1</math>}}
|style="background:#dfd"| {{Sort|0|Oui}}
|- align="center"
| [[Tri à peigne]]
|style="background:#dfd"| {{Sort|15|<math>n</math>}}
|style="background:#dfd"| {{Sort|15|<math>n \log n</math>}}
|style="background:#fdd"| {{Sort|25|<math>n^2</math>}}
|style="background:#dfd"| {{Sort|00|<math>1</math>}}
|style="background:#fdd"| {{Sort|1|Non}}
|- align="center"
| [[Tri pair-impair]]
|style="background:#dfd"| {{Sort|15|<math>n</math>}}
|style="background:#fdd"| {{Sort|25|<math>n^2</math>}}
|style="background:#fdd"| {{Sort|25|<math>n^2</math>}}
|style="background:#dfd"| {{Sort|00|<math>1</math>}}
|style="background:#dfd"| {{Sort|0|Oui}}
|}

== Exemples d'algorithmes de tri ==
=== Tris par comparaison ===
==== Algorithmes rapides ====

* [[Tri fusion]] (''merge sort'') − <math>T(n)=O(n \log n)</math> dans tous les cas ; stable ; pas en place par défaut<ref name="f/t">On peut faire du tri fusion un tri en place et toujours en <math>O(n \log n)</math>, mais l'algorithme effectue plus de copies et est plus compliqué à programmer</ref>.
*: Cet algorithme repose sur le principe [[diviser pour régner (informatique)|« diviser pour régner »]]. Pour une entrée donnée, l'algorithme la divise en deux parties de tailles similaires, trie chacune d'entre elles en utilisant le même algorithme, puis fusionne les deux parties triées. Il se prête aussi bien à des implémentations sur listes que sur tableaux. Il est utilisé en particulier par l'algorithme hybride [[Timsort]].
* [[Tri rapide]] (''quicksort'') − <math>T(n)=O(n \log n)</math> en moyenne et dans le meilleur des cas, <math>T(n)=O(n^2)</math> dans le pire des cas ; instable ; en place dans la variante de Sedgewick.
*: Cette méthode repose sur le principe [[diviser pour régner (informatique)|« diviser pour régner »]]. Une valeur est choisie comme pivot et les éléments plus petits que le pivot sont dissociés, par échanges successifs, des éléments plus grands que le pivot ; chacun de ces deux sous-ensembles est ensuite trié de la même manière. On peut rendre la complexité quasiment indépendante des données en utilisant un pivot aléatoire ou en appliquant au tableau une [[permutation aléatoire]] avant de le trier.
* [[Tri par tas]] (''heap sort'') − <math>T(n)=O(n \log n)</math> dans tous les cas ; en place mais instable.
*: Il s'agit d'une amélioration du [[tri par sélection]]. L'idée est la même (insérer les éléments un à un dans une structure déjà triée), mais l'algorithme utilise une structure de [[tas (informatique)|tas]], souvent implémentée au moyen d'un tableau. {{pas clair|Cet algorithme fonctionne très bien en conjonction avec le tri rapide. En effet, il est efficace quand on soupçonne que les données sont proches du pire cas (quadratique) du tri rapide.|date=juin 2021}}
* [[Introsort]] − <math>T(n)=O(n \log n)</math> dans tous les cas ; instable mais en place.
*: Il s'agit d'un hybride du [[tri rapide]] et du [[tri par tas]].
* [[Tri arborescent]] − <math>T(n)=O(n \log n)</math> en moyenne, <math>T(n)=O(n^2)</math> dans le pire des cas, <math>T(n)=O(n)</math> dans le meilleur des cas. ; ni stable ni en place.
*: L'idée est d'insérer les éléments un à un dans un [[arbre binaire de recherche]], puis de lire l'arbre selon un parcours en profondeur. Ce tri est un des plus lents (parmi les tris rapides) et un des plus gourmands en mémoire à cause de la structure d'arbre binaire à manipuler. Il est possible de le rendre {{comment | quasi linéaire dans tous les cas}} en maintenant un [[arbre équilibré]] (''c.f.'' [[Arbre AVL]]).
* [[Smoothsort]] − <math>T(n)=O(n \log n)</math> en moyenne et dans le pire des cas, <math>T(n)=O(n)</math> dans le meilleur des cas ; en place mais instable.
*: Tri inspiré du [[tri par tas]], mais qui utilise un {{quoi | arbre non inversé}}. Ce tri est très rapide pour les ensembles déjà presque triés.
* [[Tri à peigne]] (''comb sort'') − <math>T(n)=O(n)</math> dans le meilleur des cas, <math>T(n)=O(n \log n)</math> en moyenne et <math>T(n)=O(n^2)</math> dans le pire des cas ; instable mais en place.
*: Il s'agit d'une variante plus efficace du [[tri à bulles]], ne comparant pas uniquement des éléments consécutifs. On peut dire qu'il est au tri à bulles ce que le [[tri de Shell]] est au [[tri par insertion]].

Pour un algorithme de tri donné instable, il est facile d'en obtenir une variante stable en utilisant un tableau supplémentaire pour mémoriser l'ordre initial des éléments. L'algorithme obtenu n'est toutefois pas en place.

==== Algorithmes moyennement rapides ====
* [[Tri de Shell]] (''shell sort'') − <math>T(n)=O(n \log^2n)</math> pour la série de pas <math>2^p3^q</math> et <math>T(n)=O(n^{3/2})</math> pour la série de pas <math>2^k-1</math> ; instable ; en place.
*: Ce tri repose sur le [[tri par insertion]] des sous-suites de l'entrée obtenues en prenant les éléments espacés d'un pas constant, pour une suite de pas prédéfinie. La complexité varie selon le choix de cette suite. On ne connaît pas de série donnant  <math>O(n \log n)</math>.

Pour un algorithme de tri donné instable, il est facile d'en obtenir une variante stable en utilisant un tableau supplémentaire pour mémoriser l'ordre initial des éléments. Il peut être rendu stable, mais de préférence en travaillant sur des listes.

* [[Tri par insertion]] − <math>T(n) = O(n^2)</math> en moyenne et dans le pire des cas, <math>T(n)=O(n)</math> dans le meilleur des cas ; stable et en place.
*: C'est le tri souvent utilisé naturellement pour trier des cartes à jouer : les valeurs sont insérées les unes après les autres dans une liste triée (initialement vide). C'est souvent le plus rapide et le plus utilisé pour trier des entrées de petite taille. Il est également efficace pour des entrées déjà presque triées.
* [[Tri à bulles]] − <math>T(n) = O(n^2)</math> en moyenne et dans le pire des cas, <math>T(n)=O(n)</math> dans le meilleur des cas ; stable et en place. 
*: L'algorithme consiste à parcourir l'entrée du début à la fin et, pour chaque couple d'éléments consécutifs, à les intervertir s'ils sont mal ordonnés. Cette opération est répétée jusqu'à ce que la structure soit triée (aucune interversion lors du dernier passage). Cet algorithme est peu efficace et rarement utilisé en pratique ; son intérêt est principalement pédagogique.
* [[Tri cocktail]] − <math>T(n) = O(n^2)</math> en moyenne et dans le pire des cas, <math>T(n)=O(n)</math> dans le meilleur des cas ; stable et en place. 
*: Il s'agit d'une variante du tri à bulles dans laquelle l'entrée est alternativement parcourue dans les deux sens. S'il permet de traiter de manière plus efficace quelques cas problématiques pour le tri à bulles, il reste essentiellement similaire à ce dernier et l'intérêt est encore une fois principalement pédagogique.
* [[Tri pair-impair]] − <math>T(n) = O(n^2)</math> en moyenne et dans le pire des cas, <math>T(n)=O(n)</math> dans le meilleur des cas ; stable et en place. 
*: Il s'agit d'une variante du tri à bulles, qui procède en comparant successivement tous les éléments d'index pairs avec les éléments d'index impairs qui les suivent, puis inversement. On va ainsi commencer en comparant le premier élément au second, le troisième au quatrième, etc., puis l'on comparera le second élément au troisième, le quatrième au cinquième etc. L'opération est répétée jusqu'à ce que la structure soit triée.

==== Algorithmes lents ====
Ces algorithmes ont une complexité asymptotique en <math>O(n^2)</math> et sont par conséquent considérés comme lents pour des entrées dont la taille est de plus de quelques dizaines d'éléments.

* [[Tri par sélection]] − <math>T(n) = O(n^2)</math> dans tous les cas ; sur place ; instable par défaut (peut être rendu stable, mais de préférence en travaillant sur des listes).
*: Il s'agit, à chaque itération, d'identifier le plus petit des éléments qui ne sont pas encore triés, et de l'échanger avec le premier de ceux-ci. Ce tri est rapide pour des petites entrées, et se code de manière concise.

==== Algorithmes très lents ====
Ces algorithmes ont une complexité asymptotique moins bonne que <math>O(n^2)</math>, qui est la complexité des algorithmes les plus intuitifs.

* [[Tri stupide]] (''bogosort'') − Ne termine pas dans le pire des cas, <math>T(n) = O(n!)</math> en moyenne et <math>T(n)=O(n)</math> dans le meilleur des cas ; instable mais en place. 
*: Le tri stupide consiste à vérifier si les éléments sont ordonnés et s'ils ne le sont pas à mélanger aléatoirement les éléments, puis à répéter l'opération. 
* [[Tri faire-valoir]] ({{anglais|stooge sort}}) - <math>T(n) = O(n^{\frac{\log 3}{\log 1,5}})</math> soit approximativement <math>O(n^{2,71})</math> ; {{refnec|instable et pas en place}}.
*: Ce tri consiste à échanger si nécessaire le premier et le dernier élément, puis à trier récursivement les deux premiers tiers, puis les deux derniers, puis de nouveau les deux premiers du tableau.

=== Tris utilisant la structure des données ===
* [[Tri comptage]] ou [[tri par dénombrement]] (''counting sort'') : Algorithme linéaire, T(n) = O(n), stable mais nécessite l'utilisation d'une seconde liste de même longueur que la liste à trier. Son utilisation relève de la condition que les valeurs à trier sont des entiers naturels dont on connaît les extrema ;
* [[Tri par base]] (''radix sort'') : c'est aussi un tri linéaire dans certaines conditions (moins restrictives que pour le tri par comptage), T(n) = O(n), stable mais nécessite aussi l'utilisation d'une seconde liste de même longueur que la liste à trier ;
* [[Tri par paquets]] (''bucket sort'') : Stable et en complexité linéaire -- <math>T(n) = O(n)</math>, part de l'hypothèse que les données à trier sont réparties de manière uniforme sur un intervalle réel <math>[a, b[</math>.

=== Tris externes ===
{{article détaillé|algorithme de tri externe}}

Les algorithmes de tri doivent aussi être adaptés en fonction des configurations informatiques sur lesquelles ils sont utilisés. Dans les exemples cités plus haut, on suppose que toutes les données sont présentes en mémoire centrale (ou accessibles en [[mémoire virtuelle]]). La situation se complexifie si l'on veut trier des volumes de données supérieurs à la mémoire centrale disponible (ou si l'on cherche à améliorer le tri en optimisant l'utilisation de la hiérarchie de mémoire).

Ces algorithmes sont souvent basés sur une approche assez voisine de celle du [[tri fusion]]. Le principe est le suivant :
* découpage du volume de données à trier en sous-ensembles de taille inférieure à la mémoire rapide disponible ;
* tri de chaque sous-ensemble en mémoire centrale pour former des « monotonies » (sous-ensembles triés) ;
* interclassement des monotonies.

== Choix empirique d'un algorithme de tri ==
Beaucoup d'algorithmes existent, mais certains sont bien plus utilisés que d'autres en pratique. Le [[tri par insertion]] est souvent plébiscité pour des données de petite taille, tandis que des algorithmes asymptotiquement efficaces, comme le [[tri fusion]], le [[tri par tas]] ou [[quicksort]], seront utilisés pour des données de plus grande taille.

Il existe des implémentations finement optimisées, qui sont souvent des [[algorithme hybride|algorithmes hybrides]]. [[Timsort]] utilise ainsi à la fois les méthodes de [[tri fusion]] et de [[tri par insertion]], et est utilisé entre autres par [[Android]], [[java (langage)|Java]] et [[python (langage)|Python]] ; [[Introsort]], qui combine [[quicksort]] et [[tri par tas]], est utilisé dans certaines implémentations du tri [[C++]].

La comparaison empirique d'algorithmes n'est pas aisée dans la mesure où beaucoup de paramètres entrent en compte : taille de données, ordre des données, matériel utilisé, taille de la mémoire vive, etc. Par exemple, les essais effectués sur des données tirées aléatoirement ne représentent pas forcément très fidèlement les comportements obtenus avec des données réelles.

=== Accès à la mémoire vive ===
Afin de comparer différents algorithmes, il est important de prendre en compte la taille des données à trier ainsi que la quantité de mémoire vive disponible. Lorsqu'il n'y a plus assez de mémoire vive pour stocker les données, l'ordinateur aura recours à l'usage de mémoire externe, ce qui résulte en des temps d'accès nettement plus longs.

Dans cette situation, les algorithmes qui travaillent successivement sur des parties de plus petites tailles de l'entrée (qui seront par exemple fusionnées par la suite) auront tendance à mieux fonctionner que des algorithmes comme [[quicksort]] qui effectueront plus d'accès à la mémoire externe.

Il est également possible d'éviter de telles situations, par exemple en associant aux données à trier des clés plus petites, et en triant directement ces clés en mémoire vive. Lorsque la taille des données est vraiment conséquente, un [[algorithme de tri externe]] sera utilisé afin de minimiser le nombre d'accès à la mémoire externe.

== Problèmes liés ==
Parmi les problèmes proches du tri, on peut mentionner le {{lien|trad=Partial sorting|fr=tri partiel}}, qui consiste, pour <math>k</math> fixé, à trier les <math>k</math> plus petits éléments, ou le [[algorithme de sélection|problème de sélection]], qui consiste à trouver le <math>k</math>-ième plus petit élément de l'entrée. Bien que trier l'entrée en intégralité permette de résoudre ces problèmes, il existe des solutions plus subtiles et moins coûteuses. C'est le cas par exemple de [[quickselect]], qui possède des similitudes avec le [[tri rapide]].

À l'inverse, on peut chercher à construire des algorithmes qui mélangent de manière aléatoire l'entrée qui leur est donnée ; c'est le cas par exemple du [[mélange de Fisher-Yates]].

Un autre problème est de trier un tableau qui est déjà presque trié (c'est le cas avec les [[mégadonnées]] où les algorithmes conventionnels sont disqualifiés).  Cela peut réhabiliter des algorithmes comme le [[tri par insertion]].

== Histoire ==
La création de la première [[Routine (informatique)|routine]] de tri est attribuée à [[Betty Holberton]], lors de la seconde guerre mondiale<ref>{{chapitre |nom=Holberton|prénom=F.E.|titre=Application of Automatic Coding to Logical Processes|titre ouvrage=Symposium Automatic Programming for DigitalComputers, Office of Naval Research, Dept. of the Navy | date = Oct. 1954|passage=34-39}}</ref>{{,}}<ref>{{chapitre|nom=Hopper|prénom=Grace|titre=Automatic Coding for Digital Computers|titre ouvrage=High Speed Computer Conference (Louisiana State University)| date =  February 1995|éditeur=Remington Rand }}</ref>.

== Annexes ==
=== Notes et références ===
{{Références}}
=== Bibliographie ===
* {{Cormen3fr}}
* {{Ouvrage
| langue=fr
| prénom1=Christine
| nom1=Froidevaux
| prénom2=Marie-Claude
| nom2=Gaudel
| prénom3=Michèle
| nom3=Soria
| titre=Types de données et algorithmes
| éditeur=McGraw-Hill
| année=1990
| pages totales=577
| isbn=978-2-7042-1217-0
| isbn10=2-7042-1217-1
| bnf=350707531
| lire en ligne=https://www.lri.fr/~mcg/PDF/FroidevauxGaudelSoria.pdf
| numéro chapitre=16
}}

=== Liens externes ===
* [http://www.herve.name/pmwiki.php/Main/AlgoTri Mémoire de synthèse sur les algorithmes de tri]
* [http://www.dailly.info/-030-Algorithmes-de-Tri- Dossier sur les algorithmes de tri et leur complexité (et implémentation en divers langages)]
* [http://thomas.baudel.name/Visualisation/VisuTri/index.fr.html Illustration dynamique de plusieurs tris (nécessite Java)]
* {{en}} [https://www.toptal.com/developers/sorting-algorithms Illustration dynamique de plusieurs tris ]
* {{lien web|url=https://imgur.com/gallery/voutF|titre=Sorting Algorithms Visualized|langue=en|description=Visualisation de différents tris à l’aide de couleurs}}
* [http://interstices.info/tri Sur le site Interstices, document sur les algorithmes de tri avec une applet Java]
{{Palette|Algorithmes de tri|Informatique théorique}}{{Portail|informatique théorique}}

[[Catégorie:Algorithme de tri| ]]