Diviser, trier puis fusionner pour obtenir un tri stable en O(n log n)

Fiche pédagogique du chapitre

Objectifs d’apprentissage

À la fin de ce chapitre, l’étudiant devra être capable de :

• expliquer le principe « diviser, résoudre et combiner » appliqué au tri fusion ;
• décomposer un tableau en sous-tableaux jusqu’aux cas élémentaires ;
• fusionner correctement deux séquences déjà triées ;
• écrire la version récursive du tri fusion ;
• réaliser une trace complète des divisions et des fusions ;
• justifier la correction de l’algorithme à l’aide d’un invariant ou d’une induction ;
• établir la complexité temporelle O(n log n) ;
• évaluer la mémoire auxiliaire nécessaire ;
• expliquer pourquoi le tri fusion est stable ;
• adapter le tri fusion aux listes chaînées et aux données volumineuses.

Prérequis

• Tableaux à une dimension et indices.
• Fonctions, procédures et paramètres.
• Récursivité et cas de base.
• Complexités O(n), O(log n) et O(n log n).
• Comparaison et copie d’éléments.

Organisation proposée

Introduction

Les tris élémentaires étudiés précédemment, comme le tri par sélection, le tri à bulles et le tri par insertion, peuvent nécessiter un nombre quadratique d’opérations lorsque la taille du tableau augmente. Le tri fusion adopte une stratégie différente : il divise le problème en sous-problèmes plus petits, trie ceux-ci puis fusionne leurs résultats.

Cette méthode fournit un temps d’exécution en O(n log n) dans tous les cas. Elle est stable et se prête particulièrement bien aux listes chaînées, au tri de fichiers volumineux et aux traitements parallèles. Son principal coût est l’utilisation de mémoire auxiliaire lors de la fusion de tableaux.

9.1 Principe

9.1.1 Le paradigme « diviser pour régner »

Le tri fusion suit les trois étapes classiques du paradigme « diviser pour régner » : diviser le problème, résoudre récursivement les sous-problèmes et combiner leurs solutions.

9.1.2 Division du tableau

À chaque niveau, le tableau est partagé autour d’un indice médian. Pour un intervalle [gauche, droite], le milieu peut être calculé par gauche + (droite - gauche) div 2. Cette écriture évite un dépassement de capacité possible avec (gauche + droite) div 2 dans certains langages.

La division n’effectue pas encore le tri. Elle produit uniquement des sous-problèmes plus petits jusqu’à obtenir des séquences élémentaires.

9.1.3 Tri des deux parties

Chaque moitié est triée avec le même algorithme. L’appel récursif ne retourne qu’après avoir complètement trié sa sous-partie. L’ordre d’exécution est généralement profondeur d’abord : la branche gauche est résolue, puis la branche droite, avant la fusion.

9.1.4 Fusion des parties triées

La fusion compare les premiers éléments non encore copiés des deux sous-tableaux. Le plus petit est ajouté au résultat, puis l’indice correspondant avance. Dès qu’un sous-tableau est épuisé, les éléments restants de l’autre sont recopiés.

9.1.5 Vue globale de l’algorithme

1. Si la séquence contient au plus un élément, terminer.

2. Calculer le milieu et séparer la séquence en deux parties.

3. Trier récursivement la partie gauche.

4. Trier récursivement la partie droite.

5. Fusionner les deux parties triées dans l’ordre croissant.

9.1.6 Invariant global

À la fin de chaque appel TriFusion portant sur un intervalle donné, cet intervalle contient exactement les mêmes éléments qu’au départ, mais classés dans l’ordre demandé. Cette propriété se propage des cas de base vers le tableau complet.

9.2 Fusion de deux tableaux

9.2.1 Précondition et objectif

La procédure de fusion reçoit deux tableaux A et B triés selon le même ordre. Elle doit produire un tableau R trié contenant tous les éléments de A et de B, sans perte ni duplication artificielle.

9.2.2 Comparaison des premiers éléments

Trois indices sont utilisés : i pour A, j pour B et k pour le tableau résultat. Tant que les deux tableaux possèdent des éléments non copiés, A[i] et B[j] sont comparés. Le plus petit est placé dans R[k].

9.2.3 Copie dans le tableau résultat

9.2.4 Trace complète d’une fusion

Fusion de A = [3, 12, 20, 31] et B = [5, 9, 18, 40].

9.2.5 Traitement des éléments restants

La boucle principale s’arrête dès que l’un des deux tableaux est épuisé. Les éléments restants de l’autre tableau sont déjà triés et supérieurs ou égaux au dernier élément copié. Ils peuvent donc être ajoutés sans nouvelles comparaisons entre les deux sources.

9.2.6 Fusion dans un tableau global

Dans une implémentation par indices, la fusion porte sur deux intervalles contigus T[gauche..milieu] et T[milieu+1..droite]. Un tableau auxiliaire reçoit temporairement les éléments, puis ceux-ci sont recopiés dans T.

9.2.7 Stabilité lors de la fusion

Un tri est stable lorsque deux éléments ayant la même clé conservent leur ordre relatif initial. Pendant la fusion, si les clés sont égales, il faut sélectionner en premier l’élément provenant de la partie gauche.

Avec le test A[i] <= B[j], A est copié avant B lorsque les clés sont égales. Remplacer <= par < peut inverser leur ordre et rendre l’implémentation instable.

9.3 Version récursive

9.3.1 Cas de base

Le cas de base est atteint lorsque l’intervalle contient zéro ou un seul élément. Aucun traitement n’est nécessaire, car cet intervalle est déjà trié.

9.3.2 Division et appels récursifs

Lorsque gauche < droite, l’intervalle est partagé en deux. Les deux appels récursifs portent sur des intervalles strictement plus petits, ce qui rapproche l’exécution du cas de base.

9.3.3 Arbre des appels

L’arbre possède log2(n) niveaux de division lorsque n est une puissance de deux. À chaque niveau, la somme des tailles des intervalles fusionnés est n.

9.3.4 Ordre des fusions

Les fusions sont réalisées lors du retour des appels récursifs. Les plus petits intervalles sont donc fusionnés en premier, puis les résultats remontent progressivement vers l’intervalle initial.

9.3.5 Trace complète sur un petit tableau

Considérons T = [7, 2, 6, 3].

9.3.6 Terminaison

La terminaison est assurée car chaque appel portant sur un intervalle de taille supérieure à un le divise en deux intervalles strictement plus petits. La taille de l’intervalle est un variant entier positif qui diminue jusqu’à un.

9.3.7 Justification de la correction

La correction peut être démontrée par induction sur la taille n de l’intervalle.

9.3.8 Version itérative ascendante

Le tri fusion peut aussi être écrit sans récursion. On fusionne d’abord des blocs de taille 1, puis 2, puis 4, jusqu’à couvrir tout le tableau. Cette version est appelée tri fusion ascendant ou bottom-up.

9.4 Analyse

9.4.1 Complexité temporelle

Pour trier n éléments, l’algorithme effectue deux appels sur des sous-tableaux d’environ n/2 éléments, puis une fusion linéaire. La relation de récurrence est donc : T(n) = 2T(n/2) + Theta(n).

9.4.2 Nombre de comparaisons

Fusionner deux séquences de longueurs p et q demande au plus p + q - 1 comparaisons entre éléments. Pour n éléments, le nombre total de comparaisons est de l’ordre de n log n.

9.4.3 Mémoire supplémentaire

Pour les tableaux, la fusion classique utilise un tableau auxiliaire de taille n, soit O(n) mémoire. La pile récursive occupe en plus O(log n) cadres d’appels. Le terme dominant reste O(n).

9.4.4 Stabilité

Le tri fusion est naturellement stable lorsque la fusion choisit l’élément gauche en cas d’égalité. Cette propriété est importante pour les tris multicritères et les enregistrements contenant plusieurs champs.

9.4.5 Tri fusion et listes chaînées

Le tri fusion est particulièrement adapté aux listes chaînées. Une liste peut être divisée à l’aide de deux pointeurs, un lent et un rapide. La fusion s’effectue en réorientant les liens entre nœuds, sans recopier les valeurs dans un tableau auxiliaire de taille n.

9.4.6 Avantages et limites

9.4.7 Comparaison avec d’autres tris

Applications du tri fusion

Application 1 — Trier des résultats d’étudiants

Des enregistrements Étudiant peuvent être triés par moyenne croissante ou décroissante. La stabilité permet de conserver l’ordre alphabétique établi auparavant lorsque deux étudiants ont la même moyenne.

Application 2 — Fusionner des journaux déjà triés

Deux serveurs produisent des journaux triés par date. La procédure de fusion peut construire un journal global en temps linéaire, sans retrier toutes les lignes depuis le début.

Application 3 — Tri externe de fichiers volumineux

Lorsque les données ne tiennent pas entièrement en mémoire, le fichier est découpé en blocs. Chaque bloc est trié en mémoire et enregistré sur disque. Les blocs triés sont ensuite fusionnés, éventuellement par groupes, jusqu’à produire un fichier global trié.

1. Lire un bloc pouvant tenir en mémoire.

2. Trier le bloc et l’écrire dans un fichier temporaire.

3. Répéter pour tous les blocs.

4. Fusionner les fichiers temporaires triés.

5. Écrire le résultat final et supprimer les fichiers temporaires.

Application 4 — Trier une liste chaînée

Dans une liste chaînée, l’insertion d’éléments au milieu ne nécessite pas de décalages. Le tri fusion exploite cet avantage et réalise les fusions en modifiant uniquement les références entre nœuds.

Application 5 — Traitement parallèle

Les deux moitiés étant indépendantes, elles peuvent être triées simultanément sur deux cœurs ou deux machines. Les résultats sont ensuite fusionnés. Cette propriété facilite la parallélisation, sous réserve de gérer le coût des communications et de la fusion.

Erreurs fréquentes et bonnes pratiques

Travaux dirigés

TD 1 — Identifier les étapes

Pour T = [11, 4, 8, 2, 7, 5], représenter toutes les divisions puis toutes les fusions du tri fusion.

TD 2 — Fusion manuelle

Fusionner A = [1, 6, 12, 15] et B = [2, 3, 9, 20, 25]. Indiquer à chaque étape les valeurs de i, j et le contenu de R.

TD 3 — Compléter le pseudo-code

Compléter les conditions manquantes d’une procédure de fusion puis justifier les tests utilisés.

TD 4 — Détecter une erreur de stabilité

On fusionne des enregistrements avec le test A[i].clé < B[j].clé. Expliquer pourquoi le tri peut devenir instable et proposer la correction.

TD 5 — Analyser la complexité

Pour n = 32, déterminer le nombre de niveaux de division, le volume total d’éléments traité par niveau et l’ordre de grandeur du travail total.

TD 6 — Mémoire auxiliaire

Comparer la mémoire utilisée par une implémentation qui crée deux nouveaux sous-tableaux à chaque appel et une implémentation qui réutilise un tableau Aux unique.

TD 7 — Version descendante et ascendante

Comparer le tri fusion récursif descendant et le tri fusion itératif ascendant selon la pile d’appels, l’ordre des fusions et la lisibilité.

TD 8 — Listes chaînées

Décrire comment diviser une liste simplement chaînée en deux moitiés à l’aide de deux pointeurs, puis indiquer comment fusionner deux listes triées.

TD 9 — Tri multicritère stable

On souhaite classer des étudiants par moyenne décroissante, puis conserver l’ordre alphabétique pour les égalités. Proposer une stratégie utilisant la stabilité du tri fusion.

