Tri à Bulles : Implémentation et Trace d'Exécution

Introduction

Dans la leçon précédente, nous avons exploré le tri par sélection, une méthode qui consiste à trouver le plus petit élément et à le mettre à sa place. C'est une approche globale, car à chaque étape, nous parcourons toute la partie non triée du tableau.

Aujourd'hui, nous allons aborder le problème du tri sous un angle différent avec le tri à bulles (bubble sort). Cet algorithme a une approche plus "locale" : il se concentre sur la comparaison et l'échange d'éléments voisins (adjacents). Son nom vient de l'idée que les plus grands éléments "remontent" progressivement vers la fin du tableau, comme des bulles d'air à la surface de l'eau.

L'objectif de cette leçon est de vous permettre d'implémenter l'algorithme du tri à bulles en pseudo-code et de savoir tracer son exécution pas à pas pour n'importe quel tableau.

1. Le principe du tri à bulles

L'idée fondamentale du tri à bulles est de parcourir le tableau plusieurs fois. À chaque parcours, on compare chaque élément avec son voisin de droite. S'ils sont dans le mauvais ordre (c'est-à-dire que l'élément de gauche est plus grand que celui de droite), on les échange.

Ce processus a un effet intéressant : après le tout premier parcours complet, le plus grand élément du tableau se retrouvera inévitablement à la toute dernière position, sa place définitive. Après le deuxième parcours, le deuxième plus grand élément sera à l'avant-dernière position, et ainsi de suite.

Pour bien visualiser ce mécanisme, je vous invite à lire la première partie de la ressource suivante qui décrit ce processus avec un exemple simple.

2. Tracer l'exécution complète

Comme vous l'avez vu, un seul passage ne suffit pas (sauf si le plus grand élément était le seul mal placé). Il faut répéter ce processus. Chaque parcours complet du tableau est appelé une passe.

Après chaque passe, la partie non triée du tableau se réduit d'un élément par la fin, car un nouvel élément (le plus grand de la partie restante) a trouvé sa place définitive.

L'image ci-dessous illustre ce déroulement sur plusieurs passes.

3. Formalisation en pseudo-code

Maintenant que le principe des passes successives est clair, nous pouvons le traduire en algorithme. Pour cela, nous aurons besoin, comme pour le tri par sélection, de deux boucles imbriquées :

• Une boucle externe qui contrôle le nombre de passes. À chaque passe, la taille de la portion de tableau à trier diminue de 1.
• Une boucle interne qui parcourt la portion non triée du tableau, compare les éléments adjacents et les échange si nécessaire.

Le document suivant présente un pseudo-code clair et standard pour cet algorithme.

Analysons ensemble ce pseudo-code :

PROCEDURE tri_bulles(T)
    N ← taille de T
    // Boucle externe : contrôle les passes
    POUR i DE N - 1 À 1 FAIRE
        // Boucle interne : compare et échange les éléments adjacents
        POUR j DE 0 À i - 1 FAIRE
            SI T[j] > T[j + 1] ALORS
                ECHANGER T[j] ET T[j + 1]
            FIN SI
        FIN POUR
    FIN POUR
FIN PROCEDURE

Décortiquons les boucles :

• POUR i DE N - 1 À 1 FAIRE : C'est la boucle des passes. i représente l'index de la "frontière" entre la partie non triée (à gauche) et la partie déjà triée (à droite).

  • Au premier tour, i vaut N-1. La boucle interne ira jusqu'à l'index N-2 pour comparer T[N-2] et T[N-1]. Cela placera le plus grand élément en T[N-1].
  • Au tour suivant, i vaut N-2. La boucle interne s'arrêtera à l'index N-3, car nous savons que T[N-1] est déjà à sa place.
  • La boucle s'arrête quand i vaut 1, ce qui effectue la dernière comparaison nécessaire entre T[0] et T[1].

• POUR j DE 0 À i - 1 FAIRE : C'est la boucle qui effectue le "bullage". j parcourt la partie non triée du tableau. La condition T[j] > T[j+1] vérifie si les deux voisins sont dans le bon ordre. Si ce n'est pas le cas, on les échange.

4. À vous de jouer !

Votre préférence allant à la pratique, c'est le moment de prendre une feuille et un crayon. Cet exercice est crucial pour solidifier votre compréhension.

Exercice :
Triez le tableau T = [6, 9, 8, 2, 1, 4] en utilisant l'algorithme du tri à bulles.

Pour chaque passe (chaque valeur de i de la boucle externe), détaillez l'état du tableau après chaque échange.

Par exemple, pour la première passe (i=5), vous montrerez l'état du tableau après la comparaison de (6,9), puis (9,8), etc.

Conclusion

Félicitations ! Vous avez maintenant une compréhension pratique du tri à bulles. C'est le deuxième algorithme de tri simple que vous maîtrisez, après le tri par sélection. Même si, comme le tri par sélection, il n'est pas très performant sur de grandes quantités de données, sa logique de comparaison locale est un concept important en algorithmique.

Points clés à retenir :

• Le tri à bulles fonctionne en comparant et en échangeant des paires d'éléments adjacents.
• Il s'exécute en plusieurs passes. Après chaque passe, un élément supplémentaire est garanti d'être à sa position finale.
• Les plus grands éléments "remontent" progressivement vers la fin du tableau.
• Son implémentation typique utilise deux boucles POUR imbriquées.

Et après ?

Nous avons vu une méthode qui sélectionne le minimum global (tri par sélection) et une qui compare les voisins (tri à bulles). Dans la prochaine leçon, nous découvrirons une troisième approche avec le tri par insertion. Cette méthode s'inspire de la façon dont beaucoup de gens trient un jeu de cartes : en prenant les cartes une par une et en les insérant à la bonne place dans la partie déjà triée. Cela nous donnera une nouvelle perspective sur la résolution de problèmes de tri.