Dans cette vidéo en français, le présentateur explique comment trier un tableau d'entiers plein en ordre croissant en utilisant l'algorithme de tri à bulles. Il commence par présenter le problème et l'exemple de tableau [30, 12, 20, 9, 15], puis décrit le principe du bubble sort : à chaque passage, l'élément le plus grand « remonte » à droite grâce à des comparaisons et échanges d'éléments adjacents. Il détaille l'implémentation avec deux boucles imbriquées (une boucle « grande » contrôlée par i, une petite boucle j) et l'utilisation d'une variable temporaire tmp pour permuter les valeurs. Le présentateur montre comment initialiser le tableau, choisir les bornes des boucles (i de n‑1 à 1, j de 1 à i) et comment le commentaire de code peut être écrit avec différents symboles selon le langage. Il mentionne brièvement les possibilités d'optimisation tout en rappelant que le tri à bulles reste lent et rarement utilisé en pratique. La vidéo se conclut par un remerciement et une invitation à la prochaine vidéo.
Chapters
Bonjour à tous et bienvenue dans cette nouvelle vidéo où l'on va traiter l'exercice suivant: On dispose d'un tableau d'entiers qui est déjà plein. Les valeurs y sont stockées en désordre. On souhaite procéder au tri de ce tableau-là dans l'ordre croissant en appliquant la méthode de tri à bulles. D'après l'énoncé, le tableau en question contient une liste de valeurs entières qui y sont déposées aléatoirement. Notre mission consiste à créer un algorithme qui permet de trier les éléments de ce tableau-là du plus petit au plus grand. Pour y parvenir, on va s'appuyer sur la méthode de tri à bulles. Le tri à bulles est l'une des méthodes classiques de réorganisation d'une suite d'éléments. Elle n'est pas la plus performante de sa catégorie de tri par échange, mais son principe reste parmi les plus simples à mettre en œuvre. Considérons que l'on dispose d'un tableau qui contient les valeurs suivantes: 30, 12, 20, 9 et 15. Le principe consiste à parcourir le tableau élément par élément en comparant l'élément courant avec l'élément suivant. Si ces 2 éléments-là ne sont pas dans l'ordre, alors ils seront permutés. Ainsi, à la fin du premier parcours on aura placé l'élément le plus grand à droite du tableau. Dans ce cas, cet élément-là vaut 30. On recommence l'opération en parcourant le tableau une deuxième fois, mais cette fois-ci on exclut le dernier élément, c'est-à-dire à-dire celui qui est le plus à droite, car il est déjà traité puisqu'il est l'élément le plus grand. À la fin du deuxième parcours, on aura placé l'élément suivant juste avant l'élément le plus à droite. On procède de la même manière jusqu'à ce qu'il ne reste plus aucune comparaison à faire, ce qui signifie que le tableau est trié. Désormais, l'élément le plus petit est placé à gauche et l'élément le plus grand est positionné à droite. Donc, le principe du tri à bulles repose sur le fait que l'on pousse l'élément le plus grand le plus rapidement possible jusqu'à ce qu'il atteigne sa position finale, puis on cherche l'élément suivant que l'on traite de la même manière, etc. En analysant cette méthode de tri, on se rend compte que l'on va se servir de 2 structures itératives imbriquées. On va opter pour la structure Pour vu que le nombre d'itérations à exécuter est connu à l'avance. En effet, le nombre d'itérations de la grande boucle dépend du nombre d'éléments dans le tableau, et le nombre d'itérations de la petite boucle dépend de la valeur courante du compteur de la grande boucle. Dans notre algorithme on aura besoin des variables suivantes: tab qui est un tableau d'entiers, i qui représente le compteur de la grande boucle qui va spécifier l'intervalle à parcourir, j qui est le compteur de la petite boucle qui parcourt les éléments dans l'intervalle spécifié par la grande boucle, tmp qui est un entier et qui sert de variable intermédiaire pour effectuer la permutation. Je propose l'algorithme suivant: Dans cet algorithme aussi, on a considéré que le tableau tab est dynamique, donc nous n'avons pas spécifié sa taille au moment de la déclaration. Dans le corps de l'algorithme, la première opération consiste à initialiser le tableau en mettant des valeurs dedans. J'ai spécifié cette opération à l'aide d'un commentaire que j'ai commencé par double slash. En effet, un commentaire est un texte qui n'est pas forcément du code que l'on peut mettre n'importe où dans le code source. Il sera visible par le programmeur mais ignoré au moment de l'exécution du programme. Notez que j'ai opté pour double slash car il s'agit du symbole le plus utilisé pour désigner les commentaires dans de nombreux langages de programmation. Cependant, on peut remplacer double slash par dièse comme c'est le cas pour Python, ou placer carrément le commentaire entre deux accolades ouvrantes et fermantes comme c'est le cas en Pascal, ou encore entre slash étoile et étoile slash qui est principalement utilisé en langage C. Juste après l'initialisation du tableau identifié par tab dont la première entrée est indexée par 1, on procède au traitement itératif à l'aide de la grande boucle qui utilise le compteur i. La valeur initiale de celui-ci vaut la taille du tableau moins 1 et sa valeur finale vaut 1. Et comme pas d'incrémentation, on spécifie la valeur moins 1. Il s'agit en fait d'une décrémentation vu que la valeur initiale du compteur est supérieure à sa valeur finale. Cette boucle a pour rôle de spécifier l'intervalle de parcours des index du tableau. Ce parcours sera justement fait par la petite boucle dont le compteur est j. Cette boucle-là commence à 1 et finit à i, avec un pas d'incrémentation qui vaut par défaut 1. Donc l'intervalle de parcours rétrécit à chaque itération de la grande boucle. Dans la petite boucle on vérifie si la valeur de l'index courant du tableau est supérieure à la valeur de l'index suivant, ce qui signifie que ces 2 entrées consécutives sont en désordre. Si c'est le cas, alors il faut les remettre dans l'ordre en procédant à leur permutation en invoquant la variable intermédiaire tmp. À la fin de la boucle on aura trié le tableau dans l'ordre croissant en plaçant le plus petit élément à gauche et le plus grand à droite. Bien entendu, ce code reste basique et on peut l'optimiser davantage en appliquant des améliorations qui peuvent rendre son temps d'exécution minimal. Cependant, comme je l'ai mentionné au début de cette vidéo, la méthode de tri à bulles est par nature l'une des méthodes de tri les plus lentes et elle est rarement utilisée en pratique. On se contente de ça pour cette fois, merci pour votre attention et à la vidéo prochaine.
