Tri à bulles

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

Principe et pseudo-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 à sa 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 des éléments possiblement encore en désordre (boucle interne) est effectué sans échange. En effet, cela signifie que tout 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é

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

Application du tri à bulles au tableau de nombres « 5 1 4 2 8 » ; pour chaque étape, les éléments comparés sont en gras.

Étape 1.
1.1. ( 5 1 4 2 8 ) ( 1 5 4 2 8 ). Les nombres 5 et 1 sont comparés, et comme 5 > 1, l'algorithme les échange.
1.2. ( 1 5 4 2 8 ) ( 1 4 5 2 8 ). Échange, car 5 > 4.
1.3. ( 1 4 5 2 8 ) ( 1 4 2 5 8 ). Échange, car 5 > 2.
1.4. ( 1 4 2 5 8 ) ( 1 4 2 5 8 ). Pas d'échange, car 5 < 8.
À la fin de cet étape, un nombre est à sa place définitive, le plus grand : 8.
Étape 2.
2.1. ( 1 4 2 5 8 ) ( 1 4 2 5 8 ). Pas d'échange.
2.2. ( 1 4 2 5 8 ) ( 1 2 4 5 8 ). Échange.
2.3. ( 1 2 4 5 8 ) ( 1 2 4 5 8 ). Pas d'échange.
5 et 8 ne sont pas comparés puisqu'on sait que le 8 est déjà à sa place définitive.
Par hasard, tous les nombres sont déjà triés, mais cela n'est pas encore détecté par l'algorithme.
Étape 3.
3.1. ( 1 2 4 5 8 ) ( 1 2 4 5 8 ). Pas d'échange.
3.2. ( 1 2 4 5 8 ) ( 1 2 4 5 8 ). Pas d'échange.
Les deux derniers nombres sont exclus des comparaisons, puisqu'on sait qu'ils sont déjà à leur place définitive.
Puisqu'il n'y a eu aucun échange durant cette étape 3, le tri optimisé se termine.
Étape 4.
4.1. ( 1 2 4 5 8 ) ( 1 2 4 5 8 ). Pas d'échange.
Le tri est terminé, car on sait que les 4 plus grands nombres, et donc aussi le 5e, sont à leur place définitive.
Other Languages