Organiser, classer et préparer efficacement les données

Fiche pédagogique du chapitre

Objectifs d’apprentissage

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

• expliquer l’intérêt d’ordonner des données avant leur exploitation ;
• définir un critère et un sens de tri ;
• distinguer une partie triée d’une partie non triée ;
• concevoir et tracer un tri par sélection ;
• concevoir et optimiser un tri à bulles ;
• concevoir un tri par insertion ;
• effectuer correctement les comparaisons, échanges et décalages ;
• trier dans l’ordre croissant ou décroissant ;
• trier des nombres, des chaînes et des enregistrements ;
• préserver l’association entre plusieurs informations ;
• comparer les tris selon leur simplicité, leur coût et le contexte ;
• analyser leur comportement sur un tableau déjà ou presque trié ;
• construire des jeux d’essai et détecter les erreurs classiques.

Prérequis

• maîtriser les variables, conditions et boucles imbriquées ;
• savoir déclarer, parcourir et modifier un tableau ;
• connaître les fonctions et procédures ;
• savoir utiliser une variable temporaire pour échanger deux valeurs ;
• comprendre les comparaisons numériques et lexicographiques ;
• savoir construire une table de trace.

Plan du chapitre

14.1 Intérêt du tri

14.2 Tri par sélection

14.3 Tri à bulles

14.4 Tri par insertion

14.5 Comparaison des tris

Applications, travaux dirigés, corrigés et synthèse

Organisation pédagogique indicative

Introduction aux algorithmes de tri

Trier consiste à réorganiser une collection de valeurs selon un ordre. Cet ordre peut être croissant, décroissant, alphabétique, chronologique ou défini par un critère propre à l’application, comme la moyenne d’un étudiant ou le prix d’un produit.

Dans un tableau trié en ordre croissant, chaque élément est inférieur ou égal à l’élément suivant. En ordre décroissant, chaque élément est supérieur ou égal au suivant. Le tri doit conserver toutes les valeurs, y compris les doublons.

14.1 Intérêt du tri

14.1.1 Organisation des données

Le tri donne une structure lisible à un ensemble de données. Il facilite la consultation, la détection des valeurs extrêmes, le repérage des doublons et la production de rapports ordonnés.

14.1.2 Accélération de la recherche

Un tableau trié permet d’utiliser la recherche dichotomique. Cette méthode élimine une moitié de la zone possible à chaque comparaison. Le tri peut donc être rentable lorsque les mêmes données sont recherchées de nombreuses fois.

Pour une seule recherche dans un petit tableau non trié, trier d’abord peut être inutile. En revanche, pour des milliers de recherches dans une liste stable, le coût initial du tri peut être largement amorti.

14.1.3 Classement

Le classement ordonne des objets selon un critère. Une compétition peut classer les participants par score décroissant. Une classe peut être ordonnée par moyenne. Une boutique peut afficher les produits du moins cher au plus cher.

14.1.4 Préparation à d’autres traitements

De nombreux traitements deviennent plus simples après un tri : recherche dichotomique, fusion de listes, suppression des doublons contigus, calcul d’une médiane, regroupement de valeurs identiques ou affichage paginé.

• calcul de la médiane à partir de valeurs ordonnées ;
• regroupement des occurrences d’une même valeur ;
• comparaison de deux listes triées ;
• fusion de deux tableaux déjà triés ;
• détection rapide des doublons adjacents ;
• présentation cohérente dans une interface ou un rapport.

14.1.5 Critère, clé et sens du tri

La clé de tri est l’information utilisée pour comparer deux éléments. Pour des nombres, la clé est souvent la valeur elle-même. Pour un étudiant, elle peut être la moyenne, le nom ou le numéro d’inscription.

Le sens précise si la clé doit évoluer de la plus petite vers la plus grande ou l’inverse. La comparaison utilisée par l’algorithme doit être cohérente avec ce sens.

14.1.6 Propriétés utiles d’un algorithme de tri

Les tris étudiés dans ce chapitre sont simples et comparatifs. Ils sont particulièrement utiles pour comprendre les mécanismes fondamentaux, même si des méthodes plus rapides sont préférées pour de très grands volumes.

14.2 Tri par sélection

