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.

Problèmes liés	Algorithme de tri, tri stable (en), tri par comparaison
Structure des données	Tableau

Complexité en temps
Pire cas	$O(n^{2})$
Moyenne	$O(n^{2})$
Meilleur cas	$O(n)$

Complexité en espace
Pire cas	$O(1)auxiliary$

Le tri à bulles ou tri par propagation^[1] 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.

Visualisation statique du tri : les étapes vont de gauche à droite. À chaque étape une permutation est faite. La couleur la plus foncée a le plus de valeur et trouve sa place définitive (en bas) en premier.

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

Principe et pseudo-code modifier

L'algorithme parcourt le tableau et compare les éléments consécutifs. Lorsque deux éléments consécutifs ne sont pas dans l'ordre, ils sont permuté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 permuté avec le suivant jusqu'à arriver à 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^[2].

Le pseudo-code suivant^[3] est repris 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]
               (T[j+1], T[j]) ← (T[j], T[j+1])

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 permutation. 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]
                (T[j+1], T[j]) ← (T[j], T[j+1])
                tableau_trié ← faux
        si tableau_trié
            fin tri_à_bulles_optimisé

Complexité modifier

Pour le tri non optimisé, la complexité en temps est de Θ(n²), 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 permutations.

Le pire cas (n itérations) est atteint lorsque le plus petit élément est à la fin du tableau. La complexité est alors Θ(n²).
En moyenne, la complexité est aussi Θ(n²). En effet, le nombre de permutations 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 permutations. Lorsque l'ordre initial des éléments du tableau est aléatoire, il est en moyenne égal à n(n-1)/4 ^[4].
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

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 ) $\to$ ( 1 5 4 2 8 ). Les nombres 5 et 1 sont comparés, et comme 5 > 1, l'algorithme les permute.
1.2. ( 1 5 4 2 8 ) $\to$ ( 1 4 5 2 8 ). Permutation, car 5 > 4.
1.3. ( 1 4 5 2 8 ) $\to$ ( 1 4 2 5 8 ). Permutation, car 5 > 2.
1.4. ( 1 4 2 5 8 ) $\to$ ( 1 4 2 5 8 ). Pas de permutation, car 5 < 8.
À la fin de cette étape, un nombre est à sa place définitive, le plus grand : 8.
Étape 2.: 2.1. ( 1 4 2 5 8 ) $\to$ ( 1 4 2 5 8 ). Pas de permutation.
2.2. ( 1 4 2 5 8 ) $\to$ ( 1 2 4 5 8 ). Permutation.
2.3. ( 1 2 4 5 8 ) $\to$ ( 1 2 4 5 8 ). Pas de permutation.
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 ) $\to$ ( 1 2 4 5 8 ). Pas de permutation.
3.2. ( 1 2 4 5 8 ) $\to$ ( 1 2 4 5 8 ). Pas de permutation.
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 aucune permutation durant cette étape 3, le tri optimisé se termine.
Étape 4.: 4.1. ( 1 2 4 5 8 ) $\to$ ( 1 2 4 5 8 ). Pas de permutation.
Le tri est terminé, car on sait que les 4 plus grands nombres, et donc aussi le 5^e, sont à leur place définitive.

Variantes de l'algorithme modifier

Tri cocktail modifier

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^[5], 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 de permutations à effectuer est identique (voir ci-dessus). Ainsi, le temps d'exécution est toujours proportionnel à n² donc médiocre.

Tri jump-down modifier

Le code de ce tri^[3] 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 permute lorsqu'il trouve un nouveau plus grand.

tri_jump_down(Tableau T)
   pour i allant de taille de T - 1 à 1
       pour j allant de 0 à i - 1
           si T[i] < T[j]
               permuter(T[i], T[j])

Tri combsort modifier

Une variante du tri à bulles, nommée tri à peigne (combsort), fut développée en 1980 par Włodzimierz 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

Sur les autres projets Wikimedia :

Implémentations du tri à bulles, sur Wikibooks

Liens externes modifier

Notes et références modifier

↑ « Le tri par propagation ou tri bulle », sur Interstices.
↑ R. Zaks, La Programmation du 6502, SYBEX, 1980 (ISBN 2-902414-24-2), « IX.2 Structures de données : exemples », p. 335
↑ ^{a et b} (en) Owen Astrachan, « Bubble Sort: An Archaeological Algorithmic Analysis », sur Computer Science Department, Duke University.
↑ On définit X_ij = 0 si T(i) < T(j) et X_ij = 1 sinon. Si l'ordre des éléments est aléatoire, alors l'espérance E(X_ij) vaut 1/2 pour tous i, j (i ≠ j). 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.
↑ (en) Donald E. Knuth, The Art of Computer Programming, vol. 3 : Sorting and Searching, 1998, 2^e éd. [détail de l’édition], section 5.2.2.

Portail de l'informatique théorique

[1] « Le tri par propagation ou tri bulle », sur Interstices.

[Zaks-2] R. Zaks, La Programmation du 6502, SYBEX, 1980 (ISBN 2-902414-24-2), « IX.2 Structures de données : exemples », p. 335

[Astrachan-3] {a et b} (en) Owen Astrachan, « Bubble Sort: An Archaeological Algorithmic Analysis », sur Computer Science Department, Duke University.

[4] On définit X_ij = 0 si T(i) < T(j) et X_ij = 1 sinon. Si l'ordre des éléments est aléatoire, alors l'espérance E(X_ij) vaut 1/2 pour tous i, j (i ≠ j). 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.

[5] (en) Donald E. Knuth, The Art of Computer Programming, vol. 3 : Sorting and Searching, 1998, 2^e éd. [détail de l’édition], section 5.2.2.

[1]

[2]

[3]

[4]

[5]