Home > Algorithmes > Le tri bulle, ou tri par propagation

Le tri bulle, ou tri par propagation

October 29th, 2009
ReTwittez ce post Goto comments Leave a comment

(en anglais: bubble sort)

Le tri bulle est un très bon algo au point de vue didactique mais mauvais en termes mathématiques (complexité trop grande). Son but est de trier une liste de valeurs pour la renvoyer en ordre croissant. Pour cela, l’algo parcours les éléments de la liste deux par deux, et les classe en ordre croissant (il les permute si le 2e élément est le plus petit). Une fois la liste finie, le tri-bulle recommence. Lorsqu’un parcours a été fait entièrement sans avoir besoin de faire une permutation, le tri est fini.

Attention, le tri-bulle n’est que très rarement utilisé lorsqu’on a besoin d’opérations de tri, car il n’est pas très performant.
Cet article est le premier d’une série consacrée aux algorithmes connus et utiles, et est à prendre comme une “introduction” à l’algorithmique.

Le code du tri-bulle en PHP

  1. function bubblesort(&$liste) {
  2.     $nbItems = count($liste);
  3.     $permutation = true;
  4.     $nbPermutations = 0;
  5. // on continue tant qu’on a eu à faire des permutations…
  6.     while($permutation == true) {
  7.         $permutation = false;
  8.         for($i=0;$i<$nbItems-1;$i++) {
  9.             // si l’élément de gauche est le plus grand,
  10.             if ($liste[$i] > $liste[$i+1]) {
  11.                 // on échange la place des éléments
  12.                 $temp = $liste[$i+1];
  13.                 $liste[$i+1] = $liste[$i];
  14.                 $liste[$i] = $temp;
  15.                 $permutation = true;
  16.                 $nbPermutations++;
  17.             }
  18.         }
  19.         print_r($liste);
  20.     }
  21.     return array(‘nbpermutations’=>$nbPermutations);
  22. }
  23.  
  24. $liste = array(4,9,13,5,17,2,-6);
  25. $bubble = bubblesort($liste);
  26.  
  27. echo ‘Liste triée en ‘.$bubble[‘nbpermutations’].‘ permutations.’;

Remarques sur le code: j’ai volontairement passé la liste de valeurs par référence. Dans ce cas, la variable de départ est utilisée directement au lieu d’être copiée dans la fonction puis modifiée. On n’a donc pas besoin d’utiliser return pour récupérer la liste triée.

Ce post vous a été utile ? Re-Twittez le ! ReTwittez ce post

Algorithmes , , ,

  1. Renaud
    | #1
    Reply | Quote

    Pourquoi faire un return array(‘nbpermutations’=>$nbPermutations); ?

    Pourquoi pas directement return $nbPermutations; ?

  1. No trackbacks yet.