14.2.1 Principe général

Le tri par sélection construit progressivement une partie triée au début du tableau. À chaque passe, il recherche le minimum de la partie non triée puis l’échange avec le premier élément de cette partie.

14.2.2 Recherche du minimum

La recherche commence à l’indice i. Une variable indiceMin mémorise la position de la plus petite valeur rencontrée. Chaque élément suivant est comparé au minimum courant.

Recherche du minimum dans une zone

Il est essentiel de mémoriser l’indice et non seulement la valeur, car l’échange doit connaître la case à déplacer.

14.2.3 Échange

Après la recherche, l’élément minimal est placé à la position i. L’ancienne valeur T[i] est déplacée à l’emplacement du minimum grâce à une variable temporaire.

Échange de deux cases

14.2.4 Algorithme complet en ordre croissant

Tri par sélection

La dernière case n’a pas besoin d’une passe propre : lorsque les n - 1 premières valeurs sont correctement placées, la valeur restante est nécessairement la plus grande.

14.2.5 Trace détaillée

Considérons le tableau T = [29, 10, 14, 37, 13].

14.2.6 Version décroissante

Pour trier dans l’ordre décroissant, il suffit de rechercher le maximum de la partie non triée. La structure générale ne change pas.

Modification essentielle

14.2.7 Nombre d’opérations et propriétés

Le nombre de comparaisons ne dépend pas de l’ordre initial. La première passe effectue n - 1 comparaisons, la suivante n - 2, puis n - 3, jusqu’à 1.

Le total vaut n(n - 1) / 2, ce qui correspond à une complexité temporelle quadratique O(n²). Le nombre d’échanges est au plus n - 1, ce qui peut être avantageux lorsque les écritures sont coûteuses.

14.3 Tri à bulles

14.3.1 Principe général

Le tri à bulles compare des éléments voisins. Si deux voisins sont dans le mauvais ordre, ils sont échangés. Après une passe complète de gauche à droite, la plus grande valeur de la zone active atteint sa position définitive à droite.

Le nom évoque une bulle qui remonte progressivement : les grandes valeurs se déplacent vers la fin par échanges successifs.

14.3.2 Échanges successifs

Considérons T = [5, 1, 4, 2, 8]. Pendant la première passe, les comparaisons successives déplacent la valeur 8 vers la dernière case.

14.3.3 Version simple

Tri à bulles non optimisé

La borne n - 2 - i évite de revisiter les dernières cases déjà fixées. L’indice j + 1 reste ainsi au maximum égal à n - 1.

14.3.4 Optimisation par détection d’absence d’échange

Si une passe ne réalise aucun échange, tous les couples voisins sont déjà dans le bon ordre. Le tableau est donc trié et les passes restantes sont inutiles.

Tri à bulles optimisé

14.3.5 Trace des passes

Pour T = [5, 1, 4, 2, 8], la version optimisée produit :

14.3.6 Variante décroissante

Pour obtenir un ordre décroissant, l’échange est déclenché lorsque l’élément gauche est plus petit que l’élément droit.

14.3.7 Nombre d’opérations et propriétés

Sans optimisation, le tri à bulles effectue un nombre quadratique de comparaisons. Avec l’arrêt anticipé, son meilleur cas devient linéaire lorsque le tableau est déjà trié.

14.4 Tri par insertion

14.4.1 Partie triée et partie non triée

Le tri par insertion construit une partie triée à gauche. Il considère d’abord que le premier élément est trié. Puis il prend chaque nouvel élément, appelé clé, et l’insère à la bonne position dans la partie déjà ordonnée.

Cette méthode ressemble à la manière de ranger des cartes dans une main : chaque nouvelle carte est déplacée vers la gauche jusqu’à sa position correcte.

14.4.2 Décalage des éléments

Contrairement à la sélection et aux bulles, l’insertion ne procède pas principalement par échanges. Les valeurs plus grandes que la clé sont décalées d’une case vers la droite, puis la clé est écrite dans la case libérée.

Mécanisme d’insertion

14.4.3 Algorithme complet

Tri par insertion croissant

14.4.4 Trace détaillée

Considérons T = [12, 11, 13, 5, 6].

14.4.5 Cas presque trié

