Algorithme et développement PHP du tri bulle

Sommaire

Algorithme du tri bulle

Ce tutoriel vidéo explique à l’aide d’une animation l’algorithme du tri bulle. Puis nous verrons comment retranscrire cet algorithme en code PHP.

Le principe du tri bulle est de comparer deux valeurs adjacentes (l’une à côté de l’autre) d’un tableau. Si ce test de comparaison (un nombre est-il plus grand que son suivant pour appliquer un ordre croissant) est vrai alors nous permutons ces valeurs dans notre tableau. Autrement dit, l’un prend la place de l’autre. Ce raisonnement doit s’appliquer sur toutes les valeurs du tableau et être réitéré plusieurs fois.

L’animation que j’ai faite explique le mécanisme et met en lumière ce que nous devons faire pour sa retranscription en langage de programmation PHP.

Développement PHP

Les points principaux de cette programmation en PHP est l’imbrication de deux boucles for et la permutation de deux éléments d’un tableau.

L’imbrication de ces deux boucles interagissent entre elles puisque la première définit pour la seconde sa limite de progression.

Enfin, la permutation ne peut s’opérer directement sans écraser une valeur. Un stockage intermédiaire dans une troisième variable est donc nécessaire.

 

Sources

PHP

Tri bulle (bubble sort) en PHP
/*
* Tri bulle (Bubble sort)
* initialiser N nombres aléatoirement dans un tableau
* Appliquer le tri successif pour chaque nombre
* afficher le tableau initial puis le tableau trié
*/
define("LIMIT", 20);

/*
* Initialisation du tableau avec des valeurs tirées aléatoirement
*/
function init_tab() {
$tab = array();
for($i=0; $i<LIMIT; $i++) {
$tab[$i] = rand(0, 100);
}
return $tab;
}

/*
* Tri bulle
*/
function bubble_sort($tab) {
for($i=0; $i<LIMIT-1; $i++) {
for($j=0; $j<(LIMIT-1-$i); $j++) {
if ($tab[$j] > $tab[$j+1] ) {
$temp = $tab[$j+1];
$tab[$j+1] = $tab[$j];
$tab[$j] = $temp;
}
}
}
return $tab;
}

/*
* Affichage d'un tableau h