Voir la source de Tri à bulles

{{Infobox Algorithme}}

[[Fichier:Bubblesort-edited.svg|vignette|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''' ou '''tri par propagation'''<ref>{{lien web|url=https://interstices.info/encart.jsp?id=c_6973&encart=2&size=700,600|titre=Le tri par propagation ou tri bulle|site=[[Interstices]]}}.</ref> est un [[algorithme de tri]]. Il consiste à comparer répétitivement les éléments consécutifs d'un [[tableau (structure de données)|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 [[bulle (physique)|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 consécutifs. Lorsque deux éléments consécutifs ne sont pas dans l'ordre, ils sont [[permutation (informatique)|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<ref name="Zaks">{{ouvrage|auteur=R. Zaks|titre=La Programmation du 6502|chap=IX.2 Structures de données : exemples|année=1980|éditeur= SYBEX|isbn=2-902414-24-2|passage=335}}</ref>.

Le [[pseudo-code]] suivant<ref name=Astrachan/> est repris de [[The Art of Computer Programming|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é ===

Pour le tri non optimisé, la [[complexité en temps]] est de [[Notation O|Θ]](''n''{{2}}), 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é en temps|complexité]] est alors [[Notation O|Θ]](''n''{{2}}).
* En moyenne, la complexité est aussi Θ(''n''{{2}}). 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 <ref>On définit ''X{{ind|ij}} = 0'' si T(''i'') < T(''j'') et ''X{{ind|ij}} = 1'' sinon. Si l'ordre des éléments est aléatoire, alors l'[[Espérance mathématique|espérance]] E(X{{ind|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.</ref>.
* 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 ) <math>\to</math> ( '''1''' '''5''' 4 2 8 ). Les nombres 5 et 1 sont comparés, et comme 5 > 1, l'algorithme les permute.<br>1.2. ( 1 '''5''' '''4''' 2 8 ) <math>\to</math> ( 1 '''4''' '''5''' 2 8 ). Permutation, car 5 > 4.<br>1.3. ( 1 4 '''5''' '''2''' 8 ) <math>\to</math> ( 1 4 '''2''' '''5''' 8 ). Permutation, car 5 > 2.<br>1.4. ( 1 4 2 '''5''' '''8''' ) <math>\to</math> ( 1 4 2 '''5''' '''8''' ). Pas de permutation, car 5 < 8.<br>À 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 ) <math>\to</math> ( '''1''' '''4''' 2 5 8 ). Pas de permutation.<br>2.2. ( 1 '''4''' '''2''' 5 8 ) <math>\to</math> ( 1 '''2''' '''4''' 5 8 ). Permutation.<br>2.3. ( 1 2 '''4''' '''5''' 8 ) <math>\to</math> ( 1 2 '''4''' '''5''' 8 ). Pas de permutation.<br>5 et 8 ne sont pas comparés puisqu'on sait que le 8 est déjà à sa place définitive.<br>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 ) <math>\to</math> ( '''1''' '''2''' 4 5 8 ). Pas de permutation.<br>3.2. ( 1 '''2''' '''4''' 5 8 ) <math>\to</math> ( 1 '''2''' '''4''' 5 8 ). Pas de permutation.<br>Les deux derniers nombres sont exclus des comparaisons, puisqu'on sait qu'ils sont déjà à leur place définitive.<br>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 ) <math>\to</math> ( '''1''' '''2''' 4 5 8 ). Pas de permutation.<br>Le tri est terminé, car on sait que les 4 plus grands nombres, et donc aussi le {{5e}}, sont à leur place définitive.

== Variantes de l'algorithme ==

=== Tri cocktail ===

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<ref>{{Knuth-TAOCPVol3}}, section 5.2.2.</ref>, 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''{{2}} donc médiocre.

=== Tri jump-down ===

Le code de ce tri<ref name=Astrachan>{{Lien web|lang=en|url=https://users.cs.duke.edu/~ola/bubble/bubble.html|titre=Bubble Sort: An Archaeological Algorithmic Analysis|auteur=Owen Astrachan|site=Computer Science Department, [[Duke University]]}}.</ref> 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 ===
Une variante du tri à bulles, nommée [[tri à peigne]] (''{{langue|en|combsort}}''), fut développée en 1980 par Włodzimierz Dobosiewicz et réapparut en avril 1991 dans ''{{langue|en|[[Byte (magazine)|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 ==
{{Autres projets|b=Implémentation d'algorithmes classiques/Algorithmes de tri/Tri à bulles|wikibooks titre=Implémentations du tri à bulles}}

=== Liens externes ===
*[http://www.codingame.com/direct-puzzle/bubble-sort Vidéo et exercice pour apprendre le tri à bulles]
*{{YouTube|gWkvvsJHbwY|Vidéo illustrant le fonctionnement du tri à bulles}}
* {{en}} [https://www.toptal.com/developers/sorting-algorithms Illustration dynamique du tri à bulles]

=== Notes et références ===
{{Références|taille=30}}

{{Palette|Algorithmes de tri}}
{{Portail|informatique théorique}}

[[Catégorie:Algorithme de tri|Bulles]]

[[no:Sorteringsalgoritme#Boblesortering]]