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

NomFonction
KCompteur correspondant au nombre de cases restant à trier
PermutNuméro de la case de la dernière permutation
JCompteur courant dans le tableau
ElementTableau (ou liste, pile...) à trier
tempValueValeur temporaire afin de pouvoir inverser les 2 variables



  3. Exemple d'exécution

Le tableau est initialisé à :
15342
Etape 1 Initialisationk = 4, Permut = 5, J va de 1 à 4
J=1Rien à faire
J=2
13542
Permut = 2
J=3
13452
Permut = 3
J=4
13425
Permut = 4
Etape 2 Initialisationk = 3, Permut = 4, J va de 1 à 3
J=1Rien à faire
J=2Rien à faire
J=3
13245
Permut = 3
Etape 3 Initialisationk = 2, Permut = 3, J va de 1 à 2
J=1Rien à faire
J=2
12345
Permut = 2
Etape 4 Initialisationk = 1, Permut = 2, J va de 1 à 1
J=1Rien à faire
Le tableau est trié :
12345

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

:= 4;
Permut := k;
repeat
  k := permut - 1;
  for j:=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


Valid XHTML 1.0 Transitional