Voir la source de Tri par fusion-insertion

{{À wikifier|date=novembre 2023}}

En [[informatique]], '''le tri par fusion-insertion''' ou '''algorithme de Ford-Johnson''' est un [[algorithme de tri]] par comparaison publié en 1959 par [[Lester Randolph Ford junior|LR Ford Jr.]] et Selmer M. Johnson {{Références multiples|fj|c4cs|distrib|knuth}}. Il utilise moins de comparaisons dans le pire des cas que le [[tri par insertion]] et le [[tri fusion]] qui sont les meilleurs algorithmes connus auparavant<ref name=fj>{{article | langue=en | nom1=Ford | prénom1=Lester R. Jr. | nom2=Johnson | prénom2=Selmer M. | titre=A tournament problem | périodique=[[American Mathematical Monthly]] | mr=0103159 | passage=387–389 | volume=66 | année=1959 | doi=10.2307/2308750}}.</ref>. Pendant une période de 20 ans, l'algorithme de Ford-Johnson détenait le record du nombre minimal de comparaisons parmi les algorithmes de tri connus. Bien que son utilité pratique soit limitée, il conserve un intérêt théorique en lien avec le problème du tri utilisant un nombre minimum de comparaisons.

Il est intéressant de noter que le même algorithme a probablement été découvert de manière indépendante par {{lien|lang=en|Stanisław_Trybuła|texte=Stanisław Trybuła}} et [[Czen Ping]]<ref name=knuth>{{chapitre | langue=en | nom=Knuth | prénom=Donald E. | titre chapitre=Merge insertion | édition=2 | passage=184–186 | série=[[The Art of Computer Programming]] | titre ouvrage=3: Sorting and Searching | année=1998}}.</ref>. Cette convergence indépendante souligne l'importance et la pertinence de l'algorithme dans le contexte de la recherche en informatique et de la résolution du problème du tri avec un nombre minimal de comparaisons.

== Algorithme ==
Le tri par fusion-insertion suit dans l'ordre les étapes suivantes, prenant une entrée <math>X</math> de <math>n</math> éléments :
# Regrouper les éléments de <math>X</math> en <math>\lfloor n/2\rfloor</math> paires d'éléments, arbitrairement, laissant un élément non apparié s'il y a un nombre impair d'éléments.
# Effectuer <math>\lfloor n/2\rfloor</math> comparaisons, une par paire, pour déterminer le plus grand des deux éléments de chaque paire (déterminer le maximum).
# Trier récursivement (avec un tri par fusion-insertion) les <math>\lfloor n/2\rfloor</math> plus grands éléments de chaque paire, créant une séquence triée <math>S</math> de <math>\lfloor n/2\rfloor</math> des éléments d’entrée, par ordre croissant.
# Insérer au début de <math>S</math> l'élément qui a été apparié au premier et au plus petit élément de <math>S</math>.
# Insérer le reste des <math>\lceil n/2\rceil-1</math> éléments de <math>X\setminus S</math> dans <math>S</math>, un à la fois, avec un ordre d'insertion spécialement choisi décrit ci-dessous. Utiliser la [[recherche dichotomique]] dans les sous-séquences de <math>S</math> (comme décrit ci-dessous) pour déterminer la position à laquelle chaque élément doit être inséré.

Cet algorithme est conçu pour tirer parti du fait que les recherches dichotomiques utilisées pour insérer des éléments dans <math>S</math> sont les plus efficaces (du point de vue de l'analyse au pire cas) lorsque la longueur de la sous-séquence recherchée est inférieure à une [[puissance de deux]]. En effet, pour ces longueurs, tous les résultats de la recherche utilisent le même nombre de comparaisons les uns que les autres<ref name="fj" />. Pour choisir un ordre d'insertion qui produit ces longueurs, prenons la séquence triée <math>S</math> après l'étape 4 du plan ci-dessus (avant d'insérer les éléments restants). Soit <math>x_i</math> le <math>i</math>-ème élément de cette séquence triée. Ainsi on obtient,

: <math>S=(x_1,x_2,x_3,\dots),</math>

