Tri à bulles

Algorithme quadratique, T(n) = O(n²), en moyenne et dans le pire des cas, stable et en place.  Le « tri bulle » est une variante du tri par sélection. Il consiste à parcourir le tableau tab en permutant toute paire d'éléments consécutifs (tab[k],tab[k+1]) non ordonnés - ce qui est un échange et nécessite donc encore une variable intermédiaire de type entier. Après le premier parcours, le plus grand élément se retrouve dans la dernière case du tableau, en tab[N], et il reste donc à appliquer la même procédure sur le tableau composé des éléments tab[1], ..., tab[N-1]. Le nom de ce tri provient du déplacement des « bulles » les plus grandes vers la droite.

La procédure de tri bulle est la suivante :

procedure triBulle(entier[] tab)

   entier i, k;

   entier tmp;

   pour (i de N à 2 en décrémentant de 1) faire

      pour (k de 1 à i-1 en incrémentant de 1) faire

         si (tab[k] > tab[k+1]) alors

            tmp <- tab[k];

            tab[k] <- tab[k+1];

            tab[k+1] <- tmp;

         fin si

      fin pour

   fin pour

fin procedure