LES TRIS EN ALGORITHMIQUE : 3ÈME PARTIE (TRI BULLES)
Le tri à bulles ou tri par propagation est un algorithme detri qui consiste à faire remonter progressivement les plus grands éléments d'un tableau, comme lesbulles d'air remontent à la surface d'un liquide.
Le principe du tri Bulles :
La méthode consiste à faire plusieurs balayages du tableau en ordonnant les paires d’éléments adjacents, de bas en haut.
A la fin du premier balayage, l’élément le plus grand est remonté au sommet du tableau comme une bulle d’air dans l’eau.
Lors du deuxième balayage, on ne considère que la partie non triée du tableau pour obtenir à la fin le deuxième plus grand élément sous le plus grand et ainsi de suite jusqu’à ce que le tableau soit complétement trié (par ordre croissant).
Algorithme du tri par Bulles :
Var
T : tableau [1..100] de réels ;
n,v,i : entiers ;
aux : réel ;
Début
v <-- n ;
Tantque v>1 faire
Pour i <--1 à (v-1) faire
Si T[i] > T[i+1] alors
Aux = T[i] ;
T[i] = T [i+1] ;
T [i+1] = aux ;
FinSi
FinPour i
v <-- v-1 ;
Fin
On note que v est le compteur des balayages, il varie entre n et 2 et dans chaque cas de figure i variera entre 1 et (v-1).
aux est la variable auxiliaire servant pour la permutation des éléments comparés, s’ils sont en désordre.
Exemple d’utilisation :
Soit le tableau suivant composé de 5 éléments (n=5).
7
|
3
|
14
|
5
|
10
|
1er Balayage
|
7
|
3
|
14
|
5
|
10
|
7
|
3
|
14
|
10
|
5
|
7
|
14
|
3
|
10
|
5
|
14
|
7
|
3
|
10
|
5
|
A la fin du 1er Balayage l’élément 14 est au sommet du tableau.
2ème Balayage
|
14
|
7
|
3
|
10
|
5
|
14
|
7
|
10
|
3
|
5
|
14
|
10
|
7
|
3
|
5
|
A la fin du 2eme Balayage l’élément 10 est en dessous du plus grand élément.
3ème Balayage
|
14
|
10
|
7
|
3
|
5
|
14
|
10
|
7
|
5
|
3
|
14
|
10
|
7
|
5
|
3
|
A la fin du 3ème balayage le tableau est bel et bien trié.
Conclusion :
Le tri à bulles est souvent enseigné en tant qu'exemple algorithmique. Cependant, sa complexité est de l'ordre de n² en moyenne (où n est la taille du tableau), ce qui le classe parmi les mauvais algorithmes de tri. Il n'est donc quasiment pas utilisé en pratique.
Ads
