- Tri à bulles
-
Exemple du tri à bulles utilisant une liste de nombres aléatoiresLe 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. Cependant, sa complexité est de l'ordre de n² en moyenne (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.
Sommaire
Algorithme de base
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.
Pseudo-code
Voici la description en pseudo-code du tri à bulle, pour trier un tableau T de n éléments numérotés de 0 à n-1 :
procédure tri_bulle(tableau T, entier n) répéter aucun_échange = vrai pour j de 0 à n - 2 si T[j] > T[j + 1], alors échanger T[j] et T[j + 1] aucun_échange = faux tant que aucun_échange = fauxComplexité
Pour un tableau de taille n, le nombre d'itérations de la boucle externe « répéter … tant que aucun_échange = faux » 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, 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
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 )
( 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 ) ( 1 4 5 2 8 ) Interversion car 5 > 4.
( 1 4 5 2 8 ) ( 1 4 2 5 8 ) Interversion car 5 > 2.
( 1 4 2 5 8 ) ( 1 4 2 5 8 ) Comme 5 < 8, les éléments ne sont pas échangés.
Deuxième étape:
( 1 4 2 5 8 ) ( 1 4 2 5 8 ) Même principe qu'à l'étape 1.
( 1 4 2 5 8 ) ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ( 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 ) ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ( 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
Optimisation en ignorant la partie déjà triée
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. Voici un pseudo-code de cette dernière variante :
maximum = longueur(tableau) tant que maximum est supérieur à 0 maximumTemporaire = 0 pour i de 0 à maximum - 1 si la valeur à la position i de tableau est supérieure à la valeur à la position i+1 de tableau: inverserLesValeursDesPositions(tableau, i+1, i) maximumTemporaire = i+1 maximum = maximumTemporaireTri cocktail
Un dérivé du tri à bulles est le shakersort ou tri cocktail (en). 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.
Combsort
Une variante du tri à bulles, nommée combsort (en), 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
Liens externes
- Implémentations du tri à bulles sur wikibooks.
- Vidéo illustrant le fonctionnement du tri à bulles
- Une autre vidéo.
Notes et références
- 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 (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.
- 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)
Wikimedia Foundation. 2010.
