Pages

jeudi 17 novembre 2011

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 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

Partenaires

Computers Blogs

Contactez-nous

Nom

E-mail *

Message *

Tous droits resérvés-www.exercices-corriges.com Seo Blogger Templates