Le tri
à bulles ou tri
par propagation est un algorithme de tri qui consiste à faire
remonter progressivement les plus grands éléments d'un tableau, comme les bulles 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.
Aucun commentaire:
Enregistrer un commentaire