HOBBES World.com

Algorithmes

Accueil

Menu Général

Bubble Sort / Tri à Bulles

1. Principe

Le principe est simple : c'est de la comparaison élément par élément en réduisant à chaque fois l'intervalle de tri.
C'est à dire qu'au début on parcourt tout le tableau, on déplace l'élément le plus grand vers la droite (ou le plus petit en fonction du type de tri), si il y a une inversion (le tableau n'est donc pas trié), sinon, on peut s'arrêter.

2. Algorithme

2. 1. Codage

        k <- Nombre d'élément du tableau

        Permut <- k

        REPETER

          k <- permut - 1

          POUR J ALLANT de 1 à k FAIRE

            SI [ Elément (J) > Elément (J+1) ] ALORS 

              tempValue <- Elément (J)

              Elément (J) <- Elément (J+1)

              Elément (J+1) <- tempValue

              permut <- J;

            FIN SI

          FIN POUR

        JUSQU'A [ Permut > k ];

2. 2. Variables

Nom	Fonction
K	Compteur correspondant au nombre de cases restant à trier
Permut	Numéro de la case de la dernière permutation
J	Compteur courant dans le tableau
Element	Tableau (ou liste, pile...) à trier
tempValue	Valeur temporaire afin de pouvoir inverser les 2 variables

3. Exemple d'exécution

Le tableau est initialisé à :

Etape 1

Initialisation

k = 4, Permut = 5, J va de 1 à 4

J=1

Rien à faire

J=2

Permut = 2

J=3

Permut = 3

J=4

Permut = 4

Etape 2

Initialisation

k = 3, Permut = 4, J va de 1 à 3

J=1

Rien à faire

J=2

Rien à faire

J=3

Permut = 3

Etape 3

Initialisation

k = 2, Permut = 3, J va de 1 à 2

J=1

Rien à faire

J=2

Permut = 2

Etape 4

Initialisation

k = 1, Permut = 2, J va de 1 à 1

J=1

Rien à faire

Le tableau est trié :

Il a suffit de 5 permutations pour le trier.

4. Exemples

4. 1. PHP

    $k = 4; 

    $permut = $k; 

    do { 

      $k = $permut - 1; 

      for ($j=1; $j<=$k; $j++) { 

        if ($topDest[$j] > $topDest[$j+1]) { 

          $tempValue = $topDest[$j]; 

          $topDest[$j] = $topDest[$j+1]; 

          $topDest[$j+1] = $tempValue; 

          $permut = $j; 

        } 

      }  

    } while $permut <= $k;

4. 2. ASP / Visual Basic

    k = 4 

    permut = k 

    do 

      k = permut - 1; 

       for j=1 to k 

         if (topDest[j] > topDest[j+1]) { 

           tempValue = topDest[j]; 

           topDest[j] = topDest[j+1]; 

           topDest[j+1] = tempValue; 

           permut = j;      

         }    

       next loop  

    until ( permut > k );

4. 3. Delphi / Pascal

    k := 4; 

    Permut := k; 

    repeat 

      k := permut - 1; 

      for j:=1 to k do 

        if (topDest[j] > topDest[j+1]) then 

        begin 

          tempValue := topDest[j]; 

          topDest[j] := topDest[j+1]; 

          topDest[j+1] := tempValue; 

          permut := j; 

        end; 

    until Permut > k;

4. 4. Java

    int k=4; 

    int permut=k; 

    String tempValue; 

    do { 

      k = permut-1; 

      for (int j=0; j<=k; j++) { 

        if (((String) logValid.elementAt(j)).compareTo(logValid.elementAt(j+1)) > 0) { 

           tempValue = (String) logValid.elementAt(j); 

           logValid.setElementAt(logValid.elementAt(j+1),j); 

           logValid.setElementAt(tempValue,j+1); 

           permut = j; 

         } 

       } 

    } while (permut <= k);

Page modifiée le : 02/05/2022
Site modifié le : 14/09/2020