où chaque élément <math>x_i</math> avec <math>i\ge 3</math> est associé à un élément <math>y_i < x_i</math> qui n'a pas encore été inséré. (<math>y_1</math> et <math>y_2</math> n'existent pas car <math>x_1</math> et <math>x_2</math> ont été jumelés les uns aux autres.) Si <math>n</math> est impair, l'élément non apparié restant doit également être numéroté comme un <math>y_i</math> avec <math>i</math> plus grand que les index des éléments appariés. Ensuite, on peut étendre la dernière étape du plan ci-dessus aux étapes suivantes{{Références multiples|fj|c4cs|distrib|knuth}}:
* Partitionner les éléments non insérés <math>y_i</math> en groupes avec des index contigus. Il y a deux éléments <math>y_3</math> et <math>y_4</math> dans le premier groupe, et les sommes des tailles de tous les deux groupes adjacents forment une séquence de puissances de deux. Ainsi, les tailles des groupes sont : 2, 2, 6, 10, 22, 42...
* Classer les éléments non insérés par groupes (des index plus petits vers des index plus grands), mais au sein de chaque groupe, classez-les d'index plus grands vers des index plus petits. Ainsi, la commande devient

:: <math>y_4,y_3,y_6,y_5,y_{12},y_{11},y_{10},y_9,y_8,y_7,y_{22},y_{21}\dots</math>

* Utilisez cet ordre pour insérer les éléments <math>y_i</math> dans <math>S</math>. Pour chaque élément <math>y_i</math>, utilisez une [[recherche dichotomique]] à partir du début de <math>S</math> jusqu'à  <math>x_i</math> exclu afin de déterminer où insérer <math>y_i</math>.

== Analyse ==
Mettons <math>C(n)</math> le nombre de comparaisons effectuées par le tri par fusion-insertion, dans le pire cas, lors d'un tri de <math>n</math> éléments. Ce nombre de comparaisons <math>C(n)</math> peut se décomposer comme la somme de trois termes :
* <math>\lfloor n/2\rfloor</math> comparaisons entre les paires d'éléments,
* <math>C(\lfloor n/2\rfloor)</math> des comparaisons pour l'appel récursif, et
* un certain nombre de comparaisons pour les insertions binaires utilisées pour insérer les éléments restants.

Au troisième terme, le nombre le plus défavorable de comparaisons pour les éléments du premier groupe est de deux, car chacun est inséré dans une sous-séquence de <math>S</math> de longueur au plus trois. D'abord, <math>y_4</math> est inséré dans la sous-séquence à trois éléments <math>(x_1,x_2,x_3)</math>. Alors, <math>y_3</math> est inséré dans une permutation de la sous-séquence à trois éléments <math>(x_1,x_2,y_4)</math>, ou dans certains cas dans la sous-séquence à deux éléments <math>(x_1,x_2)</math>. De même, les éléments <math>y_6</math> et <math>y_5</math> du deuxième groupe sont chacun insérés dans une sous-séquence d'une longueur maximale de sept, à l'aide de trois comparaisons. Plus généralement, le nombre le plus défavorable de comparaisons pour les éléments du <math>i</math> le groupe est <math>i+1</math>, car chacun est inséré dans une sous-séquence de longueur au plus <math>2^{i+1}-1</math>{{Références multiples|fj|c4cs|distrib|knuth}}. En additionnant le nombre de comparaisons utilisées pour tous les éléments et en résolvant la [[Suite définie par récurrence|relation de récurrence]] résultante, cette analyse peut être utilisée pour calculer les valeurs de <math>C(n)</math>, donnant la formule

: <math>C(n)=\sum_{i=1}^n \left\lceil \log_2 \frac{3i}{4} \right\rceil \approx n\log_2 n - 1.415n</math>

ou, sous [[Expression de forme fermée|forme fermée]]<ref name=gn>{{article | langue=en | nom1=Guy | prénom1=Richard K. | nom2=Nowakowski | prénom2=Richard J. | date=décembre 1995 | doi=10.2307/2975272 | numéro=10 | périodique=[[American Mathematical Monthly]] | passage=921–926 | titre=''Monthly'' Unsolved Problems, 1969-1995 | volume=102}}.</ref>,

