Voir la source de Tri par comparaison

{{Problèmes multiples|à wikifier=novembre 2023|à délister=mars 2024|à déjargoniser=mars 2024|à sourcer=mars 2024|à recycler=mars 2024|contenu à préciser=mars 2024}}
[[Fichier:Balance_à_tabac_1850.JPG|droite|vignette| Le tri d'un ensemble de poids non étiquetés par poids en utilisant uniquement une balance nécessite un algorithme de tri par comparaison.]]
Un '''tri par comparaison''' est un type d'[[algorithme de tri]] qui lit uniquement les éléments de la liste via une seule opération de comparaison abstraite (souvent un opérateur "inférieur ou égal à" ou une [[comparaison trilatérale]]) qui détermine lequel des deux éléments doit apparaître en premier dans le liste triée finale. La seule exigence est que l'opérateur soit une [[:en:Weak_ordering#Total_preorders|relation de préordre]] total, avec:

# si ''a'' ≤ ''b'' et ''b'' ≤ ''c'' alors ''a'' ≤ ''c'' (transitivité)
# pour tout ''a'' et ''b'', ''a'' ≤ ''b'' ou ''b'' ≤ ''a'' ([[:en:Connected_relation|connexité]]).

Il est possible que ''a'' ≤ ''b'' et ''b'' ≤ ''a''; dans ce cas, l'un ou l'autre peut apparaître en premier dans la liste triée. Dans un [[Algorithme de tri|tri stable]], l’ordonnancement initial détermine l'ordre des éléments triés.

Une métaphore pour réfléchir aux types de comparaison est que quelqu'un possède un ensemble de poids non étiquetés et [[Balance (instrument)|une balance]]. Leur objectif est d'aligner les poids en fonction de leur poids sans aucune information sauf celle obtenue en plaçant deux poids sur la balance et en voyant lequel est le plus lourd (ou s'ils pèsent le même poids).

== Exemples ==
[[Fichier:Sorting_quicksort_anim.gif|vignette| [[Tri rapide]] en action sur une liste de nombres. Les lignes horizontales sont des valeurs pivots.]]
Parmi les types de comparaison les plus connus :

* [[Tri rapide]]
* [[Tri par tas|Tri en tas]]
* [[Tri de Shell]]
* [[Tri fusion|Tri par fusion]]
* [[Introsort]]
* [[Tri par insertion]]
* [[Tri par sélection|Tri de sélection]]
* [[Tri à bulles]]
* [[Tri pair-impair|Tri impair-pair]]
* [[Tri cocktail]]
* [[:en:Cycle_sort|Tri par cycles]]
* [[:en:Merge-insertion_sort|Tri par fusion-insertion]]
* [[Smoothsort|Tri en douceur]]
* [[Timsort|Tri Tim]]
* [[:en:Block_sort|Tri par blocs]]

== Bornes et avantages des différentes techniques de tri ==
Il existe des limites fondamentales aux performances des tris par comparaison. Un tri par comparaison doit avoir [[Comparaison asymptotique|Ω]] (''n'' log ''n'') comparaisons en moyenne<ref>Cormen</ref>, qui est connue sous le nom de temps [[Complexité en temps|linéarithmique]]. C’est une conséquence du peu d’informations disponibles grâce aux seules comparaisons – ou, pour le dire autrement, de la vague structure algébrique d’ensembles totalement ordonnés. En ce sens, le tri par fusion, le tri par tas et [[Introsort]] sont optimaux en termes de nombre de comparaisons qu'ils doivent effectuer, bien que cette métrique néglige les autres opérations. Les tris sans comparaison (tels que les exemples on trouve ci-dessous) peuvent atteindre des performances [[Comparaison asymptotique|O]](''n'') en utilisant des opérations autres que les comparaisons, leur permettant de contourner cette borne inférieure (en supposant que les éléments sont de taille constante).

Un algorithme de tri comparatif peut s'exécuter plus rapidement sur certaines listes ; de nombreux tris adaptatifs tels que le [[tri par insertion]] s'exécutent en un temps O(''n'') sur une liste déjà triée ou presque triée. La borne inférieure [[Comparaison asymptotique|Ω]] (''n'' log ''n'') s'applique uniquement au cas dans lequel la liste peut être dans n'importe quel ordre.

Les mesures réelles de la complexité de tri devront  prendre en compte la capacité de certains algorithmes à utiliser de manière optimale la [[Mémoire vive|mémoire vive de l'ordinateur]], ou l'algorithme peut bénéficier de méthodes de tri dans lesquelles les données triées commencent à apparaître à l'utilisateur avant la fin du tri par opposition aux méthodes de tri où aucune sortie n'est disponible tant que la liste entière n'est pas triée.

Malgré ces limitations, les tris par comparaison offrent le contrôle de la fonction de comparaison qui permet de trier de nombreux types de données différents et de contrôler finement la manière dont la liste est triée. Par exemple, inverser le résultat de la fonction de comparaison permet de trier la liste à l'envers ; et on peut trier une liste de [[Uplet|tuples]] par [[ordre lexicographique]] en créant simplement une fonction de comparaison qui compare chaque partie :
 '''function''' tupleCompare((lefta, leftb, leftc), (righta, rightb, rightc))
     '''if''' lefta ≠ righta
         '''return''' compare(lefta, righta)
     '''else if''' leftb ≠ rightb
         '''return''' compare(leftb, rightb)
     '''else'''
         '''return''' compare(leftc, rightc)
Les tris par comparaison s'adaptent généralement plus facilement aux ordres complexes tels que l'ordre des [[Virgule flottante|nombres à virgule flottante]]. Aussi, dès qu’une fonction de comparaison est fixée, n’importe quel tri par comparaison peut être utilisé; les tris sans comparaison nécessitent généralement des versions adaptées pour chaque type de données.

Cette flexibilité, ainsi que l'efficacité des algorithmes de tri par comparaison ci-dessus sur les ordinateurs modernes, ont conduit à la popularité des tris par comparaison dans la plupart des travaux pratiques.

== Alternatives ==
Certains problèmes de tri admettent une solution strictement plus rapide que la borne {{Formule|Ω(''n'' log ''n'')}} du tri par comparaison grâce à l'utilisation des [[Algorithme de tri|tris sans comparaison]] ; un exemple est le [[tri de nombres entiers]], où toutes les clés sont des entiers. Lorsque les clés forment une petite plage (en comparaison avec {{Mvar|n}}), le [[tri comptage]] est un exemple d'algorithme qui s'exécute en temps linéaire. D'autres algorithmes de tri d'entiers, tels que le [[tri par base]], ne sont pas asymptotiquement plus rapides que le tri par comparaison, mais peuvent être plus rapides en pratique.

Le problème du tri de paires de nombres par leur somme n'est pas non plus soumis à la borne {{Formule|Ω(''n''² log ''n'')}}; l'algorithme le plus connu prend toujours un temps {{Formule|O(''n''² log ''n'')}}, mais seulement {{Formule|O(''n''²)}} comparaisons.

== Nombre de comparaisons nécessaires pour trier une liste ==
<div class="thumb tright">
<div class="thumbinner" style="width:360px;">
{| class="wikitable" style="margin-left:auto; margin-right:auto;"
!''n''
!<math>\left\lceil\log_2(n!)\right\rceil</math>
!Minimum
|-
| style="text-align:right;" |1
| style="text-align:right;" |0
| style="text-align:center;" |0
|-
| style="text-align:right;" |2
| style="text-align:right;" |1
| style="text-align:center;" |1
|-
| style="text-align:right;" |3
| style="text-align:right;" |3
| style="text-align:center;" |3
|-
| style="text-align:right;" |4
| style="text-align:right;" |5
| style="text-align:center;" |5
|-
| style="text-align:right;" |5
| style="text-align:right;" |7
| style="text-align:center;" |7
|-
| style="text-align:right;" |6
| style="text-align:right;" |10
| style="text-align:center;" |10
|-
| style="text-align:right;" |7
| style="text-align:right;" |13
| style="text-align:center;" |13
|-
| style="text-align:right;" |8
| style="text-align:right;" |16
| style="text-align:center;" |16
|-
| style="text-align:right;" |9
| style="text-align:right;" |19
| style="text-align:center;" |19
|-
| style="text-align:right;" |10
| style="text-align:right;" |22
| style="text-align:center;" |22
|-
| style="text-align:right;" |11
| style="text-align:right;" |26
| style="text-align:center;" |26
|-
| style="text-align:right;" |12
| style="text-align:right;" |29
| style="text-align:center;" |30
|-
| style="text-align:right;" |13
| style="text-align:right;" |33
| style="text-align:center;" |34
|-
| style="text-align:right;" |14
| style="text-align:right;" |37
| style="text-align:center;" |38<ref name="Peczarski2004">{{article | langue=en | prénom=Marcin | nom=Peczarski | titre=New results in minimum-comparison sorting | périodique=Algorithmica | volume=40 | numéro=2 | passage=133–145 | date=24 mai 2004 | doi=10.1007/s00453-004-1100-7}}.</ref>
|-
|-
| style="text-align:right;" |15
| style="text-align:right;" |41
| style="text-align:center;" |42<ref name="Peczarski2007">{{Article| langue=en| nom1=Peczarski|prénom1=Marcin|titre=The Ford-Johnson algorithm is still unbeaten for less than 47 elements|périodique=Inf. Process. Lett.|volume=101|numéro=3|pages=126–128|année=2007|doi=10.1016/j.ipl.2006.09.001}}</ref>{{,}}<ref name="ChengLiuWang2007">{{Article|langue=zh|auteur1=Cheng|prénom1=Weiyi|auteur2=Liu|prénom2=Xiaoguang|auteur3=Wang|prénom3=Gang|auteur4=Liu|prénom4=Jing|titre=最少比较排序问题中S（15）和S（19）的解决|périodique=Journal of Frontiers of Computer Science and Technology|volume=1|numéro=3|pages=305–313|date=October 2007|lire en ligne=http://fcst.ceaj.org/EN/abstract/abstract47.shtml}}</ref>
|-
| style="text-align:right;" |16
| style="text-align:right;" |45
| style="text-align:center;" |46
|-
| style="text-align:right;" |17
| style="text-align:right;" |49
| style="text-align:center;" |50<ref name="Stober2023">{{article | langue=en | auteur1=Florian Stober | auteur2=Armin Weiß | titre=Lower Bounds for Sorting 16, 17, and 18 Elements | périodique=2023 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX) (conférence | année=2023 | passage=201-213 | éditeur=Society for Industrial and Applied Mathematics | doi=10.1137/1.9781611977561.ch17}}.</ref>
|-
| style="text-align:right;" |18
| style="text-align:right;" |53
| style="text-align:center;" |54<ref name="Stober2023" />
|-
| style="text-align:right;" |19
| style="text-align:right;" |57
| style="text-align:center;" |58<ref name="ChengLiuWang2007" />
|-
| style="text-align:right;" |20
| style="text-align:right;" |62
| style="text-align:center;" |62
|-
| style="text-align:right;" |21
| style="text-align:right;" |66
| style="text-align:center;" |66
|-
| style="text-align:right;" |22
| style="text-align:right;" |70
| style="text-align:center;" |71<ref name="Peczarski2004" />
|-
| style="height:5px;" |
|
|
|-
!''n''
!<math>\left\lceil\log_2(n!)\right\rceil</math>
!<math>n \log_2 n - \frac{n}{\ln 2}</math>
|-
| style="text-align:right;" |10
| style="text-align:right;" |22
| style="text-align:center;" |19
|-
| style="text-align:right;" |100
| style="text-align:right;" |525
| style="text-align:center;" |521
|-
| style="text-align:right;" |1 000
| style="text-align:right;" |8 530
| style="text-align:center;" |8 524
|-
| style="text-align:right;" |10 000
| style="text-align:right;" |118 459
| style="text-align:center;" |118 451
|-
| style="text-align:right;" |100 000
| style="text-align:right;" |1 516 705
| style="text-align:center;" |1 516 695
|-
| style="text-align:right;" |{{Nobr|1 000 000}}
| style="text-align:right;" |18 488 885
| style="text-align:center;" |18 488 874
|}
<div class="thumbcaption">Au dessus : Une comparaison de la borne inférieure <math>\left\lceil\log_2(n!)\right\rceil</math> au nombre minimum réel de comparaisons (à partir de {{OEIS2C|id=A036604}}) nécessaires pour trier une liste de n éléments (dans le pire des cas). Ci-dessous : en utilisant la [[formule de Stirling]], cette borne inférieure est bien approximative par

<math>n \log_2 n - \frac{n}{\ln 2}</math>.

.
</div>
</div>
</div>Le nombre de comparaisons nécessaires par un algorithme de tri par comparaison augmente proportionnellement à <math>n\log(n)</math>, où <math>n</math> est le nombre d'éléments à trier. Cette limite est [[:en:Asymptotic_computational_complexity|asymptotiquement serrée]].

Étant donné une liste de nombres distincts (on le suppose car il s'agit d'une analyse du pire des cas), il y a n [[factorielle]] permutations dont exactement l’une est la liste triée. L'algorithme de tri doit obtenir suffisamment d'informations à partir des comparaisons pour identifier la permutation correcte. Si l'algorithme se termine toujours après au plus <math>f(n)</math> étapes, il ne peut pas distinguer plus de <math>2^{f(n)}</math> cas car les clés sont distinctes et chaque comparaison n’a que deux résultats possibles. Donc,

: <math>2^{f(n)}\geq n!</math>, ou équivalent <math>f(n)\geq\log_2(n!).</math>

En regardant le premier <math>n/2</math> facteurs de <math>n! = n (n-1) \cdots 1</math>, on obtient

: <math>\log_2(n!) \geq \log_2\left(\left(\frac{n}{2}\right)^\frac{n}{2}\right) = \frac{n}{2} \frac{\log n}{\log 2} - \frac{n}{2} = \Theta(n \log n).</math>
: <math>\log_2(n!) = \Omega(n \log n).</math>

Cela fournit la borne inférieure. Un résultat plus précis peut être donnée par l'[[Formule de Stirling|approximation de Stirling]]. Une borne supérieure de même forme, avec le même terme dominant que la borne obtenue par l'approximation de Stirling, découle de l'existence d'algorithmes qui atteignent cette borne dans le pire des cas, comme le [[Tri fusion|tri par fusion]].

L'argument ci-dessus fournit une borne inférieure ''absolue'', plutôt que seulement asymptotique, à savoir <math>\left\lceil\log_2(n!)\right\rceil</math> comparaisons. Cette borne inférieure est assez bonne, mais elle est connue pour être inexacte. Par exemple, <math>\left\lceil\log_2(13!)\right\rceil = 33</math>, mais il a été prouvé que le nombre minimal de comparaisons pour trier 13 éléments est de 34.

Déterminer le nombre ''exact'' de comparaisons nécessaires pour trier un nombre donné d'entrées est un problème difficile de la théorie de la complexité, même pour un petit ''n'', et on ne connaît pas aucune formule simple pour la solution. Pour certaines valeurs concrètes qui ont été calculées, voir [[OEIS : A036604]].

=== Borne inférieure du nombre moyen de comparaisons ===
Une borne similaire s’applique au nombre moyen de comparaisons. En admettant que

* toutes les clés sont distinctes, c'est-à-dire que chaque comparaison donnera soit ''a'' > ''b'' soit ''a'' < ''b'', et
* l'entrée est une permutation aléatoire, choisie uniformément parmi l'ensemble de toutes les permutations possibles de ''n'' éléments,

il est impossible de savoir dans quel ordre se trouve l'entrée avec moins de {{Formule|log<sub>2</sub>(''n''!)}} comparaisons en moyenne.

Cela peut être plus facilement compris en utilisant les concepts de la [[théorie de l'information]]. L'[[entropie de Shannon]] d'une telle permutation aléatoire est {{Formule|log<sub>2</sub>(''n''!)}} bits. Puisqu’une comparaison ne peut donner que deux résultats, la quantité maximale d’informations qu’elle fournit est de 1 bit. Par conséquent, après ''k'' comparaisons, l'entropie restante de la permutation, compte tenu des résultats de ces comparaisons, est d'au moins {{Formule|log<sub>2</sub>(''n''!) − ''k''}} bits en moyenne. Pour effectuer le tri, des informations complètes sont nécessaires, l'entropie restante doit donc être égale à 0. Il s'ensuit que ''k'' doit être au moins {{Formule|log<sub>2</sub>(''n''!)}} en moyenne.

La borne inférieure dérivée de la théorie de l'information est formulée sous le nom de « borne inférieure de la théorie de l'information ». Cette borne inférieure est correcte mais n’est pas nécessairement la meilleure. Et dans certains cas, la borne inférieure de la théorie de l’information d’un problème peut même être très éloignée de la véritable borne inférieure. Par exemple, la borne inférieure (dans la théorie de l’information) de sélection  est <math>\left\lceil\log_2(n)\right\rceil</math> alors que <math>n-1</math> des comparaisons sont nécessaires dans un argument contradictoire. L'interaction entre la borne inférieure de la théorie de l'information et la véritable borne inférieure ressemble beaucoup à une fonction à valeur réelle limitant une fonction entière. Cependant, cela n’est pas tout à fait exact si l’on considère le cas moyen.

Pour découvrir ce qui se passe lors de l’analyse d’un cas moyen, il faut savoir ce que signifie le terme « moyenne » ?  Avec une certaine connaissance de la théorie de l’information, la borne inférieure de la théorie de l’information fait la moyenne sur l’ensemble de toutes les permutations. Mais tout algorithme informatique (selon ce que l’on croit actuellement) doit traiter individuellement chaque permutation du problème. Par conséquent, la borne inférieure moyenne que nous recherchons est calculée en moyenne sur tous les cas individuels.

Pour rechercher la borne inférieure relative à la non-réalisabilité des ordinateurs, nous adoptons le [[:en:Decision_tree_model|modèle d'arbre de décision]]. Reformulons un peu notre objectif. Dans l'[[:en:Decision_tree_model|arbre de décision]], la borne inférieure est  la longueur moyenne des chemins racine-feuille d'un [[arbre binaire]] à  <math>n!</math> feuilles (dans lequel chaque feuille correspond à une permutation). La longueur moyenne minimale d'un arbre de décision avec un nombre donné de feuilles est obtenue par un arbre binaire complet équilibré, car tout autre arbre binaire peut voir sa longueur de chemin réduite en déplaçant une paire de feuilles vers une position plus élevée. Avec quelques calculs, pour un arbre binaire complet équilibré avec <math>n!</math> feuilles, la longueur moyenne des chemins racine-feuille est donnée par

: <math>\frac{(2n! - 2^{\lfloor \log_2 n! \rfloor + 1}) \cdot \lceil \log_2 n! \rceil + (2^{\lfloor \log_2 n! \rfloor + 1} - n!) \cdot \lfloor \log_2 n! \rfloor}{n!} = \lceil \log_2 n! \rceil + 1 - \frac{2^{\lceil \log_2 n! \rceil}}{n!}</math>

Par exemple, pour {{Formule|1=''n'' = 3}}, la borne inférieure de la théorie de l'information pour le cas moyen est d'environ 2.58, tandis que la borne inférieure moyenne avec le [[:en:Decision_tree_model|modèle d'arbre de décision]] est de 8/3, soit environ 2.67.

Dans le cas où plusieurs éléments peuvent avoir la même clé, il n'y a pas d'interprétation statistique évidente du terme « cas moyen », donc un argument comme celui ci-dessus ne peut pas être appliqué sans formuler des hypothèses sur la distribution des clés.

=== n log n nombre maximum de comparaisons pour la taille du tableau au format 2^k ===
C'est possible calculer pour un véritable algorithme de fusion de listes triées (les tableaux sont triés en n blocs de taille 1, fusionnent en 1-1 en 2, fusionnent 2-2 en 4...).<pre>
(1) = = = = = = = =

(2) =  =  =  =   // max 1 compares (size1+size2-1), 4x repeats to concat 8 arrays with size 1 and 1
  === === === ===

(3)  =    =    // max 7 compares, 2x repeats to concat 4 arrays with size 2 and 2
   ===   === 
  =====  ===== 
  ======= =======

(4)          // max 15 compares, 1x repeats to concat 2 arrays with size 4 and 4

Formula extraction:
n = 256 = 2^8 (array size in format 2^k, for simplify)
On = (n-1) + 2(n/2-1) + 4(n/4-1) + 8(n/8-1) + 16(n/16-1) + 32(n/32-1) + 64(n/64-1) + 128(n/128-1)
On = (n-1) + (n-2) + (n-4) + (n-8) + (n-16) + (n-32) + (n-64) + (n-128)
On = n+n+n+n+n+n+n+n - (1+2+4+8+16+32+64+128)  | 1+2+4... = formula for geometric sequence Sn = a1 * (q^i - 1) / (n - 1), n is number of items, a1 is first item
On = 8*n - 1 * (2^8 - 1) / (2 - 1)
On = 8*n - (2^8 - 1)  | 2^8 = n
On = 8*n - (n - 1)
On = (8-1)*n + 1  | 8 = ln(n)/ln(2) = ln(256)/ln(2)
On = (ln(n)/ln(2) - 1) * n + 1

Example:
n = 2^4 = 16, On ~= 3*n
n = 2^8 = 256, On ~= 7*n
n = 2^10 = 1.024, On ~= 9*n
n = 2^20 = 1.048.576, On ~= 19*n
</pre>

=== Trier une liste pré-triée ===
Si une liste est déjà presque triée, selon une certaine mesure de tri, le nombre de comparaisons nécessaires pour la trier peut être plus petit. Un algorithme de [[:en:Adaptive_sort|tri adaptatif]] capitalise sur un éventuel pré-tri dans les données, permettant une exécution plus rapide sur des entrées quasiment triées. Il parvient souvent à maintenir une complexité de <math>O(n\log n)</math> dans le pire des cas. Un exemple est le [[:en:Adaptive_heap_sort|tri adaptatif par tas]], un algorithme de tri basé sur des [[Arbre cartésien|arbres cartésiens]]. Il a une complexité de <math>O(n\log k)</math>, où <math>k</math> est la moyenne, sur toutes les valeurs <math>x</math> dans la séquence, du nombre de fois où la séquence saute par le bas <math>x</math> ci-dessus <math>x</math> ou vice versa.


== Références ==
<references />

== Bibliographie ==

* [[Donald Knuth]]. ''[[The Art of Computer Programming|L'art de la programmation informatique]]'', volume 3 :'' tri et recherche'', deuxième édition. [[Addison-Wesley]], 1997.{{ISBN|0-201-89685-0}}. Section 5.3.1 : Tri par comparaison minimale, pp. 180-197.
{{Portail|mathématiques|sciences}}

[[Catégorie:Pages avec des traductions non relues]]
[[Catégorie:Algorithme de tri|Comparaison]]