Comprendre les compromis pour choisir une méthode adaptée aux données et aux contraintes

Fiche pédagogique du chapitre

Objectifs d’apprentissage

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

• expliquer le mécanisme fondamental des six tris étudiés ;
• comparer leurs complexités temporelles dans différents cas ;
• distinguer stabilité, adaptativité et caractère en place ;
• évaluer la mémoire auxiliaire utilisée par une méthode ;
• identifier les méthodes adaptées aux données presque triées ;
• choisir un tri selon la taille et la nature des données ;
• justifier le choix d’un tri pour un fichier volumineux ou une liste chaînée ;
• réaliser un tri multicritère sans perdre l’ordre secondaire ;
• concevoir une comparaison expérimentale équitable ;
• proposer une stratégie de choix automatique d’un algorithme de tri.

Prérequis

• Tableaux, listes et opérations d’échange ou de déplacement.
• Complexités O(1), O(n), O(n log n) et O(n²).
• Récursivité et paradigme « diviser pour régner ».
• Tri par sélection, à bulles, par insertion, fusion, rapide et par tas.
• Notions de mémoire auxiliaire et de pile des appels.

Organisation proposée

Introduction

Trier consiste à réorganiser une collection selon une relation d’ordre. Cette opération est omniprésente : classement d’étudiants, tri de produits par prix, organisation de fichiers, préparation d’une recherche dichotomique, regroupement de mesures ou production de rapports.

Plusieurs algorithmes peuvent produire exactement le même résultat tout en ayant des coûts très différents. Un petit tableau presque trié peut être traité efficacement par insertion, alors qu’un fichier de plusieurs gigaoctets exige une méthode de fusion externe. Un tri rapide est souvent excellent en mémoire vive, mais il n’est pas stable dans sa forme classique. Un tri par tas garantit O(n log n) et reste en place, mais ses accès mémoire sont moins favorables.

11.1 Panorama des algorithmes de tri

Les six méthodes étudiées appartiennent à deux grandes familles. Les tris élémentaires effectuent généralement un nombre quadratique de comparaisons, mais restent simples et efficaces sur de petites collections. Les tris avancés offrent un coût asymptotique plus favorable, au prix d’une logique plus élaborée.

11.1.1 Tri par sélection

Le tri par sélection cherche, à chaque étape, le plus petit élément de la partie non triée et l’échange avec le premier élément de cette partie. Après la passe i, les i + 1 premières cases contiennent les plus petites valeurs dans l’ordre définitif.

11.1.2 Tri à bulles

Le tri à bulles compare des éléments voisins et les échange lorsqu’ils sont dans le mauvais ordre. Après une passe complète de gauche à droite, le plus grand élément de la zone parcourue atteint sa position finale. Une variable booléenne permet d’arrêter l’algorithme lorsqu’aucun échange n’a eu lieu.

11.1.3 Tri par insertion

Le tri par insertion maintient une partie gauche déjà triée. L’élément courant est mémorisé, les éléments plus grands sont décalés vers la droite, puis l’élément est placé dans la case libérée. Le nombre de déplacements dépend directement du désordre initial.

11.1.4 Tri fusion

Le tri fusion divise récursivement la collection jusqu’à obtenir des sous-collections élémentaires, puis les fusionne dans l’ordre. Son coût O(n log n) est garanti, indépendamment de l’ordre initial. Sa stabilité et son accès séquentiel le rendent particulièrement adapté aux listes chaînées et aux fichiers externes.

11.1.5 Tri rapide

Le tri rapide choisit un pivot, partitionne le tableau, puis trie récursivement les deux parties. Il est souvent très performant en pratique grâce à sa faible mémoire auxiliaire et à sa bonne localité de référence. Son pire cas quadratique doit être limité par un choix de pivot approprié.

11.1.6 Tri par tas

Le tri par tas construit un tas maximum, échange la racine avec le dernier élément de la zone active, réduit cette zone et restaure la propriété du tas. Il garantit O(n log n) et utilise une mémoire constante, mais n’est pas stable et effectue des accès moins séquentiels que le tri rapide.

11.2 Critères de comparaison

11.2.1 Complexité temporelle

La complexité asymptotique indique la croissance du coût lorsque la taille augmente. Elle ne remplace pas la mesure expérimentale : deux algorithmes de même ordre peuvent avoir des constantes, des accès mémoire et des comportements de cache très différents.

11.2.2 Stabilité

Un tri est stable lorsque deux éléments ayant la même clé conservent leur ordre relatif initial. Cette propriété est indispensable dans un tri multicritère réalisé en plusieurs étapes.

11.2.3 Mémoire supplémentaire

La mémoire auxiliaire comprend les tableaux temporaires, les structures de travail et la pile des appels récursifs. Le caractère « en place » signifie généralement que la quantité de mémoire supplémentaire indépendante des données est constante ou logarithmique.

