- Comparées
- Échangées
- En place
Tri à bulles
Le tri à bulles parcourt une liste encore et encore, compare chaque paire de voisins et les échange quand celui de gauche est plus grand. Après chaque passage, la plus grande valeur encore mal placée est remontée jusqu'à la fin. Lancez le tri à la vitesse de votre choix, ou avancez d'une comparaison à la fois, et suivez les compteurs de comparaisons, d'échanges et de passages. Appuyez sur Lecture pour regarder le tri, ou sur Étape et Retour pour avancer d'une comparaison à la fois. Faites glisser le curseur d'étapes pour aller n'importe où. Les tuiles comptent les comparaisons, les échanges et les passages. Choisissez le nombre de barres, leur ordre de départ, ou saisissez vos propres nombres. Quand le tableau est sélectionné, les flèches avancent d'une étape, la barre d'espace lance et met en pause, et Origine et Fin vont au début et à la fin.
Comment ça marche
- Choisissez le nombre de barres et leur ordre de départ : aléatoire, presque trié, inversé ou avec peu de valeurs distinctes. Ou saisissez vos propres nombres.
- Appuyez sur Lecture, ou utilisez Étape et Retour pour avancer d'une comparaison à la fois. Faites glisser le curseur d'étapes pour aller n'importe où dans le tri.
- Suivez les tuiles qui comptent les comparaisons, les échanges et les passages, et comparez-les au pire cas.
Comment fonctionne le tri à bulles
Commencez à gauche. Comparez les deux premières valeurs ; si celle de gauche est plus grande, échangez-les. Avancez d'une place vers la droite et comparez à nouveau, jusqu'à la fin de la liste. C'est un passage, et il laisse la plus grande valeur à la dernière place. Le passage suivant s'arrête une place plus tôt. Continuez jusqu'à ce qu'un passage ne fasse aucun échange, ou qu'il ne reste qu'une valeur.
Compter le travail
Pour n valeurs, le premier passage fait n − 1 comparaisons, le suivant n − 2, et ainsi de suite : un tri complet fait donc au plus n(n − 1)/2 comparaisons. Le nombre d'échanges est toujours le nombre d'inversions de la liste de départ, c'est-à-dire de paires de valeurs dans le mauvais ordre. Une liste inversée en a le plus, n(n − 1)/2. Une liste triée n'en a aucune et, avec l'arrêt anticipé, elle ne demande qu'un passage de n − 1 comparaisons.
Questions fréquemment posées
Pourquoi l'appelle-t-on tri à bulles ?
Parce que les grandes valeurs remontent vers la fin de la liste comme des bulles dans l'eau. À chaque passage, la plus grande valeur pas encore en place avance pas à pas vers la droite jusqu'à sa place définitive.
Combien de comparaisons et d'échanges fait le tri à bulles ?
Au plus n(n − 1)/2 comparaisons pour n valeurs : 45 pour 10 valeurs, 780 pour 40. Le nombre d'échanges est toujours égal au nombre d'inversions de la liste de départ, de zéro pour une liste triée à n(n − 1)/2 pour une liste inversée.
À quoi sert l'arrêt anticipé ?
Si un passage entier ne fait aucun échange, toutes les paires de voisins sont dans l'ordre : la liste est triée et le tri peut s'arrêter. Avec l'arrêt anticipé, une liste triée ne demande qu'un passage. Sans lui, le tri à bulles fait toujours les n − 1 passages.
Le tri à bulles est-il utilisé en pratique ?
Rarement. Il est simple et stable, mais son temps est proportionnel à n² en moyenne. Le tri par insertion fait le même travail en moins d'étapes sur les listes courtes ou presque triées, et le tri fusion ou le tri rapide sont bien plus rapides sur les grandes listes.
Mes nombres sont-ils envoyés quelque part ?
Non. Le tri s'exécute dans votre navigateur, et vos derniers réglages restent dans le stockage local de ce navigateur.
Prêt à l'essayer ?
Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.
Aller à l'éditeur