Tri de comparaison - Comparison sort

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 à trois ) 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 forme une précommande totale sur les données, avec:

si a ≤ b et b ≤ c alors a ≤ c (transitivité)
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 venir en premier dans la liste triée. Dans un tri stable , l'ordre d'entrée détermine l'ordre de tri dans ce cas.

Une métaphore pour penser aux types de comparaison est que quelqu'un a un ensemble de poids non étiquetés et une balance . Leur but est d'aligner les poids dans l'ordre 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

Quicksort en action sur une liste de nombres. Les lignes horizontales sont des valeurs de pivot.

Certains des types de comparaison les plus connus incluent:

Limites de performances et avantages des différentes techniques de tri

Il existe des limites fondamentales aux performances des types de comparaison. Un tri de comparaison doit avoir une limite inférieure de cas moyen des opérations de comparaison Ω ( n log n ), ce qui est connu sous le nom de temps linéaireithmique . Ceci est une conséquence des informations limitées disponibles grâce aux seules comparaisons - ou, pour le dire autrement, de la structure algébrique vague d'ensembles totalement ordonnés. En ce sens, la fusion, le tri en tas et l'introsort sont asymptotiquement optimaux en termes de nombre de comparaisons à effectuer, bien que cette métrique néglige les autres opérations. Les tris sans comparaison (tels que les exemples décrits ci-dessous) peuvent atteindre des performances O ( n ) en utilisant des opérations autres que des comparaisons, ce qui leur permet de contourner cette limite inférieure (en supposant que les éléments sont de taille constante).

Les tris de comparaison peuvent s'exécuter plus rapidement sur certaines listes; de nombreux tris adaptatifs tels que le tri par insertion s'exécutent en temps O ( n ) sur une liste déjà triée ou presque triée. La limite inférieure Ω ( n log n ) s'applique uniquement au cas où la liste d'entrée peut être dans n'importe quel ordre possible.

Les mesures du monde réel de la vitesse de tri peuvent devoir prendre en compte la capacité de certains algorithmes à utiliser de manière optimale la mémoire de l' ordinateur en cache relativement rapide , ou l'application peut bénéficier de méthodes de tri où les données triées commencent à apparaître rapidement à l'utilisateur (et ensuite à la vitesse de l'utilisateur. de lecture sera le facteur limitant) 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 de comparaison offrent l'avantage pratique notable que le contrôle de la fonction de comparaison permet de trier de nombreux types de données différents et de contrôler précisément la manière dont la liste est triée. Par exemple, l'inversion du résultat de la fonction de comparaison permet de trier la liste en sens inverse; et on peut trier une liste de tuples dans l' ordre lexicographique en créant simplement une fonction de comparaison qui compare chaque partie dans l'ordre:

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)

La notation ternaire équilibrée permet d'effectuer des comparaisons en une seule étape, dont le résultat sera "inférieur à", "supérieur à" ou "égal à".

Les types de comparaison s'adaptent généralement plus facilement aux ordres complexes tels que l'ordre des nombres à virgule flottante . De plus, une fois qu'une fonction de comparaison est écrite, n'importe quel tri de comparaison peut être utilisé sans modification; Les tris sans comparaison nécessitent généralement des versions spécialisées pour chaque type de données.

Cette flexibilité, associée à l'efficacité des algorithmes de tri par comparaison ci-dessus sur les ordinateurs modernes, a conduit à une préférence généralisée pour les types de comparaison dans la plupart des travaux pratiques.

Des alternatives

Certains problèmes de tri admettent une solution strictement plus rapide que la borne $Ω (n log n)$ pour le tri par comparaison en utilisant des tris sans comparaison ; un exemple est le tri d'entiers , où toutes les clés sont des entiers. Lorsque les clés forment une petite plage (par rapport à $n$ ), le tri par 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 des paires de numéros de tri par leur somme ne sont pas soumis à la $Ω (n ² log n)$ lié soit (le carré résultant de l'appariement); l'algorithme le plus connu prend toujours $O (n ² log n)$ temps, mais seulement $O (n ²)$ comparaisons.

Nombre de comparaisons nécessaires pour trier une liste

n	${\ displaystyle \ left \ lceil \ log _ {2} (n!) \ right \ rceil}$	Le minimum
1	0	0
2	1	1
3	3	3
4	5	5
5	7	7
6	dix	dix
7	13	13
8	16	16
9	19	19
dix	22	22
11	26	26
12	29	30
13	33	34
14	37	38
15	41	42
16	45	45 ou 46
17	49	49 ou 50
18	53	53 ou 54
19	57	58
20	62	62
21	66	66
22	70	71

n	${\ displaystyle \ left \ lceil \ log _ {2} (n!) \ right \ rceil}$	${\ Displaystyle n \ log _ {2} n - {\ frac {n} {\ ln 2}}}$
dix	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

