Tri à bulles
Le tri à bulles (ou tri par bulles en français, ou encore bubble sort en anglais) est un algorithme de tri simple organisant une liste en comparant successivement des paires d'éléments adjacents et en les échangeant si nécessaire. Le processus répète ce balayage jusqu'à ce que la liste soit entièrement triée.
Principe de fonctionnement
L'algorithme de tri à bulles (ou Bubble Sort) est un algorithme simple et intuitif de tri de données. Il fonctionne en comparant des éléments adjacents dans une liste et en les échangeant si nécessaire pour les mettre dans l'ordre souhaité. Ce processus est répété jusqu'à ce que la liste entière soit triée. L'algorithme est appelé «à bulles» car les plus grands éléments remontent progressivement vers le haut de la liste, comme des bulles dans un liquide. Cette technique est efficace pour de petites quantités de données, mais devient rapidement inefficace pour des listes plus volumineuses en raison de son temps de calcul élevé.
Le principe fondamental du tri à bulles repose sur la comparaison de paires d'éléments adjacents. Si l'élément à gauche est plus grand que l'élément à droite, ils sont échangés. Cela garantit que, après chaque passage dans la liste, le plus grand élément "flotte" vers la fin de la liste, d'où le nom de l'algorithme. Après chaque itération, l'élément le plus grand est ainsi placé dans sa position finale. L'algorithme continue de passer en revue la liste, mais ignore les éléments déjà triés à chaque nouvelle passe.
Une caractéristique importante de l'algorithme de tri à bulles est sa simplicité, ce qui en fait un choix pédagogique populaire pour enseigner les bases du tri. Cependant, sa complexité temporelle est relativement élevée. En effet, dans le pire des cas, pour une liste de n éléments, l'algorithme effectue un nombre de comparaisons égal à n(n-1)/2, soit une complexité en O(n2). Cela en fait un algorithme inefficace pour les grandes listes, comparé à d'autres algorithmes comme le tri rapide (QuickSort) ou le tri par fusion (MergeSort).
Le tri à bulles peut être optimisé légèrement par un mécanisme permettant de détecter si la liste est déjà triée avant d'avoir fait tous les passages. Si, lors d'une itération, aucun échange n'a été effectué, cela signifie que la liste est déjà triée, et l'algorithme peut être arrêté prématurément. Cela permet de réduire les performances dans le meilleur des cas à O(n), lorsque la liste est déjà triée ou presque triée.
Enfin, bien que l'algorithme de tri à bulles ne soit pas utilisé dans des applications réelles pour de grandes quantités de données, il présente des avantages pour certaines situations. Par exemple, dans le cas de petites listes ou de données presque triées, il peut être relativement rapide et très simple à implémenter. De plus, sa simplicité le rend facilement compréhensible pour ceux qui apprennent l'algorithmique, et il sert de base à la compréhension d'autres algorithmes plus complexes.
Voici les points principales du principe de fonctionnement du tri à bulles :
- Comparaison et échange : L'algorithme parcourt la liste d'éléments en comparant chaque paire adjacente. Si un élément est plus grand que le suivant, ils sont échangés pour les remettre dans l'ordre.
- Répétition : Ce balayage est répété autant de fois que nécessaire, chaque passage amenant le plus grand élément restant non trié vers la fin de la liste. Cela ressemble à des « bulles » qui montent progressivement vers la fin de la liste.
- Optimisation éventuelle : L'algorithme peut être légèrement optimisé en ajoutant un indicateur qui arrête le processus dès qu'un passage complet n'a pas nécessité d'échange (ce qui signifie que la liste est déjà triée).
Complexité et limites
- Complexité temporelle : La complexité de l'algorithme de tri à bulles est O(n2) dans le pire et le cas moyen, ce qui le rend peu efficace pour les grandes listes.
- Utilisation : En raison de sa simplicité, il est principalement utilisé pour les démonstrations pédagogiques ou dans des cas très simples où les données sont presque triées.
Algorithme
L'idée derrière cette technique est très simple, parcourir le tableau et permuter deux éléments lorsque cela s'avère nécessaire. Voici son algorithme :
|
BOUCLE POUR I ← Nombre d'élément - 2 JUSQU'A 0 PAS -1 FAIRE BOUCLE POUR J ← 0 JUSQU'A I PAS 1 FAIRE SI Tableau [J + 1] < Tableau [J] ALORS Échanger Tableau [J + 1] avec Tableau [J] FIN SI FIN BOUCLE POUR FIN BOUCLE POUR |
Exemple en langage de programmation Turbo Pascal
Voici un exemple d'un tri à bulle d'un tableau de 8 éléments écrit en Turbo Pascal :
- Program BubbleTri;
-
- 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,
Exemple en langage de programmation C
Voici un exemple d'un tri à bulle d'un tableau de 8 éléments écrit en C :
- #include <stdio.h>
- #include <stdlib.h>
-
- #define MaxTableau 8
-
- int main()
- {
- int K,L,I,J;
- int Tableau[MaxTableau] = {15, 10, 23, 2, 8, 9, 14, 16};
- printf("Avant:");
- for(K = 0; K < MaxTableau; K++) printf("%i, ",Tableau[K]);
-
- for(I = MaxTableau - 2;I >= 0; I--) {
- for(J = 0; J <= I; J++) {
- if(Tableau[J + 1] < Tableau[J]) {
- int t = Tableau[J + 1];
- Tableau[J + 1] = Tableau[J];
- Tableau[J] = t;
- }
- }
- }
-
- printf("\nAprès:");
- for(L = 0; L < MaxTableau; L++) {
- printf(", %i",Tableau[L]);
- }
- printf("\n");
- return 0;
- }
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,
Exemple en langage de programmation C#
Voici un exemple d'un tri à bulle d'un tableau de 8 éléments écrit en C# :
- using System;
- using System.Collections.Generic;
- using System.Linq;
- using System.Text;
-
- namespace TriBubble
- {
- class Program
- {
- static void Main(string[] args)
- {
- const int MaxTableau = 8;
- int K,L,I,J;
- int[] Tableau = { 15, 10, 23, 2, 8, 9, 14, 16 };
- Console.Write("Avant:");
- for(K = 0; K < MaxTableau; K++) Console.Write(Tableau[K] + ", ");
-
- for(I = MaxTableau - 2;I >= 0; I--) {
- for(J = 0; J <= I; J++) {
- if(Tableau[J + 1] < Tableau[J]) {
- int t = Tableau[J + 1];
- Tableau[J + 1] = Tableau[J];
- Tableau[J] = t;
- }
- }
- }
- Console.WriteLine();
- Console.Write("Après:");
- for(L = 0; L < MaxTableau; L++) {
- Console.Write(", " + Tableau[L]);
- }
- Console.WriteLine();
- }
- }
- }
-
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,
Exemple en langage de programmation Delphi
Voici un exemple d'un tri à bulle d'un tableau de 8 éléments écrit en Delphi :
- 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,
Exemple en langage de programmation Free Pascal
Voici un exemple d'un tri à bulle d'un tableau de 8 éléments écrit en Free Pascal :
- Program BubbleTri;
-
- 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,
Exemple en langage de programmation JavaScript
Voici un exemple d'un tri à bulle d'un tableau de 8 éléments écrit en JavaScript :
- <html>
- <body>
- <script>
- var MaxTableau = 8;
- var K,L,I,J;
- var Tableau = new Array(15, 10, 23, 2, 8, 9, 14, 16);
- document.write("Avant:");
- for(K = 0; K < MaxTableau; K++) document.write(Tableau[K],", ");
-
- for(I = MaxTableau - 2;I >= 0; I--) {
- for(J = 0; J <= I; J++) {
- if(Tableau[J + 1] < Tableau[J]) {
- var t = Tableau[J + 1];
- Tableau[J + 1] = Tableau[J];
- Tableau[J] = t;
- }
- }
- }
-
- document.write("<br>Après:");
- for(L = 0; L < MaxTableau; L++) {
- document.write(Tableau[L],", ");
- }
- document.write("<br>");
- </script>
- </body>
- </html>
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,
Exemple en langage de programmation PHP
Voici un exemple d'un tri à bulle d'un tableau de 8 éléments écrit en PHP :
- <?php
- $Tableau = array(15, 10, 23, 2, 8, 9, 14, 16);
-
- echo "Avant:";
- for($K = 0; $K < count($Tableau); $K++) {
- echo $Tableau[$K].", ";
- }
-
- for($I = count($Tableau) - 2;$I >= 0; $I--) {
- for($J = 0; $J <= $I; $J++) {
- if($Tableau[$J + 1] < $Tableau[$J]) {
- $t = $Tableau[$J + 1];
- $Tableau[$J + 1] = $Tableau[$J];
- $Tableau[$J] = $t;
- }
- }
- }
-
- echo "<br />Après:";
- for($L = 0; $L < count($Tableau); $L++) {
- echo $Tableau[$L].", ";
- }
- echo "<br />";
- ?>
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,