Le tri par propagation ou tri bulle - avec explication -

Le tri bulle est une sort du tri par sélection.
 

Ce tri consiste à parcourir le tableau tab en permutant toute paire d'éléments consécutifs (T[k],T[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 1er parcours, le plus grand élément se retrouve dans la dernière case du tableau, en T[N], et il reste donc à appliquer la même procédure sur le tableau composé des éléments (T[1], T[2], ..., T[N-1]).

Le nom de ce tri provient du déplacement des " bulles " les plus grandes vers la droite.

/* Procédure de tri bulle */

procedure triBulle(entier[] T)

   entier i, k;

   entier temp;

   pour i allant de N à 2 [-1] faire

      pour k allant de 1 à i-1 [1] faire

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

            temp <- T[k];

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

            T[k+1] <- temp;

         fin si

      fin pour

   fin pour

fin procedure

Le nombre de comparaisons dans la procédure de tri bulle est le même que pour le tri par sélection :

Le nombre d'échanges quant à lui dépend de l'ordre des éléments dans le tableau :

• Dans le meilleur des cas, le tableau initial est trié et il n'y a pas d'échange à faire .
• En moyenne, on montre que le nombre d'échanges est de :

• Dans le pire des cas, les entiers du tableau sont initialement donnés dans l'ordre décroissant. Dans ce cas, on effectue l'échange à chaque comparaison, c'est-à-dire que le nombre d'échanges est alors de :
  
  

  

Quoi qu'il en soit, la complexité du tri bulle reste en O (N²), c'est-à-dire du même ordre de grandeur que le carré du nombre d'éléments.