Les TRIS en algorithmique : 3�me partie (Tri Bulles)

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 1^er 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 2^eme 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^�mebalayage 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.