Le tri à bulle

Le tri à bulle

Définition

• Le tri à bulle consiste à parcourir un tableau, par exemple de gauche à droite, en comparant les éléments côte à côte et en les permutant s’ils ne sont pas dans le bon ordre. Au cours d’une passe du tableau, les plus grands éléments remontent de proche en proche vers la droite comme des bulles vers la surface.
• On s’arrête dès que l’on détecte que le tableau est trié : si aucune permutation n’a été faite au cours d’une passe.
• Le tri à bulles ou tri par propagation est un algorithme de tri. Il consiste à comparer répétitivement les éléments consécutifs d’un tableau, et à les permuter lorsqu’ils sont mal triés. Il doit son nom au fait qu’il déplace rapidement les plus grands éléments en fin de tableau, comme des bulles d’air qui remonteraient rapidement à la surface d’un liquide.

Principe

• Le tri à bulle fait remonter les grands éléments vers la fin du tableau.
• Cette migration le long du tableau s’effectue par permutation successive.
• L’algorithme parcourt le tableau et compare les éléments adjacents. Lorsque les éléments ne sont pas dans l’ordre, ils sont échangés.
• Après un premier parcours complet du tableau, le plus grand élément est forcément en fin de tableau, à sa position définitive. En effet, aussitôt que le plus grand élément est rencontré durant le parcours, il est mal trié par rapport à tous les éléments suivants, donc échangé à chaque fois jusqu’à la fin du parcours.
• Après le premier parcours, le plus grand élément étant à sa position définitive, il n’a plus à être traité. Le reste du tableau est en revanche encore en désordre. Il faut donc le parcourir à nouveau, en s’arrêtant à l’avant-dernier élément. Après ce deuxième parcours, les deux plus grands éléments sont à leur position définitive. Il faut donc répéter les parcours du tableau, jusqu’à ce que les deux plus petits éléments soient placés à leur position définitive.

Le tri à bulle consiste à parcourir le tableau, tant qu’il n’est pas trié,et à permuter les couples d’éléments consécutifs mal ordonnés. On sait que le tableau est trié si lors d’un parcours, aucun couple d’éléments n’a été
permuté.

Code de départ

tri_à_bulles(Tableau T)
   pour i allant de taille de T - 1 à 1
       pour j allant de 0 à i - 1
           si T[j+1] < T[j]
               échanger(T[j+1], T[j])

Code amélioré (Optimisé)

tri_à_bulles_optimisé(Tableau T)
    pour i allant de taille de T - 1 à 1
        tableau_trié := vrai
        pour j allant de 0 à i - 1
            si T[j+1] < T[j]
                échanger(T[j+1], T[j])
                tableau_trié := faux
        si tableau_trié
            fin tri_à_bulles_optimisé