Algorithmes de tri courants en PHP : Tri à bulles et Tri par insertion

Les algorithmes de tri sont fondamentaux en informatique. Nous allons explorer deux algorithmes couramment utilisés pour trier de petites quantités de données : le tri à bulles et le tri par insertion.

1. Tri à bulles (Bubble Sort)

Principe :

• Comparer séquentiellement les éléments adjacents. Si leur ordre est incorrect, les échanger.
• À chaque passage, l'élément le plus grand "remonte" à sa position finale.

Optimisation : Si un passage complet ne nécessite aucun échange, cela signifie que le tableau est déjà trié et l'algorithme peut s'arrêter prématurément.

Implémentation en PHP :

public static function triABulles() {
   $donnees = [4, 5, 6, 3, 2, 1];
   $taille = count($donnees);

   // La boucle externe contrôle le nombre d'éléments déjà placés
   for ($i = 0; $i < $taille; $i++) {
       $echangeEffectue = false; // Indicateur pour l'optimisation

       // La boucle interne parcourt les éléments non triés
       // -i car les 'i' derniers éléments sont déjà triés
       for ($j = 0; $j < $taille - $i - 1; $j++) {
           if ($donnees[$j] > $donnees[$j + 1]) {
               // Échange des éléments
               $temp = $donnees[$j];
               $donnees[$j] = $donnees[$j + 1];
               $donnees[$j + 1] = $temp;
               $echangeEffectue = true; // Un échange a eu lieu
           }
       }

       // Si aucun échange n'a été effectué lors de ce passage, le tableau est trié
       if (!$echangeEffectue) {
           break;
       }
   }
   return $donnees;
}
   

2. Tri par insertion (Insertion Sort)

Principe :

• Le tableau est divisé en deux parties : une partie triée et une partie non triée.
• Initialement, la partie triée ne contient que le premier élément.
• On prend le premier élément de la partie non triée et on le place à sa position correcte dans la partie triée, en décalant si nécessaire les éléments plus grands.
• Ce processus est répété jusqu'à ce que tous les éléments soient dans la partie triée.

Implémentation en PHP :

public static function triParInsertion() {
   $donnees = [4, 5, 6, 1, 3, 2];
   $taille = count($donnees);

   // On commence à partir du deuxième élément (indice 1)
   for ($i = 1; $i < $taille; $i++) {
       $valeurCourante = $donnees[$i]; // L'élément à insérer
       $j = $i - 1; // L'indice du dernier élément trié

       // Tant que nous sommes dans la partie triée et que l'élément précédent est plus grand
       while ($j >= 0 && $donnees[$j] > $valeurCourante) {
           // Décaler l'élément vers la droite pour faire de la place
           $donnees[$j + 1] = $donnees[$j];
           $j--;
       }
       // Insérer la valeur courante à sa position correcte
       $donnees[$j + 1] = $valeurCourante;
   }
   return $donnees;
}
   

3. Comparaison : Tri à bulles vs Tri par insertion

Les deux algorithmes ont une complexité temporelle de O(n²) dans le pire des cas. Ce sont des algorithmes de tri en place (complexité spatiale O(1)) et stables. Ils conviennent bien aux petites collections de données. Pour des ansembles de données plus volumineux, des algorithmes comme le tri rapide, le tri fusion ou le tri par tas sont préférables.

Cependant, le tri par insertion est souvent préféré au tri à bulles en pratique. L'implémentation du tri par insersion implique généralement moins d'opérations de déplacement de données que le tri à bulles, ce qui le rend potentiellement plus performant dans certains scénarios.