Tri à bulles
Le tri à bulles est l'algorithme de tri le plus simple à décrire : comparer deux voisins, les échanger s'ils sont dans le mauvais ordre, et recommencer. Il est lent sur les longues listes, mais chaque étape est facile à suivre, ce qui en fait le premier algorithme classique à regarder.
Le principe
Parcourez la liste de gauche à droite et regardez chaque paire de voisins. Si la valeur de gauche est plus grande que celle de droite, échangez-les. Une fois à la fin, la plus grande valeur a été portée jusqu'à la dernière place, comme une bulle qui remonte à la surface. Ce parcours s'appelle un passage. Répétez les passages jusqu'à ce que la liste soit triée.
Un exemple
Prenez 5, 1, 4, 2, 8. Le premier passage compare 5 et 1 et les échange, puis 5 et 4 (échange), 5 et 2 (échange) et 5 et 8 (pas d'échange) : 1, 4, 2, 5, 8. Le 8 est maintenant à sa place définitive. Le deuxième passage compare 1 et 4 (pas d'échange), 4 et 2 (échange) et 4 et 5 (pas d'échange) : 1, 2, 4, 5, 8. Le troisième passage ne fait aucun échange, donc la liste est triée : 9 comparaisons et 4 échanges.
Pourquoi chaque passage place une valeur de plus
Pendant un passage, la plus grande valeur vue jusque-là est toujours emportée : dès que le passage l'atteint, chaque comparaison la déplace d'une place vers la droite. Le premier passage met donc la plus grande valeur en dernier, le deuxième la deuxième plus grande juste avant, et ainsi de suite. Après le passage k, les k dernières places sont définitives, et le passage suivant peut s'arrêter une place plus tôt. C'est pourquoi les passages raccourcissent.
Les échanges égalent les inversions
Une inversion est une paire de valeurs dans le mauvais ordre : une valeur plus grande placée quelque part avant une plus petite. Échanger deux voisins mal ordonnés supprime exactement une inversion et n'en crée aucune. Le tri à bulles fait donc exactement autant d'échanges que la liste de départ compte d'inversions, quel que soit l'ordre des comparaisons. Une liste triée n'en a aucune ; une liste inversée de n valeurs en a n(n − 1)/2, le maximum possible.
L'arrêt anticipé et le coût
Si un passage entier ne fait aucun échange, tous les voisins sont dans l'ordre et la liste est triée. Ce test permet au tri à bulles de finir une liste triée en un seul passage de n − 1 comparaisons. Dans le pire cas, il faut toujours n − 1 passages et n(n − 1)/2 comparaisons, et en moyenne le nombre d'échanges est n(n − 1)/4. Les deux croissent comme n² : doubler la liste rend le tri environ quatre fois plus long.
Le tri à bulles est stable : des valeurs égales ne sont jamais échangées, elles gardent donc leur ordre. Il trie en place, sans mémoire supplémentaire. Le tri par insertion a les mêmes propriétés et demande en général moins d'étapes, et le tri fusion et le tri rapide prennent un temps proportionnel à n log n, bien moindre sur les longues listes.
Explorez-le
Ouvrez l'application et appuyez sur Lecture, ou sur Étape pour avancer d'une comparaison à la fois. Les deux valeurs comparées sont mises en évidence, un échange a sa propre couleur, et les valeurs déjà en place deviennent vertes. Essayez une liste inversée pour voir le pire cas, une liste presque triée pour voir l'arrêt anticipé finir le tri après quelques passages, ou saisissez les nombres de l'exemple ci-dessus.
Questions fréquemment posées
Quelle est la complexité en temps du tri à bulles ?
O(n²) dans le pire cas et en moyenne : jusqu'à n(n − 1)/2 comparaisons pour n valeurs. Avec l'arrêt anticipé, une liste déjà triée prend O(n), un seul passage. Il ne demande que O(1) de mémoire supplémentaire.
Le tri à bulles est-il stable ?
Oui. Il n'échange deux voisins que si celui de gauche est strictement plus grand : des valeurs égales ne se dépassent jamais et gardent leur ordre d'origine.
Quelle différence entre le tri à bulles et le tri par insertion ?
Les deux échangent des voisins et font autant d'échanges qu'il y a d'inversions. Le tri à bulles fait des passages complets sur la partie non triée ; le tri par insertion ne fait reculer chaque nouvelle valeur que du nécessaire, il fait donc en général moins de comparaisons, surtout sur les listes presque triées.
Quand le tri à bulles est-il un bon choix ?
Surtout pour l'enseignement, et pour les listes très courtes où la simplicité compte plus que la vitesse. Pour tout le reste, la fonction de tri intégrée à votre langage de programmation est bien plus rapide.
Prêt à l'essayer ?
Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.
Essayer le tri à bulles