PHP et tri à bulles

Ajouter un commentaire

Les algorithmes de tri sont des moyens très classiques de manipulation d’un ensemble d’objets, qui permettent d’obtenir une suite ordonnée de ces objets. La méthode que nous allons présenter consiste à trier le tableau par ordre croissant, en utilisant le fait qu’à chaque étape, tous les éléments de la partie visitée du tableau constituent en fait une suite de paires que l’on peut ordonner. On ne contente pas de dégager le max à chaque balayage, mais on ordonne les éléments de chaque paire. Cela diminuera éventuellement le nombre de balayages à effectuer.

Le tri à bulles utilise deux boucles imbriquées.
Le tableau est parcouru en comparant les éléments adjacents de chaque paire, c’est à dire en ordonnant les paires d’éléments consécutifs : si l’élément de la deuxième case est plus petit que celui de la précédente, alors on échange ces deux valeurs car cette paire n’est pas bien ordonnée. Remarquons que toute paire a comme premier élément le second de la paire précédente.
On effectue de tels parcours sur des préfixes dans lesquels le dernier élément est chaque fois évité, car il a été bien placé dans le parcours précédent.
Après chaque parcours des préfixes, les valeurs les plus grandes du tableau seront remontées aux dernières cases, de façon que l’élément le plus grand soit systématiquement remonté à la dernière case.
Si aucune inversion n’est effectuée lors du balayage d’un préfixe, on s’arrête : le tableau est trié, aucune inversion ne se produire plus sur les préfixes suivants visités.

Voici le code de la fonction qu’il faut ajouté à la classe TableauReelTReel  de l’ancien article

// Tri par à bulles
  public function triBulle(){
   $indice = 0;
   $boolean = true;
   $nbIteration = count($this->tableauReel) - 1;
   while($boolean){
     $indice = 1;
     $boolean = false;
     while($indice <= $nbIteration) { 	
        if( $this->tableauReel[$indice] < $this->tableauReel[$indice-1]){
	   $this->echanger($indice, $indice-1);
	   $boolean = true;;
	}
      $indice++;
     }
   }
}
// Test Classe
$tableau = new TableauReelTReel();
$tableau->add(45);
$tableau->add(3.14);
$tableau->add(3.24);
$tableau->add(-1.14);
$tableau->add(4.14);
// Afficher tableau 
$tableau->afficher();
echo '
';
//$tableau->triMax();
$tableau->triBulle();
$tableau->afficher();

Aperçu de résultat du code :

tribulles