Tri à bulles

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Exemple du tri à bulles utilisant une liste de nombres aléatoires.
Autre tri.

Le tri à bulles ou tri par propagation est un algorithme de tri qui consiste à faire remonter progressivement les plus grands éléments d'un tableau, comme les bulles d'air remontent à la surface d'un liquide.

Le tri à bulles est souvent enseigné en tant qu'exemple algorithmique, car son principe est simple. Cependant, sa complexité en moyenne est de l'ordre de n² (où n est la taille du tableau), ce qui le classe parmi les mauvais algorithmes de tri. Il n'est donc quasiment pas 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 couples d'éléments successifs. Lorsque deux éléments successifs ne sont pas dans l'ordre croissant, ils sont échangés. Après chaque parcours complet du tableau, l'algorithme recommence l'opération. Lorsqu’aucun échange n'a lieu pendant un parcours, cela signifie que le tableau est trié. On arrête alors l'algorithme.

procédure tri_bulle(tableau T)
    n = longueur(T)
    pour i de n - 1 à 1
        aucun_échange = vrai
        pour j de 1 à i
            si T[j] > T[j + 1], alors
                échanger T[j] et T[j + 1]
                aucun_échange = faux
            fin si
        fin pour 
        si aucun_échange : fin procédure
    fin pour
fin procédure

Complexité[modifier | modifier le code]

Pour un tableau de taille n, le nombre d'itérations de la boucle externe « répéter … tant que échange_effectué » 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 ) \to ( 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 ) \to ( 1 4 5 2 8 ) Interversion car 5 > 4.
( 1 4 5 2 8 ) \to ( 1 4 2 5 8 ) Interversion car 5 > 2.
( 1 4 2 5 8 ) \to ( 1 4 2 5 8 ) Comme 5 < 8, les éléments ne sont pas échangés.
Deuxième étape:
( 1 4 2 5 8 ) \to ( 1 4 2 5 8 ) Même principe qu'à l'étape 1.
( 1 4 2 5 8 ) \to ( 1 2 4 5 8 )
( 1 2 4 5 8 ) \to ( 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 ) \to ( 1 2 4 5 8 )
( 1 2 4 5 8 ) \to ( 1 2 4 5 8 )
Comme la liste est triée, aucune interversion n'a lieu à cette étape, ce qui provoque l'arrêt de l'algorithme.

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

Optimisation en ignorant la partie déjà triée[modifier | modifier le code]

Exemple de tri à bulles optimisé utilisant une liste d'entiers de 0 à 99 mélangés. Le point rouge représente l'indice du tableau à partir duquel l'algorithme considère que le tableau est trié.

Comme expliqué plus haut, les i derniers éléments du tableau sont bien placés après le i-ème parcours de l'algorithme. On peut donc limiter la boucle du parcours à l'intervalle [0,n-i-1] au lieu de [0,n-2].

On peut également arrêter le parcours là où la dernière interversion a eu lieu au parcours précédent, ce qui est plus efficace lorsque la fin du tableau est déjà triée.

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 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)