Tri par fusion-insertion

En informatique, le tri par fusion-insertion ou algorithme de Ford-Johnson est un algorithme de tri par comparaison publié en 1959 par LR Ford Jr. et Selmer M. Johnson .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. 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 Stanisław Trybuła (en) et Czen Ping. 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 $X$ de $n$ éléments :

1. Regrouper les éléments de $X$ en $\lfloor n/2\rfloor$ paires d'éléments, arbitrairement, laissant un élément non apparié s'il y a un nombre impair d'éléments.
2. Effectuer $\lfloor n/2\rfloor$ comparaisons, une par paire, pour déterminer le plus grand des deux éléments de chaque paire (déterminer le maximum).
3. Trier récursivement les $\lfloor n/2\rfloor$ plus grands éléments de chaque paire, créant une séquence triée $S$ de $\lfloor n/2\rfloor$ des éléments d’entrée, par ordre croissant.
4. Insérer au début de $S$ l'élément qui a été apparié au premier et au plus petit élément de $S$ .
5. Insérer le reste des $\lceil n/2\rceil -1$ éléments de $X\setminus S$ dans $S$, 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 $S$ (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 $S$ 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. Pour choisir un ordre d'insertion qui produit ces longueurs, prenons la séquence triée $S$ après l'étape 4 du plan ci-dessus (avant d'insérer les éléments restants). Soit $x_{i}$ le $i$-ème élément de cette séquence triée. Ainsi on obtient,

$S=(x_{1},x_{2},x_{3},\dots ),$

où chaque élément $x_{i}$ avec $i\geq 3$ est associé à un élément $y_{i}<x_{i}$ qui n'a pas encore été inséré. ($y_{1}$ et $y_{2}$ n'existent pas car $x_{1}$ et $x_{2}$ ont été jumelés les uns aux autres.) Si $n$ est impair, l'élément non apparié restant doit également être numéroté comme un $y_{i}$ avec $i$ 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:

• Partitionner les éléments non insérés $y_{i}$ en groupes avec des index contigus. Il y a deux éléments $y_{3}$ et $y_{4}$ 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

$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$

• Utilisez cet ordre pour insérer les éléments $y_{i}$ dans $S$ . Pour chaque élément $y_{i}$, utilisez une recherche dichotomique à partir du début de $S$ jusqu'à $x_{i}$ exclu afin de déterminer où insérer $y_{i}$ .

Analyse

Mettons $C(n)$ le nombre de comparaisons effectuées par le tri par fusion-insertion, dans le pire cas, lors d'un tri de $n$ éléments. Ce nombre de comparaisons $C(n)$ peut se décomposer comme la somme de trois termes :

• $\lfloor n/2\rfloor$ comparaisons entre les paires d'éléments,
• $C(\lfloor n/2\rfloor )$ 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 $S$ de longueur au plus trois. D'abord, $y_{4}$ est inséré dans la sous-séquence à trois éléments $(x_{1},x_{2},x_{3})$ . Alors, $y_{3}$ est inséré dans une permutation de la sous-séquence à trois éléments $(x_{1},x_{2},y_{4})$, ou dans certains cas dans la sous-séquence à deux éléments $(x_{1},x_{2})$ . De même, les éléments $y_{6}$ et $y_{5}$ 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 $i$ le groupe est $i+1$, car chacun est inséré dans une sous-séquence de longueur au plus $2^{i+1}-1$. En additionnant le nombre de comparaisons utilisées pour tous les éléments et en résolvant la relation de récurrence résultante, cette analyse peut être utilisée pour calculer les valeurs de $C(n)$, donnant la formule

$C(n)=\sum _{i=1}^{n}\left\lceil \log _{2}{\frac {3i}{4}}\right\rceil \approx n\log _{2}n-1.415n$

ou, sous forme fermée,

$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 }.$

Pour $n=1,2,\dots$ le nombre de comparaisons est : 0, 1, 3, 5, 7, 10, 13, 16, 19, 22, 26, 30, 34... (suite A001768 de l'OEIS).

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'à $n=11$ ) son nombre de comparaisons est égal à la limite inférieure du tri par comparaison de $\lceil \log _{2}n!\rceil \approx n\log _{2}n-1.443n$ . 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 (Sorting Numbers (en)), 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 $n\log _{2}n-0.915n$ et $n\log _{2}n-n$, avec le même terme principal mais un facteur constant pire dans le terme linéaire d'ordre inférieur.

Le tri par fusion-insertion est l'algorithme de tri avec le minimum de comparaisons possibles pour $n$ articles à chaque fois $n\leq 22$, et il contient le moins de comparaisons connues pour $n\leq 46$ . 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. 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.

Bibliographie

1. The original description by Ford & Johnson (en) (1959) "A tournament problem", American Mathematical Monthly, 66: 387–389, doi:10.2307/2308750 MR 0103159.
2. Williamson, Stanley Gill (2002), "2.31 Merge insertion (Ford–Johnson)", Combinatorics for Computer Science, Dover books on mathematics, Courier Corporation, p. 66–68, (ISBN 9780486420769).
3. Mahmoud, Hosam M. (2011), "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)
4. Knuth, Donald E. (1998), "Merge insertion", The Art of Computer Programming, Vol. 3: Sorting and Searching (2nd ed.), p. 184–186
5. 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
6. 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.
7. 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).
8. Guy, Richard K.; Nowakowski, Richard J. (December 1995), "Monthly Unsolved Problems, 1969-1995", American Mathematical Monthly, 102 (10): 921–926, doi:10.2307/2975272
9. Knuth (1998), p. 184: "Since it involves some aspects of merging and some aspects of insertion, we call it merge insertion."
10. Peczarski, Marcin (2004), "New results in minimum-comparison sorting", Algorithmica, 40 (2): 133–145, doi:10.1007/s00453-004-1100-7, MR 2072769
11. Peczarski, Marcin (2007), "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, MR 2287331