Ci-dessus: Une comparaison de la limite inférieure au nombre minimum réel de comparaisons (d'après OEIS : A036604 ) nécessaire pour trier une liste de n éléments (dans le pire des cas). Ci-dessous: En utilisant l'approximation de Stirling , cette borne inférieure est bien approximée par .

{\ displaystyle \ left \ lceil \ log _ {2} (n!) \ right \ rceil}

{\ Displaystyle n \ log _ {2} n - {\ frac {n} {\ ln 2}}}

Le nombre de comparaisons requis par un algorithme de tri par comparaison augmente proportionnellement à , où est le nombre d'éléments à trier. Cette limite est asymptotiquement serrée . ${\ Displaystyle n \ log (n)}$ ${\ displaystyle n}$

Étant donné une liste de nombres distincts (nous pouvons le supposer car il s'agit d'une analyse du pire des cas), il existe des permutations factorielles dont exactement l'une est la liste dans l'ordre trié. 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 la plupart des étapes, il ne peut pas distinguer plus de cas car les clés sont distinctes et chaque comparaison n'a que deux résultats possibles. Par conséquent, ${\ displaystyle n}$ ${\ displaystyle f (n)}$ ${\ displaystyle 2 ^ {f (n)}}$

{\ displaystyle 2 ^ {f (n)} \ geq n!}

, ou équivalent

{\ Displaystyle f (n) \ geq \ log _ {2} (n!).}

En regardant les premiers facteurs de , on obtient ${\ displaystyle n / 2}$ ${\ Displaystyle n! = n (n-1) \ cdots 1}$

{\ displaystyle \ 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). }

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

Cela constitue la partie inférieure de la revendication. Une meilleure borne peut être donnée via l'approximation de Stirling .

Une limite supérieure identique découle de l'existence des algorithmes qui atteignent cette limite dans le pire des cas, comme le tri en tas et le tri par fusion .

L'argument ci-dessus fournit une limite inférieure absolue , plutôt que seulement asymptotique, sur le nombre de comparaisons, à savoir les comparaisons. Cette borne inférieure est assez bonne (elle peut être approchée dans une tolérance linéaire par un simple tri par fusion), mais elle est connue pour être inexacte. Par exemple, mais le nombre minimal de comparaisons pour trier 13 éléments s'est avéré être de 34. ${\ displaystyle \ left \ lceil \ log _ {2} (n!) \ right \ rceil}$ ${\ displaystyle \ left \ lceil \ log _ {2} (13!) \ right \ rceil = 33}$

Déterminer le nombre exact de comparaisons nécessaires pour trier un nombre donné d'entrées est un problème de calcul difficile, même pour un petit n , et aucune formule simple pour la solution n'est connue. Pour certaines des quelques valeurs concrètes qui ont été calculées, voir OEIS : A036604 .

Limite 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 dans l'ensemble de toutes les permutations possibles de n éléments,

il est impossible de déterminer dans quel ordre l'entrée se trouve avec moins de $log 2 (n!)$ comparaisons en moyenne.

Cela peut être vu plus facilement en utilisant les concepts de la théorie de l' information . L' entropie de Shannon d'une telle permutation aléatoire est $log 2 (n!)$ Bits. Étant donné qu'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 2 (n!) - k$ bits en moyenne. Pour effectuer le tri, des informations complètes sont nécessaires, donc l'entropie restante doit être égale à 0. Il s'ensuit que k doit être au moins $log 2 (n!) En$ moyenne.

La borne inférieure dérivée via la théorie de l'information est formulée comme «borne inférieure de la théorie de l'information». La borne inférieure de la théorie de l'information est correcte mais n'est pas nécessairement la borne inférieure la plus forte. Et dans certains cas, la borne inférieure théorique de l'information d'un problème peut même être loin de la véritable borne inférieure. Par exemple, la limite inférieure de la sélection théorique de l'information est alors que les comparaisons sont nécessaires par 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 qui délimite une fonction entière. Cependant, ce n'est pas tout à fait correct lorsque l'on considère le cas moyen. ${\ Displaystyle \ left \ lceil \ log _ {2} (n) \ right \ rceil}$ ${\ displaystyle n-1}$

