Le tri à bulles ou tri par propagation

Attention ! cette page va être migrée vers https://lwh-21.github.io/Algos/

Le tri bulle

Le principe du tri à bulles (bubble sort ou sinking sort) est de comparer deux à deux les éléments e1 et e2 consécutifs d'un tableau et d'effecteur une permutation si e1 > e2. On continue de trier jusqu'à ce qu'il n'y ait plus de permutation.

L'animation ci-après détaille le fonctionnement du tri bulle :

Démonstration du tri à bulles

  1. PROCEDURE tri_bulle ( TABLEAU a[1:n])
  2. passage ← 0
  3. REPETER
  4.     permut ← FAUX
  5.     POUR i VARIANT DE 1 A n - 1 - passage FAIRE
  6.         SI a[i] > a[i+1] ALORS
  7.             echanger a[i] ET a[i+1]
  8.             permut ← VRAI
  9.         FIN SI
  10.     FIN POUR
  11.     passage ← passage + 1
  12. TANT QUE permut = VRAI
  1. let tri_bulle tableau =
  2.     let passage= ref 1 and permutation = ref true in
  3.     while (!permutation = true) do
  4.         permutation := false;
  5.         passage := !passage + 1;
  6.         for en_cours = 0 to (Array.length tableau) - !passage do
  7.             if tableau.(en_cours) > tableau.(en_cours + 1) then
  8.             begin
  9.                 (* On echange les deux elements *)
  10.                 permutation := true;
  11.                 let temp = tableau.(en_cours) in
  12.                 begin
  13.                    tableau.(en_cours) <- tableau.(en_cours + 1);
  14.                    tableau.(en_cours + 1) <- temp;
  15.                 end
  16.             end
  17.         done;
  18.     done;
  19. tableau;;
  1. type tab = array[1..20] of integer;
  2. procedure tri_bulle(var tableau : tab);
  3. var permutation : boolean;
  4.     en_cours : integer;
  5.     temp : integer;
  6.     passage : integer;
  7.  
  8. begin
  9.     passage := 1;
  10.     REPEAT
  11.         permutation := false;
  12.         for en_cours := 1 to 20 - passage do
  13.         begin
  14.             if (tableau[en_cours] > tableau[en_cours + 1]) then
  15.             begin
  16.                 { on échange les deux éléments }
  17.                 temp := tableau[en_cours];
  18.                 tableau[en_cours]:=tableau[en_cours + 1];
  19.                 tableau[en_cours + 1]:=temp;
  20.                 permutation := true;
  21.             end;
  22.         end;
  23.         passage := passage + 1;
  24.     UNTIL (not permutation);
  25. end;
  1. def tri_bulle(tableau):
  2.     permutation = True
  3.     passage = 0
  4.     while permutation == True:
  5.         permutation = False
  6.         passage = passage + 1
  7.         for en_cours in range(0, len(tableau) - passage):
  8.             if tableau[en_cours] > tableau[en_cours + 1]:
  9.                 permutation = True
  10.                 # On echange les deux elements
  11.                 tableau[en_cours], tableau[en_cours + 1] = \
  12.                 tableau[en_cours + 1],tableau[en_cours]
  13.     return tableau  
  1. void tri_bulle(int* tableau)
  2. {
  3.     int passage = 0;
  4.     bool permutation = true;
  5.     int en_cours;
  6.    
  7.     while ( permutation) {
  8.         permutation = false;
  9.         passage ++;
  10.         for (en_cours=0;en_cours<20-passage;en_cours++) {
  11.             if (tableau[en_cours]>tableau[en_cours+1]){
  12.                 permutation = true;
  13.                 // on echange les deux elements
  14.                 int temp = tableau[en_cours];
  15.                 tableau[en_cours] = tableau[en_cours+1];
  16.                 tableau[en_cours+1] = temp;
  17.             }
  18.         }
  19.     }
  20. }

Si on applique cet algorithme au petit jeu de la page précédente, on obtient :



 


Complexité du tri bulle

Dans le meilleur des cas, avec des données déjà triées, l'algorithme effectura seulement n - 1 comparaisons. Sa complexité dans le meilleur des cas est donc en Θ(n).

Complexite du tri bulle dans le meilleur des cas Nombre d'opérations Nombre d'elements à trier Θ(n)

Dans le pire des cas, avec des données triées à l'envers, les parcours successifs du tableau imposent d'effectuer (n2-n)/2 comparaisons et échanges. On a donc une complexité dans le pire des cas du tri bulle en Θ(n2).

Complexite du tri bulle le meilleur des cas Nombre d'opérations Nombre d'elements à trier Θ(n2)

Si tous les éléments de la série à trier sont distincts et que toutes leurs permutations sont équiprobables, la complexité en moyenne de l'algorithme est de l'ordre de (n2-n)/4 comparaisons et échanges. La complexité en moyenne du tri bulle est donc également en Θ(n2)

Complexite du tri bulle en moyenne Nombre d'opérations Nombre d'elements à trier Θ(n2)

Parmi les variantes du tri bulle on peut citer le tri Shuttle.Cet algorithme de tri fonctionne comme le tri bulle mais change de direction à chaque fois qu'il est parvenu à une extrémité.

On peut également citer le tri de Oyelami ou le tri à "peigne" qui reprend des caractéristiques du tri Shell et du tri à bulles.