Prog-Info > C++ > Tri et Recherche > Le tri bulle.

---

Le tri à bulle

Cet algorithme consiste à comparer les différentes valeurs adjacentes d'un tableau. Les éléments 0 et 1 sont comparés. Si le premier est supérieur au second, on effectue une permutation. Ensuite on fait de même avec les éléments 1 et 2, 2 et 3, etc... Dans cette étape, il y a n-1 tests et on est sûr que le plus grand élément se trouve à la fin du tableau. Il reste à traiter les n-1 premiers éléments.
L'algorithme se termine lorsqu'il n'y a plus de permutations possibles.
Le pire des cas est lorsque le tableau est classé par ordre décroissant.

void triABulle(int tableau[], int longueur) {    int i;    bool permutation;    do    {       permutation = false;       for(i=0; i<longueur-1; i++)       {          if(tableau[i]>tableau[i+1])          {             echanger(tableau, i, i+1);             permutation = true;          }       }       longueur--;    }    while(permutation); }

Exemple :
Les différentes étapes de l'algorithme :

7	3	0	1	9	6
3	7	0	1	9	6
3	0	7	1	9	6
3	0	1	7	9	6
3	0	1	7	9	6
3	0	1	7	6	9
0	3	1	7	6	9
0	1	3	7	6	9
0	1	3	7	6	9
0	1	3	6	7	9

Complexité :
Calculons le nombre de passages dans le pire des cas : (n-1)+(n-2)+ ... +2+1 = n*n/2 - n/2.
Si le tableau est déjà bien trié, cela ne prendra pas beaucoup de temps.