Le tri à bulles
Tu connais le tri par sélection. Voici un autre algorithme de tri, tout aussi célèbre : le tri à bulles. Son nom vient des grandes valeurs qui « remontent » peu à peu vers la fin du tableau, comme des bulles dans un verre.
L'idée
On parcourt le tableau en comparant chaque élément avec son voisin de droite. S'ils sont dans le mauvais ordre, on les échange. Et on recommence, jusqu'à faire un passage complet sans aucun échange.
Avec [5, 3, 8, 1] :
- on compare 5 et 3 : mauvais ordre, on échange →
[3, 5, 8, 1] ; - on compare 5 et 8 : bon ordre, on ne touche à rien ;
- on compare 8 et 1 : mauvais ordre, on échange →
[3, 5, 1, 8].
Après ce premier passage, la plus grande valeur (8) est arrivée tout au bout : elle est à sa place définitive.
Question : Après un passage complet du tri à bulles, quelle valeur est forcément bien placée ? — La plus grande, à la fin. La plus grande valeur gagne toutes ses comparaisons et « remonte » jusqu'à la dernière case.
Un passage
valeurs est un tableau vaut [5, 3, 8, 1]
tampon est un nombre
pour i de 0 à longueur(valeurs) - 2
si valeurs[i] > valeurs[i + 1] alors
tampon vaut valeurs[i]
valeurs[i] vaut valeurs[i + 1]
valeurs[i + 1] vaut tampon
fin si
fin pour
affiche joindre(valeurs, ', ') // 3, 5, 1, 8
La boucle s'arrête à l'avant-dernière case (longueur - 2) : la dernière n'a pas de voisin de droite.
Le tri complet
On répète les passages tant qu'il y a eu au moins un échange. Un drapeau s'en souvient :
procédure triBulles(liste)
dernierIndex est un nombre vaut longueur(liste) - 2
tampon est un nombre
echange est un booléen vaut vrai
tant que echange
echange vaut faux
pour i de 0 à dernierIndex
si liste[i] > liste[i + 1] alors
tampon vaut liste[i]
liste[i] vaut liste[i + 1]
liste[i + 1] vaut tampon
echange vaut vrai
fin si
fin pour
dernierIndex soustrait 1
affiche joindre(liste, ', ')
fin tant que
fin procédure
valeurs est un tableau vaut [5, 3, 8, 1]
appelle triBulles(valeurs)
Le programme affiche le tableau après chaque passage :
3, 5, 1, 83, 1, 5, 81, 3, 5, 81, 3, 5, 8 : aucun échange, le tri est terminé.
Deux détails malins :
- le drapeau
echange repasse à faux au début de chaque passage ; s'il est encore à faux à la fin, tout est en ordre ; dernierIndex soustrait 1 : à chaque passage, une valeur de plus est à sa place au bout, inutile de la comparer à nouveau.
Bulles ou sélection ?
Les deux tris font un nombre de comparaisons du même ordre : pour 1 000 éléments, environ 500 000. Mais le tri à bulles a un avantage : sur un tableau déjà trié, il s'arrête après un seul passage, puisqu'il ne fait aucun échange.
procédure triBulles(liste)
dernierIndex est un nombre vaut longueur(liste) - 2
tampon est un nombre
passages est un nombre vaut 0
echange est un booléen vaut vrai
tant que echange
echange vaut faux
passages ajoute 1
pour i de 0 à dernierIndex
si liste[i] > liste[i + 1] alors
tampon vaut liste[i]
liste[i] vaut liste[i + 1]
liste[i + 1] vaut tampon
echange vaut vrai
fin si
fin pour
dernierIndex soustrait 1
fin tant que
affiche 'Trié en ' + passages + ' passages'
fin procédure
dejaTrie est un tableau vaut [1, 2, 3, 4, 5, 6]
appelle triBulles(dejaTrie)
aEnvers est un tableau vaut [6, 5, 4, 3, 2, 1]
appelle triBulles(aEnvers)
Le tableau déjà trié demande 1 passage ; le tableau à l'envers en demande 6. Un même algorithme peut être rapide ou lent selon les données qu'on lui donne.
Lance le tri en pas à pas (F7) et observe le tableau dans la carte des variables : tu verras les grandes valeurs glisser vers la droite.
En résumé
- Tri à bulles : comparer chaque élément à son voisin et les échanger s'ils sont mal rangés.
- Après chaque passage, la plus grande valeur restante est à sa place.
- Un drapeau arrête le tri dès qu'un passage ne fait aucun échange.
- La rapidité d'un algorithme dépend aussi des données : meilleur cas, pire cas.