Le tri par insertion est particulièrement efficace lorsque peu d’éléments sont mal placés. Si chaque clé est déjà supérieure ou égale à l’élément précédent, aucune valeur n’est décalée et chaque passe coûte très peu.

14.4.6 Version décroissante

Pour un ordre décroissant, les valeurs plus petites que la clé doivent être décalées vers la droite.

14.4.7 Nombre d’opérations et propriétés

14.5 Comparaison des tris

14.5.1 Simplicité

Les trois algorithmes utilisent des structures élémentaires. La sélection repose sur la recherche d’un minimum, les bulles sur des comparaisons voisines et l’insertion sur l’ouverture d’une place dans une partie triée.

14.5.2 Nombre de comparaisons

La sélection réalise toujours environ n²/2 comparaisons. Les bulles et l’insertion peuvent en réaliser beaucoup moins lorsque le tableau est déjà ou presque trié, à condition d’utiliser la version optimisée du tri à bulles.

14.5.3 Nombre d’échanges ou de déplacements

Le tri par sélection limite les échanges à un par passe. Le tri à bulles peut effectuer un échange pour chaque inversion, donc beaucoup d’écritures. Le tri par insertion effectue des décalages et est souvent avantageux lorsque les éléments sont proches de leur position finale.

14.5.4 Stabilité

Un tri stable conserve l’ordre initial de deux éléments ayant la même clé. Cette propriété est importante lorsqu’un premier classement a déjà été effectué selon un autre critère.

Ali reste avant Lina parce que les deux notes sont égales et qu’Ali apparaissait d’abord. L’insertion et les bulles sont stables dans leurs versions présentées. La sélection simple ne l’est généralement pas, car un échange éloigné peut inverser deux éléments de même clé.

14.5.5 Comportement sur un tableau presque trié

Le tri par insertion est généralement le meilleur des trois dans ce contexte. Le tri à bulles optimisé peut aussi terminer rapidement si une passe ne détecte aucun échange. Le tri par sélection ne profite pas de l’ordre existant, car il cherche systématiquement le minimum restant.

14.5.6 Tableau comparatif global

14.5.7 Choisir une méthode

Applications guidées

Application 1 — Trier des notes

On souhaite trier les notes d’une classe dans l’ordre croissant afin de faciliter le calcul de la médiane et l’analyse de la distribution.

Solution avec tri par insertion

Application 2 — Classer des étudiants

Chaque étudiant possède un nom et une moyenne. Le classement doit être décroissant selon la moyenne. En cas d’égalité, l’ordre initial est conservé grâce à un tri stable.

Tri par insertion sur des enregistrements

Application 3 — Trier des noms

Les chaînes sont comparées selon l’ordre lexicographique. Pour éviter que les majuscules et minuscules produisent un ordre inattendu, on peut comparer des versions normalisées tout en conservant les noms originaux.

Comparaison normalisée

Application 4 — Trier dans l’ordre croissant ou décroissant

Une procédure peut recevoir un paramètre sens. La condition de mauvais ordre est alors calculée selon la valeur de ce paramètre.

Tri à bulles paramétrable

Application 5 — Trier plusieurs informations associées

Supposons que les noms et les notes soient stockés dans deux tableaux parallèles. Chaque déplacement d’une note doit être reproduit sur le nom correspondant. Sinon, les informations seront désynchronisées.

Sélection avec tableaux parallèles

Erreurs fréquentes et stratégie de test

Erreurs fréquentes

Jeux d’essai recommandés

Vérification du résultat

Un test complet vérifie deux propriétés : l’ordre et la conservation des données. Vérifier seulement que le tableau est croissant ne suffit pas si une valeur a été perdue ou dupliquée par erreur.

Vérifier l’ordre croissant

Pour vérifier la conservation, on peut comparer les effectifs de chaque valeur avant et après le tri ou conserver une copie de référence et utiliser un second tri fiable dans un environnement de test.

Travaux dirigés

Exercice 1 — Tracer un tri par sélection

Appliquer le tri par sélection croissant au tableau [18, 6, 12, 3, 10]. Indiquer le minimum, l’échange et le tableau après chaque passe.

Exercice 2 — Compter les comparaisons

