Tri par comparaison

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 relation de préordre total, avec:

1. si a ≤ b et b ≤ c alors a ≤ c (transitivité)
2. pour tout a et b, a ≤ b ou b ≤ a (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 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 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

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 en tas
• Tri de Shell
• Tri par fusion
• Introsort
• Tri par insertion
• Tri de sélection
• Tri à bulles
• Tri impair-pair
• Tri cocktail
• Tri par cycles
• Tri par fusion-insertion
• Tri en douceur
• Tri Tim
• 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 Ω (n log n) comparaisons en moyenne, qui est connue sous le nom de 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 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 comparatifs peuvent 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 Ω (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 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 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 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 Ω(n log n) du tri par comparaison grâce à l'utilisation des 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 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 Ω(n² log n); l'algorithme le plus connu prend toujours un temps O(n² log n), mais seulement O(n²) comparaisons.

Nombre de comparaisons nécessaires pour trier une liste

n	$\left\lceil \log _{2}(n!)\right\rceil$	Minimum
1	0	0
2	1	1
3	3	3
4	5	5
5	7	7
6	10	10
7	13	13
8	16	16
9	19	19
10	22	22
11	26	26
12	29	30
13	33	34
14	37	38
15	41	42
16	45	46
17	49	50
18	53	54
19	57	58
20	62	62
21	66	66
22	70	71
n	$\left\lceil \log _{2}(n!)\right\rceil$	$n\log _{2}n-{\frac {n}{\ln 2}}$
10	22	19
100	525	521
1 000	8 530	8 524
10 000	118 459	118 451
100 000	1 516 705	1 516 695
1 000 000	18 488 885	18 488 874

Au dessus : Une comparaison de la borne inférieure $\left\lceil \log _{2}(n!)\right\rceil$ au nombre minimum réel de comparaisons (à partir de  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

$n\log _{2}n-{\frac {n}{\ln 2}}$.

.

Le nombre de comparaisons nécessaires par un algorithme de tri par comparaison augmente proportionnellement à $n\log(n)$, où $n$ est le nombre d'éléments à trier. Cette limite est 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 $f(n)$ étapes, il ne peut pas distinguer plus de $2^{f(n)}$ cas car les clés sont distinctes et chaque comparaison n’a que deux résultats possibles. Donc,

$2^{f(n)}\geq n!$, ou équivalent $f(n)\geq \log _{2}(n!).$

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

$\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).$

$\log _{2}(n!)=\Omega (n\log n).$

Cela fournit la borne inférieure. Un résultat plus précis peut être donnée par l'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 par fusion.

L'argument ci-dessus fournit une borne inférieure absolue, plutôt que seulement asymptotique, à savoir $\left\lceil \log _{2}(n!)\right\rceil$ comparaisons. Cette borne inférieure est assez bonne, mais elle est connue pour être inexacte. Par exemple, $\left\lceil \log _{2}(13!)\right\rceil =33$, 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 log₂(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 log₂(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 log₂(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 log₂(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 $\left\lceil \log _{2}(n)\right\rceil$ alors que $n-1$ 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 modèle d'arbre de décision. Reformulons un peu notre objectif. Dans l'arbre de décision, la borne inférieure est la longueur moyenne des chemins racine-feuille d'un arbre binaire à $n!$ 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 $n!$ feuilles, la longueur moyenne des chemins racine-feuille est donnée par

${\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!}}$

Par exemple, pour 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 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...).

(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

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 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 $O(n\log n)$ dans le pire des cas. Un exemple est le tri adaptatif par tas, un algorithme de tri basé sur des arbres cartésiens. Il a une complexité de $O(n\log k)$, où $k$ est la moyenne, sur toutes les valeurs $x$ dans la séquence, du nombre de fois où la séquence saute par le bas $x$ ci-dessus $x$ ou vice versa.

Bibliographie

• Donald Knuth. 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.