Le tri à bulles, mieux connu sous son appellation anglaise «Bubble Sort», est l'un des algorithmes de tri les plus célèbres dans le domaine de l'informatique. Bien qu'il soit rarement utilisé dans les applications modernes nécessitant des performances élevées, il demeure extrêmement populaire à des fins pédagogiques en raison de sa simplicité de compréhension et de son implantation relativement facile. Il constitue souvent l'un des premiers algorithmes de tri enseignés aux étudiants qui découvrent la programmation et les structures de données.
Le principe de fonctionnement du tri à bulles est particulièrement intuitif. L'algorithme parcourt à plusieurs reprises un tableau de données et compare chaque élément avec son voisin immédiat. Lorsque deux éléments ne sont pas dans le bon ordre, ils sont simplement échangés. À force de répétitions successives, les valeurs les plus grandes « remontent » progressivement vers la fin du tableau, à la manière de bulles qui montent à la surface d'un liquide, d'où l'origine de son nom. Ce mécanisme simple permet d'obtenir, après plusieurs passages, une liste entièrement ordonnée.
Même si cet algorithme n'est pas le plus rapide lorsque le nombre d'éléments devient important, il présente l'avantage de ne nécessiter qu'une faible quantité de mémoire supplémentaire. De plus, sa logique repose uniquement sur des comparaisons et des permutations, ce qui en fait un excellent exercice pour comprendre les notions fondamentales liées aux tableaux, aux boucles et aux conditions. C'est également un excellent point de départ avant l'étude d'algorithmes plus performants tels que le tri rapide (QuickSort), le tri par fusion (Merge Sort) ou le tri par tas (Heap Sort).
À l'aide du code source Delphi présenté ci-dessous, vous découvrirez comment mettre en oeuvre un tri à bulles sur un tableau de nombres. Le programme affiche tout d'abord le contenu du tableau avant le tri, effectue ensuite les différentes permutations nécessaires, puis présente le résultat final une fois les données classées en ordre croissant. Cette démonstration permet de visualiser concrètement le fonctionnement de cet algorithme classique et de mieux comprendre les mécanismes fondamentaux du tri de données :
- Program BubbleTri;
-
- {$APPTYPE CONSOLE}
-
- Uses SysUtils;
-
- Const
- Tableau : Array[0..7] of Byte = (15, 10, 23, 2, 8, 9, 14, 16);
-
- Var
- K,L,I,J,T:Byte;
-
- BEGIN
- Write('Avant:');
- For K := 0 to High(Tableau) do Begin
- Write(Tableau[K],', ');
- End;
- For I := (High(Tableau) + 1) - 2 downto 0 do Begin
- For J := 0 to I do Begin
- If Tableau[J + 1] < Tableau[J]Then Begin
- T := Tableau[J + 1];
- Tableau[J + 1] := Tableau[J];
- Tableau[J] := T;
- End;
- End;
- End;
- WriteLn;
- Write('Après:');
- For L := 0 to High(Tableau) do Begin
- Write(Tableau[L],', ');
- End;
- WriteLn;
- END.
on obtiendra le résultat suivant :
Avant:15, 10, 23, 2, 8, 9, 14, 16,Après:2, 8, 9, 10, 14, 15, 16, 23,