TD 10 — Choisir un algorithme

Pour chacun des contextes suivants, dire si le tri fusion est adapté : petit tableau presque trié, liste chaînée volumineuse, données ne tenant pas en mémoire, tableau en mémoire avec contrainte stricte O(1) supplémentaire.

Corrigés indicatifs des travaux dirigés

Corrigé du TD 1

Corrigé du TD 2

Corrigé du TD 3

Corrigé du TD 4

Lorsque les clés sont égales, le test strict < sélectionne l’élément de B, même si celui de A apparaissait plus tôt dans la séquence initiale. Le test doit être A[i].clé <= B[j].clé pour choisir la partie gauche en cas d’égalité.

Corrigé du TD 5

Pour n = 32 = 2^5, il existe 5 niveaux de fusion. Chaque niveau traite au total 32 éléments. Le travail principal est donc proportionnel à 32 × 5 = 160, soit Theta(n log n).

Corrigé du TD 6

Créer des sous-tableaux à chaque appel provoque de nombreuses allocations et copies temporaires. Le pic mémoire reste généralement O(n), mais les coûts constants et la pression sur l’allocateur augmentent. Un unique tableau Aux de taille n, réutilisé, est plus efficace et plus prévisible.

Corrigé du TD 7

Corrigé du TD 8

Un pointeur lent avance d’un nœud tandis qu’un pointeur rapide avance de deux nœuds. Lorsque le rapide atteint la fin, le lent se trouve près du milieu. La liste est coupée à cet endroit. La fusion compare les têtes et relie au résultat le nœud possédant la plus petite clé.

Corrigé du TD 9

On peut d’abord trier les étudiants par nom croissant, puis appliquer un tri fusion stable par moyenne décroissante. Les étudiants ayant la même moyenne conservent alors l’ordre alphabétique issu du premier tri. On peut également utiliser un comparateur multicritère explicite.

Corrigé du TD 10

Travail pratique — Implémentation et étude expérimentale du tri fusion

Objectifs

• Implémenter une procédure de fusion stable.
• Implémenter le tri fusion récursif par indices.
• Tester la correction sur des cas variés.
• Mesurer le nombre de comparaisons et de copies.
• Comparer les performances avec le tri par insertion.
• Observer l’influence de la taille et de l’ordre initial des données.

Travail demandé

1. Écrire FusionnerIntervalles en utilisant un tableau auxiliaire unique.

2. Écrire TriFusion récursif et une fonction d’appel principale.

3. Ajouter des compteurs de comparaisons et d’affectations.

4. Tester des tableaux vides, unitaires, triés, inversés, aléatoires et contenant des doublons.

5. Vérifier la stabilité sur des enregistrements (clé, ordreInitial).

6. Comparer les temps avec un tri par insertion pour plusieurs tailles.

7. Tracer ou présenter un tableau des résultats.

8. Rédiger une conclusion reliant les mesures à O(n log n).

Jeux d’essai minimaux

Architecture suggérée

Grille d’évaluation indicative

Pistes d’extension

• Implémenter la version itérative ascendante.
• Trier une liste chaînée.
• Ajouter un ordre décroissant paramétrable.
• Trier des enregistrements avec un comparateur multicritère.
• Paralléliser les deux appels récursifs au-dessus d’un seuil.
• Simuler un tri externe avec plusieurs fichiers temporaires.

Synthèse du chapitre

Glossaire

Auto-évaluation

Conclusion

Le tri fusion illustre de manière complète la méthode « diviser pour régner ». Sa fusion linéaire, sa complexité garantie en Theta(n log n) et sa stabilité en font un algorithme de référence. Il est particulièrement pertinent pour les listes chaînées, les tris externes et les applications exigeant des performances prévisibles. Sa compréhension prépare directement l’étude du tri rapide, des relations de récurrence et d’autres algorithmes récursifs avancés.