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.
De manière générale, on considère un ensemble d’éléments de la même classe sur lesquels est défini un ordre total, tous ces éléments sont comparables, pour une certaine relation d’ordre que l’on note <. Si ces objets sont des nombres, la comparaison numérique est évidente. Si ces objets sont, par exemple, des étudiants, le nom peut être considéré comme une chaîne de caractères sur laquelle on peut appliquer l’ordre lexicographique (celui du dictionnaire). On cherche à ordonner ces éléments c’est à dire à en réaliser une permutation, de manière que l’ensemble obtenu soit ordonné de façon croissante ou décroissante, pour la relation d’ordre que l’on s’est fixé. La manière retenue pour ordonner les éléments constituera un certain algorithme de tri.
Il existe de très nombreux algorithmes de tri, car le problème n’est en fait pas si simple. Il s’agit en effet d’obtenir une suite, par exemple croissante, des éléments que l’on souhaite trier, dans un temps raisonnable, voire dans un temps très court.
Dans cet article, nous allons considérer un tableau de réels. et on va les trier en les permutant de manière à obtenir, dans le même tableau, les éléments en ordre croissant.
Pour cela nous définissons une classe qui comporte une méthode d’affichage du tableau, méthode pour échanger deux éléments et les méthodes de tri.
La première méthode que nous allons définir consiste à trier le tableau par ordre croissant en utilisant la notion d’élément maximum que l’on doit mettre à sa place (trie par le max).
Voici le code
<?php class TableauReelTReel { private $tableauReel = array(); private $tailleTableau = 0; public function __construct(){} // Afficher les éléments du tableau public function afficher(){ $indice = 0; $nbIteration = 0; $nbIteration = count($this->tableauReel); while($indice < $nbIteration) { echo $this->tableauReel[$indice]; $indice++; echo '
'; } } // Ajouter des items au tableau public function add($item) { array_push($this->tableauReel, $item); } // Echanger les éléments du yableau public function echanger($pos1, $pos2) { $this->tailleTableau = count($this->tableauReel); $reelTmp = 0; if( ($pos1 > ($this->tailleTableau-1 ) ) || $pos2 > ($this->tailleTableau-1 ) ) { echo 'Impossible'; } else { $reelTmp = $this->tableauReel[$pos1]; $this->tableauReel[$pos1] = $this->tableauReel[$pos2]; $this->tableauReel[$pos2] = $reelTmp; } } // Tri par le max public function triMax(){ $indice = $posMax = 0; $max = $element1 = 0; $nbIteration = count($this->tableauReel) - 1; while($nbIteration >= 1) { $max = $this->tableauReel[0]; $posMax = 0; $indice = 1; while($indice <= $nbIteration) { $element1 = $this->tableauReel[$indice]; if($element1 > $max) { $max = $this->tableauReel[$indice]; $posMax = $indice; } $indice++; } echo 'Position du max ='.$posMax.' et nombre d\'iteration ='.$nbIteration. '
'; $this->echanger($posMax, $nbIteration); $this->afficher(); $nbIteration--; } } } // --------------------------------------------------------- $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(); ?>
Dans cet exemple, on dispose un tableau non vide de réels, le tableau est de dimension 5.
On parcourt le tableau (pour l’indice variant de 0 à 4) pour rechercher l’indice de l’élément le plus grand (que l’on placera dans une variable appelée max).
On échange la place de cet élément (le max) avec le dernier élément du tableau (la place normale du max). L’élément maximum sera à sa place et l’élément échangé qui occupait cette place sera réexaminé.
Le max étant placé, on recommence le balayage pour tous les éléments du tableau avant lui, c’est à dire le éléments dont les indices varient de 0 à 3 : on appellera un préfixe ce sous-tableau contenant les premiers éléments dont les indices vont de 0 à l’indice avant le max. Et ainsi de suite sur des préfixes de plus en plus petit, c’est à dire avec des indices allant de 0 à 2, puis de 0 à 1, jusqu’à ce qu’il n’y ait plus d’élément dont la place soit à échanger avec celle d’un autre élément.
Aperçu de résultat du code :