Pour découvrir ce qui se passe lors de l'analyse du cas moyen, la clé est de savoir à quoi se réfère la «moyenne»? Faire la moyenne sur quoi? Avec une certaine connaissance de la théorie de l'information, la borne inférieure de la théorie de l'information fait des moyennes sur l'ensemble de toutes les permutations dans leur ensemble. Mais tout algorithme informatique (selon ce que l'on croit actuellement) doit traiter chaque permutation comme une instance individuelle du problème. Par conséquent, la limite 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 le modèle d'arbre de décision , la limite inférieure à afficher est la limite inférieure de la longueur moyenne des chemins de racine à feuille d'un arbre binaire à feuilles (dans lequel chaque feuille correspond à une permutation). On serait convaincu de dire qu'un arbre binaire complet équilibré atteint le minimum de la longueur moyenne. Avec quelques calculs minutieux, pour un arbre binaire complet équilibré avec des feuilles, la longueur moyenne des chemins de racine à feuille est donnée par ${\ Displaystyle n!}$ ${\ Displaystyle n!}$

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

Par exemple, pour $n = 3$ , la limite inférieure de la théorie de l'information pour le cas moyen est d'environ 2,58, tandis que la limite inférieure moyenne dérivée via le modèle d'arbre de décision est de 8/3, soit environ 2,67.

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

Trier une liste pré-triée

Si une liste est déjà pré-triée, le nombre de comparaisons nécessaires pour trier la liste est généralement plus petit. La notion de liste pré-triée peut être formalisée avec diverses mesures de pré- tri . Compte tenu d'une telle mesure , il existe une notion d' algorithme de tri (faiblement) optimal. ${\ displaystyle m}$ ${\ displaystyle m}$

Remarques

^ Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2009) [1990]. Introduction aux algorithmes (3e éd.). MIT Press et McGraw-Hill. 191–193. ISBN 0-262-03384-4 .
^ Mark Wells, Applications d'un langage pour le calcul en combinatoire, Traitement de l'information 65 (Actes du Congrès de l'IFIP 1965), 497–498, 1966.
^ Mark Wells, Elements of Combinatorial Computing, Pergamon Press, Oxford, 1971.
^ Takumi Kasai, Shusaku Sawato, Shigeki Iwata, trente-quatre comparaisons sont nécessaires pour trier 13 éléments, LNCS 792, 260-269, 1994.
^ Marcin Peczarski, le tri de 13 éléments nécessite 34 comparaisons, LNCS 2461, 785–794, 2002.
^ ^A ^b ^c Marcin Peczarski, de nouveaux résultats dans le tri minimum de comparaison, Algorithmica 40 (2), 133-145, 2004.
^ Marcin Peczarski, Recherche assistée par ordinateur des posets, thèse de doctorat, Université de Varsovie, 2006.
^ Peczarski, Marcin (2007). "L'algorithme de Ford-Johnson est toujours invaincu pour moins de 47 éléments". Inf. Traiter. Lett . 101 (3): 126-128. doi : 10.1016 / j.ipl.2006.09.001 .
^ ^un ^b Cheng, Weiyi; Liu, Xiaoguang; Wang, Gang; Liu, Jing (octobre 2007). "最少比较排序问题中 S （15）和 S （19）的解决" [Les résultats de S (15) et S (19) au problème de tri par comparaison minimale]. Journal of Frontiers of Computer Science and Technology (en chinois). 1 (3): 305–313.
^ Peczarski, Marcin (3 août 2011). "Vers un tri optimal de 16 éléments". Acta Universitatis Sapientiae . 4 (2): 215-224. arXiv : 1108.0866 . Bibcode : 2011arXiv1108.0866P .

Les références

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.

[1] Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2009) [1990]. Introduction aux algorithmes (3e éd.). MIT Press et McGraw-Hill. 191–193. ISBN 0-262-03384-4 .

[Wells1965-2] Mark Wells, Applications d'un langage pour le calcul en combinatoire, Traitement de l'information 65 (Actes du Congrès de l'IFIP 1965), 497–498, 1966.

[Wells1971-3] Mark Wells, Elements of Combinatorial Computing, Pergamon Press, Oxford, 1971.

[KasaiSawatoIwata1994-4] Takumi Kasai, Shusaku Sawato, Shigeki Iwata, trente-quatre comparaisons sont nécessaires pour trier 13 éléments, LNCS 792, 260-269, 1994.

[Peczarski2002-5] Marcin Peczarski, le tri de 13 éléments nécessite 34 comparaisons, LNCS 2461, 785–794, 2002.

[Peczarski2004-6] A ^b ^c Marcin Peczarski, de nouveaux résultats dans le tri minimum de comparaison, Algorithmica 40 (2), 133-145, 2004.

[Peczarski2006-7] Marcin Peczarski, Recherche assistée par ordinateur des posets, thèse de doctorat, Université de Varsovie, 2006.

[Peczarski2007-8] Peczarski, Marcin (2007). "L'algorithme de Ford-Johnson est toujours invaincu pour moins de 47 éléments". Inf. Traiter. Lett . 101 (3): 126-128. doi : 10.1016 / j.ipl.2006.09.001 .

[ChengLiuWang2007-9] un ^b Cheng, Weiyi; Liu, Xiaoguang; Wang, Gang; Liu, Jing (octobre 2007). "最少比较排序问题中 S （15）和 S （19）的解决" [Les résultats de S (15) et S (19) au problème de tri par comparaison minimale]. Journal of Frontiers of Computer Science and Technology (en chinois). 1 (3): 305–313.

[10] Peczarski, Marcin (3 août 2011). "Vers un tri optimal de 16 éléments". Acta Universitatis Sapientiae . 4 (2): 215-224. arXiv : 1108.0866 . Bibcode : 2011arXiv1108.0866P .

Languages

In other projects