Tri à bulles - Définition
La liste des auteurs de cet article est disponible ici.
Variantes de l'algorithme
Optimisation en ignorant la partie déjà triée
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 = maximumTemporaire
Tri 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, 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.
