Section courante

A propos

Section administrative du site

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 :

Complexité et limites

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 :

  1. Program BubbleTri;
  2.  
  3. Const 
  4.  Tableau : Array[0..7] of Byte = (15, 10, 23, 2, 8, 9, 14, 16);
  5.  
  6. Var
  7.  K,L,I,J,T:Byte;
  8.  
  9. BEGIN
  10.  Write('Avant:');
  11.  For K := 0 to High(Tableau) do Begin
  12.   Write(Tableau[K],', ');
  13.  End;
  14.  For I := (High(Tableau) + 1) - 2 downto 0 do Begin
  15.   For J := 0 to I do Begin
  16.    If Tableau[J + 1] < Tableau[J]Then Begin
  17.     T := Tableau[J + 1];
  18.     Tableau[J + 1] := Tableau[J];
  19.     Tableau[J] := T;
  20.    End;
  21.   End;
  22.  End;
  23.  WriteLn;
  24.  Write('Après:');
  25.  For L := 0 to High(Tableau) do Begin
  26.   Write(Tableau[L],', ');
  27.  End;
  28.  WriteLn;
  29. 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 :

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. #define MaxTableau 8
  5.  
  6. int main()
  7. {
  8.     int K,L,I,J;
  9.     int Tableau[MaxTableau] = {15, 10, 23, 2, 8, 9, 14, 16};
  10.     printf("Avant:");
  11.     for(K = 0; K < MaxTableau; K++) printf("%i, ",Tableau[K]);
  12.  
  13.     for(I = MaxTableau - 2;I >= 0; I--) {
  14.         for(J = 0; J <= I; J++) {
  15.             if(Tableau[J + 1] < Tableau[J]) {
  16.                 int t = Tableau[J + 1];
  17.                 Tableau[J + 1] = Tableau[J];
  18.                 Tableau[J] = t;
  19.             }
  20.         }
  21.     }
  22.  
  23.     printf("\nAprès:");
  24.     for(L = 0; L < MaxTableau; L++) {
  25.         printf(", %i",Tableau[L]);
  26.     }
  27.     printf("\n");
  28.     return 0;
  29. }

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# :

  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5.  
  6. namespace TriBubble
  7. {
  8.     class Program
  9.     {
  10.         static void Main(string[] args)
  11.         {
  12.             const int MaxTableau = 8;
  13.             int K,L,I,J;
  14.             int[] Tableau = { 15, 10, 23, 2, 8, 9, 14, 16 };
  15.             Console.Write("Avant:");
  16.             for(K = 0; K < MaxTableau; K++) Console.Write(Tableau[K] + ", ");
  17.  
  18.             for(I = MaxTableau - 2;I >= 0; I--) {
  19.                 for(J = 0; J <= I; J++) {
  20.                     if(Tableau[J + 1] < Tableau[J]) {
  21.                         int t = Tableau[J + 1];
  22.                         Tableau[J + 1] = Tableau[J];
  23.                         Tableau[J] = t;
  24.                     }
  25.                 }
  26.             }
  27.             Console.WriteLine();
  28.             Console.Write("Après:");
  29.             for(L = 0; L < MaxTableau; L++) {
  30.                 Console.Write(", " + Tableau[L]);
  31.             }
  32.             Console.WriteLine(); 
  33.         }
  34.     }
  35. }
  36.  

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 :

  1. Program BubbleTri;
  2.  
  3. {$APPTYPE CONSOLE}
  4.  
  5. Uses SysUtils;
  6.      
  7. Const 
  8.  Tableau : Array[0..7] of Byte = (15, 10, 23, 2, 8, 9, 14, 16);
  9.      
  10. Var
  11.  K,L,I,J,T:Byte;
  12.      
  13. BEGIN
  14.  Write('Avant:');
  15.  For K := 0 to High(Tableau) do Begin
  16.   Write(Tableau[K],', ');
  17.  End;
  18.  For I := (High(Tableau) + 1) - 2 downto 0 do Begin
  19.   For J := 0 to I do Begin
  20.    If Tableau[J + 1] < Tableau[J]Then Begin
  21.     T := Tableau[J + 1];
  22.     Tableau[J + 1] := Tableau[J];
  23.     Tableau[J] := T;
  24.    End;
  25.   End;
  26.  End;
  27.  WriteLn;
  28.  Write('Après:');
  29.  For L := 0 to High(Tableau) do Begin
  30.   Write(Tableau[L],', ');
  31.  End;
  32.  WriteLn;
  33. 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 :

  1. Program BubbleTri;
  2.  
  3. Const
  4.  Tableau : Array[0..7] of Byte = (15, 10, 23, 2, 8, 9, 14, 16);
  5.  
  6. Var
  7.  K,L,I,J,T:Byte;
  8.  
  9. BEGIN
  10.  Write('Avant:');
  11.  For K := 0 to High(Tableau) do Begin
  12.   Write(Tableau[K],', ');
  13.  End;
  14.  For I := (High(Tableau) + 1) - 2 downto 0 do Begin
  15.   For J := 0 to I do Begin
  16.    If Tableau[J + 1] < Tableau[J]Then Begin
  17.     T := Tableau[J + 1];
  18.     Tableau[J + 1] := Tableau[J];
  19.     Tableau[J] := T;
  20.    End;
  21.   End;
  22.  End;
  23.  WriteLn;
  24.  Write('Après:');
  25.  For L := 0 to High(Tableau) do Begin
  26.   Write(Tableau[L],', ');
  27.  End;
  28.  WriteLn;
  29. 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 :

  1. <html>
  2. <body>
  3. <script>
  4.      var MaxTableau = 8;
  5.      var K,L,I,J;
  6.     var Tableau = new Array(15, 10, 23, 2, 8, 9, 14, 16);
  7.     document.write("Avant:");
  8.     for(K = 0; K < MaxTableau; K++) document.write(Tableau[K],", ");
  9.  
  10.     for(I = MaxTableau - 2;I >= 0; I--) {
  11.         for(J = 0; J <= I; J++) {
  12.             if(Tableau[J + 1] < Tableau[J]) {
  13.                 var t = Tableau[J + 1];
  14.                 Tableau[J + 1] = Tableau[J];
  15.                 Tableau[J] = t;
  16.             }
  17.         }
  18.     }
  19.  
  20.     document.write("<br>Après:");
  21.     for(L = 0; L < MaxTableau; L++) {
  22.         document.write(Tableau[L],", ");
  23.     }
  24.     document.write("<br>");
  25. </script>
  26. </body>
  27. </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 :

  1. <?php
  2. $Tableau = array(15, 10, 23, 2, 8, 9, 14, 16);
  3.  
  4. echo "Avant:";
  5. for($K = 0; $K < count($Tableau); $K++) {
  6.  echo  $Tableau[$K].", ";
  7. }
  8.  
  9. for($I = count($Tableau) - 2;$I >= 0; $I--) {
  10.  for($J = 0; $J <= $I; $J++) {
  11.   if($Tableau[$J + 1] < $Tableau[$J]) {
  12.    $t = $Tableau[$J + 1];
  13.    $Tableau[$J + 1] = $Tableau[$J];
  14.    $Tableau[$J] = $t;
  15.   }
  16.  }
  17. }
  18.  
  19. echo "<br />Après:";
  20. for($L = 0; $L < count($Tableau); $L++) {
  21.   echo $Tableau[$L].", ";
  22. }
  23. echo "<br />";
  24. ?>

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,


Dernière mise à jour : Dimanche, le 12 mars 2006