Le Tri à bulles / Bubble Sort

Niveau:

Le tri à bulles / Bubble sort

Aujourd’hui, nous allons aborder le tri le plus facile, le plus « naturel » qui nous vienne à l’esprit, j’ai nommé le tri à bulles. Il est nommé ainsi à cause de sa particularité qui est de faire « remonter » une donnée jusqu’à sa place définitive, un peu comme une bulle qui remonterait à la surface. Ce tutoriel est de niveau débutant, ce qui signifie que tu peux le suivre, même sans connaître la programmation. Le plus important ici, c’est la logique algorithmique.

Le problème à résoudre

Imaginons une liste de personnes, toutes possèdent un âge différent, le but est de classer ces personnes de la plus jeune à la plus âgée. Bien entendu, si on leur demandait de s’organiser entre elles, elles arriveraient à résoudre le problème de façon plus ou moins naturelle, car il est très simple. Mais ici, nous allons essayer de déterminer quelle est la suite des étapes logiques nécessaires à la résolution de ce problème.

En effet, une machine ne sait pas appliquer de solution « naturelle », elle ne sait qu’exécuter des ordres, il faut donc être très précis avec elle, lui donner une espèce de « recette de cuisine », c’est ce que l’on appelle un algorithme. Afin de réfléchir plus facilement, voici une illustration des données qui composent notre problème, chacune des cases représente l’âge d’une des personnes:

Situation initiale – les données sont dans le désordre.
Situation finale recherchée – les données sont dans l’ordre.

Maintenant que le problème est bien arrêté, place à l’algorithme !

L’algorithme

Comme dit plus haut, l’algorithme du tri à bulles est relativement simple, il consiste tout simplement à faire remonter une donnée à la place qui est la sienne, un peu comme une bulle qui remonterait à la surface. Commençons par la première donnée en partant de la gauche, à savoir le nombre 50 et appliquons lui la logique suivante:

Tant que la valeur courante (ici 50) est supérieure à la valeur située à sa droite, on échange leurs positions au sein de la liste des valeurs. Et voici ce que l’on obtient:

Bon c’est pas mal, mais on se rend compte que l’on pourrait facilement optimiser tout cela, par exemple en échangeant les positions des valeurs 63 et 58. Du coup, je vous propose de mettre à jour la logique algorithmique:

  • Choisir le premier élément comme élément courant
  • Tant que l’élément courant est suivi d’un autre élément, appliquer les opérations suivantes:
    • Si l’élément courant est supérieur à l’élément suivant, échanger leurs positions
    • Sinon faire de l’élément suivant l’élément courant

Et voici ce que l’on obtient:

Ici, il est important de faire un point intermédiaire, qu’avons-nous réussi à faire ? Si l’on regarde attentivement les données, on peut constater que l’on a fait remonter le nombre 63 à la bonne place, en effet, il est le plus grand de tous nos nombres, il sera donc tout à droite. Si l’on pousse l’analyse un peu plus loin, on constate également que les nombres 50 et 58 sont à leur place définitive, mais croyez-le ou non, c’est uniquement dû au hasard, voici un autre exemple permettant de le constater:

On constate donc bien que seule la donnée la plus grande finit par remonter à la bonne place. Essayons une nouvelle fois mais en appliquant l’ensemble des étapes 2 fois.

On peut alors constater que l’on a fait remonter à la bonne place les données 63 et 58 soit la dernière et l’avant-dernière ( en partant de la gauche ) … Mais du coup, si à chaque fois que l’on applique notre petite routine, notre petite « boucle » ( c’est le nom algorithmique de la structure que l’on a utilité jusqu’ici ) … Qu’arriverait-il si nous l’appliquions un certain nombre de fois … ?

… Et oui ! Si à chaque fois que l’on applique notre boucle, une donnée finit par remonter à sa place définitive ( comme une bulle ), alors il nous suffit d’appliquer cette routine autant de fois qu’il y a d’éléments à classer. Enfin, en vérité nous pouvons même nous permettre de l’appliquer une fois de moins … Pourquoi ? Et bien tout simplement parce que si parmi une liste de 10 éléments, 9 sont bien rangés, alors le dernier est forcément à sa place par rapport aux autres, c’est logique. Je vous propose de mettre à jour la logique algorithmique une dernière fois:

  • Créer une valeur nommée « compteur » et lui attribuer la valeur 1
  • Créer une valeur nommée « max » et lui attribuer la valeur correspondant au nombre d’éléments à classer.
  • Tant que « compteur » est inférieure ou égale à « max », répéter les opérations suivantes:
    • Créer une valeur nommée « position » et lui assigner la valeur 1
    • Tant que « position » est inférieure ou égale à « max » – 1 répéter les opérations suivantes:
      • Si la valeur située à « position » est supérieure à la valeur située à « position + 1 » alors on intervertit les deux éléments
      • Augmenter la valeur de « position » de 1
    • Augmenter la valeur de « compteur » de 1

Et voici le résultat de l’application de cette logique avec un schéma:

Conclusion

Sur cette dernière animation, tu as pu voir à l’oeuvre le pire des cas possibles, la liste d’éléments est initialement dans l’ordre inverse de celui que l’on souhaite, l’algorithme utilisé n’est donc pas optimisable dans ce cas précis. Cependant, si tu pars du cas initial, tu pourras constater par toi-même que la liste des éléments est triée, et ce bien avant que l’on en arrive à la dernière opération. Ce qui revient à dire que l’algorithme peut être optimisé, je te laisse trouver des axes possibles d’améliorations par toi-même, pour t’aider, tu peux toujours consulter la page wikipédia consacrée à cet algorithme.

C’est ici que ce tutoriel se termine, j’espère qu’il t’as plu, si c’est le cas n’hésite pas à me laisser un commentaire, même chose pour les questions ou éventuelles erreurs et imprécisions que tu as pu repérer.

Tu peux trouver une implémentation du tri à bulles sur le dépôt Github suivant: https://github.com/thetinyspark/moocaccino-bubble-sort.

À bientôt devant un petit café ;).

8 commentaires pour “Le Tri à bulles / Bubble Sort

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *