Tri bulle

Presentation

L’algorithme du tri bulle - ou bubble sort - consiste à regarder les différentes valeurs adjacentes d’un tableau, et à les permuter si le premier des deux éléments est supérieur au second. L’algorithme se déroule ainsi : les deux premiers éléments du tableau sont comparés, si le premier élément est supérieur au second, une permutation est effectuée. Ensuite, sont comparés et éventuellement permutés les valeurs 2 et 3, 3 et 4 jusque (n-1) et n. Une fois cette étape achevée, il est certain que le dernier élément du tableau est le plus grand. L’algorithme reprend donc pour classer les (n-1) éléments qui précédent. L’algorithme se termine quand il n’y a plus de permutations possibles. Pour classer les n valeurs du tableau, il faut, au pire, effectuer l’algorithme n fois.

Cet algorithme porte le nom de tri bulle car, petit à petit, les plus grands éléments du tableau remontent, par le jeu des permutations, en fin de tableau. Dans un aquarium il en va de même : les plus grosses bulles remontent plus rapidement à la surface que les petites qui restent collés au fond.

Il existe plusieures variantes de cet algorithme :
 La première consiste à n’effectuer les comparaisons que sur les éléments du tableau qui ne sont pas remontés à la surface. Ainsi, si n est le nombre d’éléments du tableau et p le nombre de fois où le parcours complet du tableau a été effectué, a chaque itération, seul les (n-p) premiers éléments sont comparés. Le gain de temps apporté par cette otimisation est d’ailleurs loin d’être négligeable, c’est pourquoi une version de ce tri bulle optimisé est également présentée.
 Une autre variante du tri bulle, qui n’est pas très différente, consiste à faire descendre les plus petites valeurs au début du tableau. Dans ce cas, le tableau est parcouru, non plus de gauche à droite, mais de droite à gauche. Dans sa version optimisée, ce sont les (n-p) derniers éléments qui sont comparés. Cette variante est utilisée pour implémenter le tri bulle dans le cas de listes ou de piles.
 La seconde consiste à reprendre au début chaque fois qu’une permutation est détectée. Ainsi, les plus petits et les plus grands éléments vont tout doucement migrer en début et en fin de tableau. Cette version de l’algorithme est aussi connue sous le nom de "tri Shaker" ou de "tri Shuttle".
 Une autre version est le "tri Boustrophedon" ou "bidirectionnel". Elle consiste à parcourir le tableau de gauche à droite, puis de droite à gauche, le changement de direction ayant lieu chaque fois que l’une des extrémités est atteinte. Ainsi, les plus petits éléments du tableau descendent au même rythme que remontent les plus gros éléments.

Exemple

Evolution du tableau au fil de l’algorithme (en bleu, les éléments qui sont comparés, et éventuellement premutés, pour passer à la ligne suivante).

L’algorithme se termine car il n’y a plus de permutations possibles. Ce fait sera constaté grace à un dernier parcours du tableau ou aucune permutation n’a lieu.

Complexité

Considérons la complexité, en nombre d’opérations du tri bulle, pour un tableau ou une liste de n éléments. Dans le pire des cas, ce qui correspond à un tableau préalablement trié de manière décroissante, il a des permutations jusqu’à ce que la liste ait été parcourue (n-1) fois.

Dans le cas du tri bulle non optimisé, cela reviens à faire (n-1) fois (n-1) comparaisons (et quelques permutations). Soit une complexité proportionnelle à (n-1)²=n²-2n+1, soit en O(n²).

Dans le cas du tri bulle optimisé, le nombre de comparaisons est donné grace au calcul suivant, soit une complexité moins élevée, mais toujours en O(n²)

 Accueil des algorithmes de tri
 Article précédent : la fonction échanger
 Article suivant : le tri par creation