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 horizontalement
*/
function aff_tab ($tab, $header) {
$str = "<TABLE>";
$lig1 = "<TR><TH>Indice</TH>";
$lig2 = "<TR><TH>$header</TH>";
foreach ($tab as $cle => $val) {
$lig1 .= "<TD>$cle</TD>";
$lig2 .= "<TD>$val</TD>";
}
$lig1 .= "</TR>";
$lig2 .= "</TR>";
$str .= $lig1.$lig2."</TABLE>";
return $str;
}
$tab = init_tab(); // Initialisation du tableau
echo aff_tab($tab, "Initialisation"); // Affichage de ce tableau
echo aff_tab(bubble_sort($tab), "Tri Bulle"); // Affichage du tableau trié
CSS
Feuille de style pour l'affichage du tableau
@font-face {
font-family:'PT Sans Narrow';
src:url("fonts/PTN57F.ttf");
}
body {
background: url("images/pattern.png") repeat scroll left top #f9e830;
color: #000;
font-family: 'Open Sans', sans-serif;
font-size: 12px;
}
html, body {
margin: 0;
padding: 0;
}
h1 {
font-family: 'PT Sans Narrow', Arial, sans-serif;
text-transform: uppercase;
letter-spacing:1px;
color: #000;
font-size: 34px;
margin: 10px 0 0 20px;
text-shadow: 1px 1px 1px #fef7a9;
margin-top:10px;;
}
.container {
text-align: center;
}
table {
margin:20px auto;
border-spacing:20px;
border:none;
}
td {
background-color: #f9e830;
padding: 7px;
box-shadow: 0px 0px 1px #2ab7ec inset, 2px 3px 1px 0 #156785, 7px 10px 5px 0px #999;
border:none;
font-size:20px;
min-width:25px;
}
th {
min-width:100px;
}
Et voici le résultat !
Ressources
Pour les boutons de l’animation : CSS Buttons Pseudo Elements
Pour le background : Vertical Sliding Accordion