Tri à bulles

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Tableau de nombres représenté en 2 dimensions : en abscisse la position du nombre dans le tableau, en ordonnée la valeur du nombre. On voit qu'avec le tri à bulles, les grands nombres trouvent leur position finale avant les petits.
Visualisation statique du tri : les étapes vont de gauche à droite. À chaque étape un échange est fait. La couleur la plus foncée a le plus de valeur et trouve sa place définitive (en bas) en premier.

Le tri à bulles ou tri par propagation est un algorithme de tri. Il consiste à comparer répétitivement les éléments consécutifs d'un tableau, et à les permuter lorsqu'ils sont mal triés. Il doit son nom au fait qu'il déplace rapidement les plus grands éléments en fin de tableau, comme des bulles d'air qui remonteraient rapidement à la surface d'un liquide.

Le tri à bulles est souvent enseigné en tant qu'exemple algorithmique, car son principe est simple. Mais c'est le plus lent des algorithmes de tri communément enseignés, et il n'est donc guère utilisé en pratique.

Algorithme de base[modifier | modifier le code]

Principe et pseudo-code[modifier | modifier le code]

L'algorithme parcourt le tableau et compare les éléments adjacents. Lorsque les éléments ne sont pas dans l'ordre, ils sont échangés.

Après un premier parcours complet du tableau, le plus grand élément est forcément en fin de tableau, à sa position définitive. En effet, aussitôt que le plus grand élément est rencontré durant le parcours, il est mal trié par rapport à tous les éléments suivants, donc échangé à chaque fois jusqu'à la fin du parcours.

Après le premier parcours, le plus grand élément étant à position définitive, il n'a plus à être traité. Le reste du tableau est en revanche encore en désordre. Il faut donc le parcourir à nouveau, en s'arrêtant à l'avant-dernier élément. Après ce deuxième parcours, les deux plus grands éléments sont à leur position définitive. Il faut donc répéter les parcours du tableau, jusqu'à ce que les deux plus petits éléments soient placés à leur position définitive.

Le pseudo-code suivant est repris de Bubble Sort: An Archaeological Algorithmic Analysis qui le reprend de Knuth.

tri_à_bulles(Tableau T)
   pour i allant de taille de T - 1 à 1
       pour j allant de 0 à i - 1
           si T[j+1] < T[j]
               échanger(T[j+1], T[j])

Une optimisation courante de ce tri consiste à l'interrompre dès qu'un parcours entier est effectué sans échange. En effet, cela signifie que le tableau est trié. Cette optimisation nécessite une variable supplémentaire.

tri_à_bulles_optimisé(Tableau T)
    pour i allant de taille de T - 1 à 1
        tableau_trié := vrai
        pour j allant de 0 à i - 1
            si T[j+1] < T[j]
                échanger(T[j+1], T[j])
                tableau_trié := faux
        si tableau_trié
            fin tri_à_bulles_optimisé

Complexité[modifier | modifier le code]

Pour le tri non optimisé, la complexité en temps est de Θ(n2), avec n la taille du tableau.

Pour le tri optimisé, le nombre d'itérations de la boucle externe est compris entre 1 et n. En effet, on peut démontrer qu'après la i-ème étape, les i derniers éléments du tableau sont à leur place. À chaque itération, il y a exactement n-1 comparaisons et au plus n-1 échanges.

  • Le pire cas (n itérations) est atteint lorsque le plus petit élément est à la fin du tableau. La complexité est alors Θ(n2).
  • En moyenne, la complexité est aussi Θ(n2). En effet, le nombre d'échanges de paires d'éléments successifs est égal au nombre d'inversions de la permutation, c'est-à-dire de couples (i,j) tels que i < j et T(i) > T(j). Ce nombre est indépendant de la manière d'organiser les échanges. Lorsque l'ordre initial des éléments du tableau est aléatoire, il est en moyenne égal à n(n-1)/4 [1].
  • Le meilleur cas (une seule itération) est atteint quand le tableau est déjà trié. Dans ce cas, la complexité est linéaire.