Donner le nombre de comparaisons réalisées par le tri par sélection pour n = 5, n = 10 et n = 100.

Exercice 3 — Tracer un tri à bulles

Appliquer le tri à bulles optimisé au tableau [4, 2, 5, 1, 3]. Montrer le tableau après chaque passe et préciser quand l’algorithme s’arrête.

Exercice 4 — Corriger les bornes

L’algorithme suivant contient une erreur :

Identifier l’accès invalide et proposer les bornes correctes.

Exercice 5 — Tracer un tri par insertion

Trier [9, 5, 1, 4, 3] par insertion. Pour chaque clé, indiquer les éléments décalés et la position d’insertion.

Exercice 6 — Version décroissante

Adapter le tri par insertion afin d’ordonner les valeurs du plus grand au plus petit.

Exercice 7 — Trier des noms

Écrire une procédure qui trie un tableau de noms dans l’ordre alphabétique sans modifier la casse des chaînes originales.

Exercice 8 — Classement multi-critères

Classer des étudiants par moyenne décroissante. En cas d’égalité, les classer par nom croissant.

Exercice 9 — Préserver les associations

Deux tableaux contiennent des références de produits et leurs prix. Écrire un tri croissant par prix qui conserve la correspondance entre chaque référence et son prix.

Exercice 10 — Choisir le tri

Choisir parmi sélection, bulles optimisé et insertion pour les situations suivantes : tableau presque trié, écritures très coûteuses, besoin de stabilité, apprentissage des comparaisons voisines. Justifier.

Exercice 11 — Tester la stabilité

On dispose de [A(12), B(15), C(12), D(15)]. Donner le résultat attendu d’un tri stable par note croissante et expliquer comment détecter une perte de stabilité.

Exercice 12 — Vérifier un tri

Écrire une fonction EstTrie(T, n, sens) qui vérifie un ordre croissant ou décroissant selon le paramètre sens.

Corrigés indicatifs des travaux dirigés

Corrigé 1 — Tri par sélection

Corrigé 2 — Nombre de comparaisons

Le nombre est n(n - 1) / 2.

Corrigé 3 — Tri à bulles

Corrigé 4 — Bornes correctes

Lorsque j = n - 1 - i, l’accès T[j + 1] peut dépasser la zone valide à la première passe. La boucle interne doit s’arrêter à n - 2 - i et la boucle externe à n - 2.

Corrigé 5 — Tri par insertion

Corrigé 6 — Insertion décroissante

Corrigé 7 — Trier des noms

Corrigé 8 — Classement multi-critères

Un étudiant A doit passer avant B si sa moyenne est plus grande, ou si les moyennes sont égales et son nom vient avant celui de B.

Condition de déplacement en insertion

Corrigé 9 — Références et prix

À chaque échange de prix, les références correspondantes doivent également être échangées.

Une meilleure modélisation consiste à créer un enregistrement Produit contenant la référence et le prix.

Corrigé 10 — Choix du tri

Corrigé 11 — Stabilité

Le résultat stable est A(12), C(12), B(15), D(15). A reste avant C et B reste avant D. Une inversion de ces couples signale que le tri n’a pas conservé l’ordre relatif des égalités.

Corrigé 12 — Vérifier un tri

Synthèse du chapitre

Le tri organise les données selon une clé et un sens. Le tri par sélection place successivement les minima et limite le nombre d’échanges. Le tri à bulles compare les voisins et peut s’arrêter lorsqu’une passe ne réalise aucun échange. Le tri par insertion place chaque nouvelle clé dans une partie déjà triée et se montre particulièrement efficace sur de petits tableaux presque ordonnés.

Checklist de conception

1.  Définir la clé et le sens du tri.

2.  Choisir une méthode compatible avec la taille et l’état des données.

3.  Fixer correctement les bornes des boucles.

4.  Préserver la valeur temporaire avant tout écrasement.

5.  Déplacer ensemble les informations associées.

6.  Décider si la stabilité est nécessaire.

7.  Prévoir les tableaux vides, unitaires et contenant des doublons.

8.  Tester les cas déjà trié et inversé.

9.  Vérifier l’ordre du résultat.

10.  Vérifier que toutes les données ont été conservées.

Glossaire

Auto-évaluation