Tri à bulles

Le tri à bulles ou tri par propagation est un algorithme de tri qui consiste à faire remonter progressivement les plus petits éléments d'une liste, comme les bulles d'air remontent à la surface d'un liquide. L'algorithme parcourt la liste, 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 de la liste, l'algorithme recommence l'opération. Lorsqu'aucun échange n'a lieu pendant un parcours, cela signifie que la liste est triée : l'algorithme peut s'arrêter.

Cet algorithme est souvent enseigné en tant qu'exemple algorithmique. Cependant, il présente une complexité en ?(n²;) dans le pire des cas (où n est la longueur de la liste), ce qui le classe parmi les mauvais algorithmes de tri. Il n'est donc quasiment pas utilisé en pratique.

Complexité

Pour un tableau de taille n, la boucle for sera exécutée n-1 fois et while sera exécutée une fois si permut == faux, c'est-à-dire le tableau est trié n-1 fois si permut est vrai.

• Meilleur cas : O(n) le tableau est trié : n * 1 = o(n)
• Pire cas: o(n²;) le tableau est trié en ordre inverse (n -1)*(n-1) = o(n²;)

Le nombre d'échanges de paires d'éléments successifs est égal au nombre de couples (i,j) tels que i < j et A(i) > A(j). Ce nombre d'échanges est indépendant de la manière d'organiser les échanges. Pour un tableau aléatoire, il est en moyenne égal à .

Un dérivé du tri à bulles est le shakersort ou tri cocktail. Cette méthode de tri est basée sur une simple observation du comportement du tri à bulles : quand on fait un passage pour trier le maximum du tableau, on a tendance à déplacer les éléments les plus petits du tableau vers le début de celui-ci. Donc l'astuce consiste à alterner les sens de passage de notre bulle. Bien que le nombre d'échanges à effectuer soit identique (voir ci-dessus), on obtient un tri un peu plus rapide que la bulle. En effet, lors des changements de sens, cet algorithme relit les données les plus récentes et qui sont donc encore dans le tampon (cache) de la mémoire. Mais le temps d'exécution est toujours proportionnel à N2 donc médiocre.

Notons qu'une variante du tri à bulles, nommée combsort, fut développée en 1980 par Wlodek Dobosiewicz et réapparut en avril 1991 dans Byte Magazine. Elle permet de corriger le défaut majeur du tri à bulles qui sont les tortues et qui rend l'algorithme aussi rapide qu'un Quicksort.

Télécharger le projet "Tri_Bulle"