Tri à bulles

Un article de DeathAngel.

[modifier] Principe

Le principe est de comparer deux éléments successifs dans un tableau et de les réordonner si la condition de tri n'est pas respectée. Une fois ce tri de deux éléments effectué, on passe aux deux éléments suivants dans le tableau et ainsi de suite jusqu'à parcourir entièrement le tableau.

A la fin de ce premier parcours, l'élément le plus grand se retrouve à l'extrémité du tableau. Il suffit ensuite de recommencer le même principe sur tout le tableau.

La complexité de cet algorithme est O(n²)

Le principal intérêt de cet algorithme est qu'il peut être écrit très rapidement dans n'importe quel langage, une dizaine de lignes suffisent en général et est suffisant si l'on a besoin de trier un petit nombre d'éléments sans utiliser trop de mémoire (pas de création de tableau temporaire). Par contre celui-ci peut très rapidement devenir extrêmement lent dans le cas de tableaux de tailles plus importante.

[modifier] Exemple

Soit le tableau v suivant [ 8 ; 3 ; 6 ; 2 ]

• On commence la première itération sur tout le tableau
• On compare 8 et 3, comme 8 est supérieur à 3, on échange nos deux éléments de place, on a v = [ 3 ; 8 ; 6 ; 2 ]
• On passe à la case suivante, on compare 8 et 6. Comme 8 est supérieur à 6, on échange les deux éléments. v = [ 3 ; 6 ; 8 ; 2]
• Case suivante, comparaison de 8 et 2. 8 est supérieur à 2, on échange, v = [ 3 ; 6 ; 2 ; 8 ]
• Nous sommes arrivés au bout du tableau, la plus grande valeur se trouve à l'extrémité. v = [ 3 ; 6 ; 2 ; 8 ]
• On recommence l'algorithme tant que le tableau n'est pas trié
• On compare 3 et 6, 3 est bien inférieur à 6, on ne change rien. v = [ 3 ; 6 ; 2 ; 8 ]
• Case suivante, comparaison de 6 et 2. 6 est supérieur à 2, on échange v = [ 3 ; 2 ; 6 ; 8 ]
• Le deuxième élément le plus grand est à sa place.
• 3ème itération, on compare 3 et 2. 3 est supérieur à 2, on inverse, v = [ 2 ; 3 ; 6 ; 8 ]

Notre tableau est trié.

[modifier] Algorithme

• Soit v un tableau d'éléments non trié
• Soit n le nombre d'éléments de ce tableau

i de type Entier
trie de type Booléen

    trie <- false
    Tant que trie == false Faire
    {
         trie <- true
         Pour i de 0 à n-2 Faire
         {
              // comparer les deux éléments successifs du tableau
              Si v[i]>v[i+1]
              {
                     // échanger les deux éléments
                     tmp <- v[i]
                     v[i] <- v[i+1]
                     v[i+1] <- tmp
                     // on n'est plus sur que le tableau soit trie
                     trie <- false
              }
         }
    }

[modifier] Optimisation possible

Une optimisation (mineure) est possible. En conservant le nombre d'éléments déjà triés à la fin du tableau, on peut limiter le nombre d'itération pour i. Au lieu de tester i de 0 à n-2, on teste i de 0 à n-2-nbTrie.

[modifier] Divers

Afin de se rendre compte de la non performance de cet algorithme, une petite vidéo est disponible sur Youtube à l'adresse suivante : Bubble Sort vs Quick Sort

Retour à la page principale