11.2.4 Nombre d’écritures et de déplacements

Dans certains systèmes, écrire une donnée coûte davantage que la comparer. C’est le cas de certaines mémoires non volatiles, de gros enregistrements ou de structures dont le déplacement déclenche des copies coûteuses.

• Le tri par sélection réalise peu d’échanges, malgré ses nombreuses comparaisons.
• Le tri à bulles peut réaliser un grand nombre d’échanges voisins.
• Le tri par insertion effectue des décalages proportionnels au désordre.
• Le tri fusion copie les données dans des zones temporaires.
• Le tri rapide et le tri par tas réalisent des échanges en place.

11.3 Adaptation aux données presque triées

Une collection est presque triée lorsqu’elle contient peu d’inversions ou lorsque chaque élément est proche de sa position finale. Cette propriété peut être fréquente dans les mises à jour quotidiennes, les journaux temporels ou les tableaux ayant subi seulement quelques modifications.

11.3.1 Notion d’inversion

Une inversion est une paire d’indices i < j telle que T[i] > T[j]. Un tableau trié ne contient aucune inversion. Le coût du tri par insertion est étroitement lié au nombre d’inversions, car chaque déplacement en corrige une.

11.3.2 Comportement des méthodes

11.4 Choix selon la taille et le contexte

11.4.1 Très petites collections

Pour quelques dizaines d’éléments, la simplicité, la faible surcharge et la localité mémoire dominent souvent l’analyse asymptotique. Le tri par insertion est généralement un excellent choix. De nombreuses bibliothèques utilisent d’ailleurs l’insertion pour les petits sous-tableaux produits par un tri avancé.

11.4.2 Collections de taille moyenne en mémoire

Le tri rapide est souvent privilégié pour des tableaux en mémoire lorsque la stabilité n’est pas requise. Le tri fusion convient lorsque la stabilité est essentielle. Le tri par tas fournit une garantie O(n log n) avec une mémoire auxiliaire constante.

11.4.3 Grandes collections et fichiers externes

Lorsqu’un fichier ne tient pas en mémoire, les accès disque dominent le coût. Le tri fusion externe est adapté parce qu’il lit et écrit de grands blocs séquentiels. Les morceaux du fichier sont triés en mémoire, écrits temporairement, puis fusionnés.

11.4.4 Listes chaînées

Le tri fusion est naturellement adapté aux listes chaînées : la division peut utiliser deux pointeurs et la fusion réorganise les références sans déplacer les données. L’accès aléatoire nécessaire à plusieurs autres tris est moins favorable.

11.4.5 Contraintes de temps réel ou de garantie

Lorsque le pire cas doit être maîtrisé, le tri par tas ou le tri fusion apporte une garantie O(n log n). Le tri rapide peut être sécurisé par une stratégie hybride telle que l’introsort, qui bascule vers le tri par tas si la récursion devient trop profonde.

11.4.6 Matrice de décision synthétique

11.5 Stratégie de choix automatique

Une bibliothèque peut sélectionner une méthode à partir de plusieurs indicateurs : taille de la collection, type de structure, estimation du désordre, besoin de stabilité, mémoire disponible et profondeur de récursion. Il s’agit d’un algorithme hybride plutôt que d’un tri unique.

Applications

Application 1 — Tri de fichiers volumineux

Un fichier de plusieurs gigaoctets ne tient pas entièrement en mémoire. Le tri externe suit deux phases : création de blocs triés puis fusion multi-voies. Chaque bloc est lu, trié en mémoire, écrit dans un fichier temporaire, puis tous les blocs sont fusionnés selon leur premier élément disponible.

Application 2 — Tri multicritère d’étudiants

On souhaite classer les étudiants par moyenne décroissante, puis par nom croissant et enfin par numéro d’inscription. Deux approches sont possibles : utiliser directement un comparateur multicritère, ou appliquer plusieurs tris stables en commençant par le critère le moins prioritaire.

Application 3 — Comparaison expérimentale des temps

Une comparaison équitable exige les mêmes données initiales pour tous les tris. Chaque algorithme doit recevoir une copie indépendante du tableau. Les mesures sont répétées, les premières exécutions peuvent être ignorées et plusieurs distributions sont testées.

Application 4 — Choix automatique d’une méthode

Un système hybride inspecte les caractéristiques du problème et choisit une méthode. Il peut également combiner plusieurs tris : tri rapide ou fusion pour les grandes zones, insertion pour les petites zones, et tas comme solution de secours en cas de récursion trop profonde.

Erreurs fréquentes et points de vigilance

Travaux dirigés

TD 1 — Compléter un tableau de propriétés