Exemple étape par étape[modifier | modifier le code]

Prenons la liste de chiffres « 5 1 4 2 8 » et trions-la de manière croissante en utilisant l'algorithme de tri à bulles. Pour chaque étape, les éléments comparés sont écrits en gras.

Première étape:
( 5 1 4 2 8 ) ( 1 5 4 2 8 ) Les éléments 5 et 1 sont comparés, et comme 5 > 1, l'algorithme les intervertit.
( 1 5 4 2 8 ) ( 1 4 5 2 8 ) Échange car 5 > 4.
( 1 4 5 2 8 ) ( 1 4 2 5 8 ) Échange car 5 > 2.
( 1 4 2 5 8 ) ( 1 4 2 5 8 ) Comme 5 < 8, les éléments ne sont pas échangés.
Deuxième étape:
( 1 4 2 5 8 ) ( 1 4 2 5 8 ) Même principe qu'à l'étape 1.
( 1 4 2 5 8 ) ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
À ce stade, la liste est triée, mais pour le détecter, l'algorithme doit effectuer un dernier parcours.
Troisième étape:
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
Comme la liste est triée, aucun échange n'a lieu à cette étape, ce qui provoque l'arrêt de l'algorithme.

Variantes de l'algorithme[modifier | modifier le code]

Tri cocktail[modifier | modifier le code]

Un dérivé du tri à bulles est le tri cocktail ou tri shaker. Cette méthode de tri est basée sur l'observation suivante : dans le tri à bulles, les éléments peuvent avancer rapidement vers la fin du tableau, mais ne sont déplacés vers le début du tableau que d'une position à la fois.

L'idée du tri cocktail consiste à alterner le sens du parcours. On obtient un tri un peu plus rapide, d'une part parce qu'il nécessite moins de comparaisons[2], d'autre part parce qu'il relit les données les plus récentes lors du changement de sens (elles sont donc encore dans la mémoire cache). Cependant, le nombre d'échanges à effectuer est identique (voir ci-dessus). Ainsi, le temps d'exécution est toujours proportionnel à n2 donc médiocre.

Tri jump-down[3][modifier | modifier le code]

Le code de ce tri ressemble énormément au tri à bulles. Tout comme le tri à bulles, ce tri fait remonter en premier les plus grands éléments. Toutefois, il ne travaille pas sur des éléments adjacents ; il compare chaque élément du tableau avec celui qui est à la place du plus grand, et échange lorsqu'il trouve un nouveau plus grand.

tri_à_bulles(Tableau T)
   pour i allant de taille de T - 1 à 1
       pour j allant de 0 à i - 1
           si T[i] < T[j]
               échanger(T[i], T[j])

Tri Combsort[modifier | modifier le code]

Une variante du tri à bulles, nommée Tri Combsort, fut développée en 1980 par Wlodek Dobosiewicz et réapparut en avril 1991 dans Byte Magazine. Elle corrige le défaut majeur du tri à bulles que sont les tortues et rend l'algorithme aussi efficace que le tri rapide.

Voir aussi[modifier | modifier le code]

Liens externes[modifier | modifier le code]

Notes et références[modifier | modifier le code]

  1. On définit Xij = 0 si T(i) < T(j) et Xij = 1 sinon. Si l'ordre des éléments est aléatoire, alors l'espérance E(Xij) vaut 1/2 pour tous i, j (ij). Il y a n(n-1)/2 couples (i,j) tels que 0 ≤ i < j < n. Par linéarité de l'espérance, le nombre moyen d'inversions est donc n(n-1)/4.
  2. Donald E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching, Addison-Wesley 1973, (ISBN 978-0-201-03803-3) (section 5.2.2, p. 110)
  3. Bubble Sort: An Archaeological Algorithmic Analysis, Owen Astrachan, Computer Science Department, Duke University