: <math>C(n)=n\biggl\lceil\log_2\frac{3n}{4}\biggr\rceil-\biggl\lfloor\frac{2^{\lfloor \log_2 6n\rfloor}}{3}\biggr\rfloor+\biggl\lfloor\frac{\log_2 6n}{2}\biggr\rfloor.</math>

Pour <math>n=1,2,\dots</math> le nombre de comparaisons est<ref name="fj" /> : 0, 1, 3, 5, 7, 10, 13, 16, 19, 22, 26, 30, 34... ({{OEIS|A001768}}).

== Relation avec d'autres types de comparaison ==
L'algorithme est appelé tri par fusion-insertion car les comparaisons initiales qu'il effectue avant son appel récursif (association d'éléments arbitraires et comparaison de chaque paire) sont les mêmes que les comparaisons initiales du [[tri fusion]], tandis que les comparaisons qu'il effectue après l'appel récursif (en utilisant la recherche binaire pour insérer des éléments un par un dans une liste triée) suivez le même principe que le [[tri par insertion]]. En ce sens, il s’agit d’un algorithme hybride qui combine à la fois le tri par fusion et le tri par insertion.

Pour les petits intrants (jusqu'à <math>n=11</math>) son nombre de comparaisons est égal à la [[Majorant ou minorant|limite inférieure]] du tri par comparaison de <math>\lceil\log_2 n!\rceil\approx n\log_2 n - 1.443n</math>. Cependant, pour des entrées plus volumineuses, le nombre de comparaisons effectuées par l'algorithme de fusion-insertion est supérieur à cette limite inférieure. Le tri par fusion-insertion effectue également moins de comparaisons que les nombres de tri {{lien|lang=en|Sorting_number|texte=(Sorting Numbers}}), qui comptent les comparaisons effectuées par le tri par insertion binaire ou par le tri par fusion dans le pire des cas. Les nombres de tri varient entre <math>n\log_2 n - 0.915n</math> et <math>n\log_2 n - n</math>, avec le même terme principal mais un facteur constant pire dans le terme linéaire d'ordre inférieur<ref name="fj" />.

Le tri par fusion-insertion est l'algorithme de tri avec le minimum de comparaisons possibles pour <math>n</math> articles à chaque fois <math>n\le 22</math>, et il contient le moins de comparaisons connues pour <math>n\le 46</math> {{Références multiples|pec|pec2}}. Pendant 20 ans, le tri par fusion-insertion était l'algorithme de tri avec le moins de comparaisons connu pour toutes les longueurs d'entrée. Cependant, en 1979, Glenn Manacher a publié un autre algorithme de tri utilisant encore moins de comparaisons, pour des entrées suffisamment volumineuses{{Références multiples|distrib|nonopt}}. Le nombre exact de comparaisons nécessaires pour trier un ensemble d'éléments, quel que soit sa taille ''n'', demeure inconnu. Cependant, il est notable que l'algorithme de Manacher et d'autres algorithmes de tri avancés ont incorporé des adaptations des concepts du tri par fusion-insertion<ref name=distrib>{{chapitre | langue=en | nom=Mahmoud | prénom=Hosam M. | titre chapitre=12.3.1 The Ford–Johnson algorithm | isbn=9781118031131 | passage=286–288 | éditeur=John Wiley & Sons | series=Wiley Series in Discrete Mathematics and Optimization | titre ouvrage=Sorting: A Distribution Theory | volume=54 | année=2011 | lire en ligne=https://books.google.com/books?id=kM5v2YqMVuoC&pg=PA286}}.</ref>.

== Références ==
{{Références|références=
<ref name=c4cs>{{chapitre | langue=en | nom=Williamson | prénom=Stanley Gill | titre chapitre=2.31 Merge insertion (Ford–Johnson) | titre ouvrage=Combinatorics for Computer Science | isbn=9780486420769 | passage=66–68 | éditeur=Courier Corporation | series=Dover books on mathematics | titre=Combinatorics for Computer Science | année=2002 | lire en ligne=https://books.google.com/books?id=YMIoy5JwdHMC&pg=PA66}}.</ref>
<ref name=pec>{{article | langue=en | nom=Peczarski | prénom=Marcin | doi=10.1007/s00453-004-1100-7 | numéro=2 | périodique=Algorithmica | mr=2072769 | passage=133–145 | titre=New results in minimum-comparison sorting | volume=40 | année=2004}}.</ref>
<ref name=pec2>{{article | langue=en | nom=Peczarski | prénom=Marcin | doi=10.1016/j.ipl.2006.09.001 | numéro=3 | périodique=Information Processing Letters | mr=2287331 | passage=126–128 | titre=The Ford-Johnson algorithm still unbeaten for less than 47 elements | volume=101 | année=2007}}.</ref>
<ref name=nonopt>{{article | langue=en | nom=Manacher | prénom=Glenn K. | date=juillet 1979 | doi=10.1145/322139.322145 | numéro=3 | périodique=[[Journal of the ACM]] | passage=441–456 | titre=The Ford-Johnson Sorting Algorithm Is Not Optimal | volume=26| accès doi=libre}}.</ref>
}}

== Bibliographie ==
# The original description by [[Lester Randolph Ford junior|Ford]] & {{lien|lang=en|Selmer_M._Johnson|texte=Johnson}} (1959)  "A tournament problem", ''[[The American Mathematical Monthly|American Mathematical Monthly]]'', '''66''': 387–389, {{doi|10.2307/2308750}}, {{MathSciNet|0103159}}.
# Williamson, Stanley Gill (2002), [https://books.google.com/books?id=YMIoy5JwdHMC&pg=PA66 "2.31 Merge insertion (Ford–Johnson)"], ''Combinatorics for Computer Science'', Dover books on mathematics, Courier Corporation, {{p.|66–68}}, {{ISBN|9780486420769}}.
# Mahmoud, Hosam M. (2011), [https://books.google.com/books?id=kM5v2YqMVuoC&pg=PA286 "12.3.1 The Ford–Johnson algorithm"], ''Sorting: A Distribution Theory'', Wiley Series in Discrete Mathematics and Optimization, vol. 54, [[John Wiley & Sons]], {{p.|286–288}}, {{ISBN|9781118031131}}
# [[Donald Knuth|Knuth, Donald E.]] (1998), "Merge insertion", ''[[The Art of Computer Programming]], Vol. 3: Sorting and Searching'' (2nd ed.), {{p.|184–186}}
# Manacher, Glenn K. (July 1979), "The Ford-Johnson Sorting Algorithm Is Not Optimal", ''[[Journal of the ACM]]'', '''26''' (3): 441–456, {{doi|10.1145/322139.322145}}
# The original description by Ford & Johnson (1959) sorted the elements in descending order. The steps listed here reverse the output, following the description in Knuth (1998). The resulting algorithm makes the same comparisons but produces ascending order instead.
# [[Donald Knuth|Knuth (1998)]] credits the summation formula to the 1960 Ph.D. thesis of A. Hadian. The approximation formula was already given by Ford & Johnson (1959).
# [[Richard Guy|Guy, Richard K]].; Nowakowski, Richard J. (December 1995), "''Monthly'' Unsolved Problems, 1969-1995", ''[[The American Mathematical Monthly|American Mathematical Monthly]]'', '''102''' (10): 921–926, {{doi|10.2307/2975272}}
# [[Donald Knuth|Knuth (1998)]], {{p.|184}}: "Since it involves some aspects of merging and some aspects of insertion, we call it ''merge insertion''."
# Peczarski, Marcin (2004), "New results in minimum-comparison sorting", ''Algorithmica'', '''40''' (2): 133–145, {{doi|10.1007/s00453-004-1100-7}}, {{MathSciNet|2072769}}
# Peczarski, Marcin (2007), "{{lang|en|texte=The Ford-Johnson algorithm still unbeaten for less than 47 elements}}", ''Information Processing Letters'', '''101''' (3): 126–128, {{doi|10.1016/j.ipl.2006.09.001}}, {{MathSciNet|2287331}}

{{Palette|Algorithmes de tri}}
{{Portail|informatique}}

[[Catégorie:Programmation informatique]]
[[Catégorie:Algorithme de tri|Fusion-insertion]]