Compléter pour les six tris : meilleur cas, pire cas, stabilité, mémoire et adaptativité.

TD 2 — Choisir un tri pour chaque contexte

Proposer et justifier un choix pour : 20 valeurs presque triées, un million de valeurs en mémoire, une liste chaînée, un fichier de 50 Go et une application exigeant la stabilité.

TD 3 — Compter les opérations

Pour T = [5, 1, 4, 2, 3], compter les comparaisons et les échanges du tri par sélection et du tri à bulles.

TD 4 — Étudier la stabilité

À partir de [(A, 12), (B, 10), (C, 12), (D, 10)], montrer un résultat stable et un résultat non stable après tri sur la note.

TD 5 — Données presque triées

Comparer qualitativement insertion, fusion et tas sur T = [1, 2, 3, 4, 6, 5, 7, 8, 9].

TD 6 — Mémoire limitée

Une machine doit trier 10 millions d’entiers avec peu de mémoire libre. Comparer fusion, rapide et tas.

TD 7 — Tri multicritère

Écrire un comparateur permettant de classer par note décroissante, puis par nom croissant.

TD 8 — Construire une politique hybride

Proposer un arbre de décision utilisant la taille, la stabilité, le désordre et la mémoire.

TD 9 — Concevoir un benchmark

Définir les tailles, distributions, répétitions, métriques et contrôles nécessaires à une comparaison expérimentale.

TD 10 — Analyser des résultats

Un benchmark indique qu’insertion gagne pour n ≤ 40, rapide gagne sur tableaux aléatoires et fusion gagne sur gros fichiers. Expliquer ces observations.

Corrigés indicatifs des travaux dirigés

Correction du TD 1

Correction du TD 2

Correction du TD 3

Pour le tri par sélection, le nombre de comparaisons vaut toujours 4 + 3 + 2 + 1 = 10. Le nombre d’échanges dépend de l’implémentation ; sur cette entrée, trois échanges suffisent. Le tri à bulles effectue des comparaisons voisines et plusieurs échanges ; avec une borne réduite et arrêt anticipé, le nombre exact dépend du dernier échange de chaque passe.

Correction du TD 4

Résultat stable : (B,10), (D,10), (A,12), (C,12). B reste avant D et A reste avant C. Un résultat tel que (D,10), (B,10), (C,12), (A,12) est trié sur la note mais non stable.

Correction du TD 5

• Insertion parcourt presque linéairement et corrige seulement l’inversion (6,5).
• Fusion effectue toujours sa division et ses fusions en Θ(n log n).
• Tas reconstruit un tas et ne profite pas du faible désordre initial.

Correction du TD 6

Le tri fusion sur tableau demande une zone auxiliaire O(n), ce qui peut être problématique. Le tri rapide utilise une pile O(log n) en moyenne et est souvent le meilleur compromis. Le tri par tas garantit O(n log n) avec O(1) mémoire, au prix de constantes et d’accès mémoire moins favorables.

Correction du TD 7

Correction du TD 8

Correction du TD 9

• Tailles : par exemple 10², 10³, 10⁴, 10⁵ et 10⁶ selon les méthodes.
• Distributions : aléatoire, triée, inverse, presque triée et nombreux doublons.
• Répétitions : au moins 5 à 20 selon la variabilité.
• Métriques : temps médian, comparaisons, échanges, mémoire et profondeur.
• Contrôles : même entrée copiée, résultat vérifié, environnement identique.

Correction du TD 10

L’insertion gagne sur les petites tailles grâce à sa simplicité et à sa faible surcharge. Le tri rapide exploite bien le cache et évite une grande zone temporaire sur des tableaux aléatoires. Le tri fusion convient aux gros fichiers parce que ses accès sont séquentiels et que la fusion peut travailler par blocs.

Travail pratique — Comparateur expérimental de tris

Objectif

Implémenter et comparer les six tris sur plusieurs tailles et distributions. Le programme doit produire un rapport permettant de relier les mesures aux analyses théoriques.

Travail demandé

1. Implémenter sélection, bulles optimisé, insertion, fusion, rapide et tas.
2. Ajouter des compteurs de comparaisons, écritures ou échanges.
3. Générer des tableaux aléatoires, triés, inversés, presque triés et riches en doublons.
4. Exécuter plusieurs répétitions avec la même entrée copiée pour chaque méthode.
5. Mesurer le temps avec une horloge de haute résolution.
6. Vérifier automatiquement que chaque résultat est trié et contient les mêmes éléments.
7. Produire un tableau récapitulatif et interpréter les résultats.
8. Proposer une fonction de choix automatique fondée sur les observations.

Structure des mesures

Jeux d’essai minimaux

Grille d’évaluation proposée

Synthèse du chapitre

Glossaire

Auto-évaluation