GEINAC
Contenu
Une implémentation en Caml light :
(*Fonction qui réalise la permutation circulaire*)
let decalage tab i j =
let temp = tab.(j) in
for k=j-1 downto i do
tab.(k+1) <- tab.(k)
done;
tab.(i) <- temp;;
(*Fonction qui trouve la place de l'élement i*)
let insertion tab i =
let j=ref(0) in
while (!j < i && tab.(!j) < tab.(i)) do
incr(j)
done;
decalage tab !j i;;
(*La fonction de tri*)
let tri_ins tab =
for i=0 to vect_length(tab)-1 do
insertion tab i done;
tab;;
tri_ins [|5;7;9;4;6;8;7;98;5;4;32;0;1;117|];;
Une implémentation en PHP :
function tab_decalage(&$tab, $i, $j) {
$tmp = $tab[$j];
for ($k = $j-1; $k >= $i; $k--) {
$tab[$k+1] = $tab[$k];
}
$tab[$i] = $tmp;
}
/* insert le i-eme élément du tableau dans la partie triée (de 0 à i-1) */
function tab_insertion(&$tab, $i) {
$j = 0;
while ($j < $i && $tab[$j] < $tab[$i]) {
$j++;
}
tab_decalage($tab, $j, $i);
}
function tri_insertion($tab) {
for ($i = 0; $i < count($tab); $i++) {
tab_insertion($tab, $i);
}
return $tab;
}
L’avantage de cet algorithme est qu’il n’est encore pas trop compliqué et qu’il est bien différent du tri précédent. En revanche sa complexité est la même, c'est-à-dire mauvaise. En effet pour placer le k-eme élément il faut en moyenne (k+1)/2 comparaisons. Pourquoi ? Car dans le tableau déjà trié des éléments 0 à k-1, le k-eme élément qu’on insère a la probabilité 1/k de se retrouver inséré en position i, ce qui coûte i comparaisons, i variant de 0 à k :
Ca c’est pour insérer le k-ième élément. Or k varie de 0 à n-1. D’où la complexité finale :
Tri Fusion
C’est le tri le plus intéressant en termes de performance parmi les 4 qu’on étudie. L’algorithme est également récursif. Il coupe le tableau en deux sous tableaux, les trie, puis fusionne ces 2 tableaux. En fait chaque sous tableau est passé de nouveau a l’algorithme, il est fractionné de nouveau ainsi de suite jusqu'à ce que sa taille soit unitaire. On voit donc que l’étape clé est la fusion de 2 tableaux. Pour fusionner on compare les 2 tableaux indice par indice et on place à chaque fois dans le nouveau tableau résultant le plus petit élément.
Exemple : n=4 Tab=8 ;4 ;7 ;1
- On coupe le tableau en 2, on obtient T1=8 ;4 et T2=7 ;1
- On trie T1 et T2 par tri fusion. On coupe T1 en T3 = 8 et T4=4 et on coupe T2 en T5=7 et T6=1. Tous les tableaux sont unitaires, on passe à la fusion. On fusionne T3 et T4 en T1’=4 ;8 et T5 et T6 enT2’=1 ;7.
- On fusionne alors T1’ et T2’ en T= 1 ;4 ;7 ;8. Voilà !
Complexité : Elle est nettement plus difficile a établir cependant mais on peut démontrer qu’elle est en 
.
Comme d'habitude je donne deux implémentations de l'algorithme, une en Caml et une en PHP. Par contre pour le version Caml j'utilise des listes pour structure de données, car elles se prêtent mieux aux tris récursifs. Comparez avec les tableaux pour la version PHP.
Version PHP tableaux
//Coupe le tableau au milieu en deux sous tableaux
function coupe($tab) {
$mid = count($tab)/2;
for ($i = 0; $i < $mid; $i++) {
$t1[] = $tab[$i];
}
for ($i = $mid; $i < count($tab); $i++) {
$t2[] = $tab[$i];
}
return array($t1, $t2);
}
//Fusionne deux tableaux t1 et t2
function fusion($t1, $t2) {
$i = 0; //Indice qui parcourt t1
$j = 0; //Indice qui parcourt t2
while ($i < count($t1) || $j < count($t2)) {
if ($i >= count($t1)) {
// Si on est arrivé à la fin de t1 on rajoute la fin de t2
$tab[] = $t2[$j];
$j++;
} else if ($j >= count($t2)) {
// Si on est à la fin de t2 on rajoute la fin de t1
$tab[] = $t1[$i];
$i++;
} else {
// Il reste des éléments dans les deux tableaux, on prend le plus petit
if ($t1[$i] < $t2[$j]) {
$tab[] = $t1[$i];
$i++;
} else {
$tab[] = $t2[$j];
$j++;
}
}
}
return $tab;
}
function tri_fusion($tab) {
if (count($tab) > 1) {
list($t1, $t2) = coupe($tab); //On coupe
$t1 = tri_fusion($t1); //On trie le 1er
$t2 = tri_fusion($t2); //On trie le 2eme
$tab = fusion($t1, $t2); //On fusionne
}
return $tab;
}
print_r(tri_fusion(array(1, 2, 5, 6, 8, 7, 9, 6, 3, 42, 13, 37)));
Et la version Caml sur des listes
let rec coupe = function
| [] -> ([],[])
| [t] -> ([t],[])
| t1::t2::q -> let (q1,q2) = coupe q in (t1::q1,t2::q2);;
let rec fusion = function
| ([],[]) -> []
| (l,[]) -> l
| ([],l) -> l
| (t1::q1,t2::q2) -> if t1<=t2 then t1::fusion(q1,t2::q2)
else t2::fusion(t1::q1,q2);;
let rec tri_fusion = function
| [] -> []
| [t] -> [t]
| l -> let (q1,q2) = coupe l in fusion(tri_fusion q1, tri_fusion q2);;
Tri Rapide
C’est l’algorithme le plus complexe à comprendre mais il est très efficace. Le principe consiste à choisir un élément du tableau T et de le considérer comme le pivot P du tableau T. C'est-à-dire qu’on compare ensuite les autres éléments au pivot et on les classe en deux sous tableaux T1 et T2 : T1 contient les éléments plus petits que le pivot P et T2 ceux plus grands. Le pivot sert donc de référence. Puis on appelle récursivement le tri rapide sur les deux sous tableaux. Une fois les deux tableaux T1 et T2 triés on concatène T1.P.T2. En effet par définition le pivot P est plus grand que tous les éléments du premier tableau et plus petit que tous les éléments du second tableau. L’étape clé est ici la coupe du tableau T en T1 et T2 selon P.
Je donne deux implémentations une en PHP sur des tableaux l’autre en Caml light sur des listes.
//Fonction qui coupe le sous tableau d'indice $deb à $fin
function partage(&$tab, $deb, $fin) {
$ipivot = $deb; //Indice du pivot
$pivot = $tab[$ipivot]; //Valeur du pivot
for ($i = $ipivot+1; $i <= $fin; $i++) {
if ($tab[$i] < $pivot) {
$tab[$ipivot] = $tab[$i];
$ipivot++;
$tab[$i] = $tab[$ipivot];
}
}
$tab[$ipivot] = $pivot;
return $ipivot;
}
function tri_rec(&$tab, $deb, $fin) {
if ($deb < $fin) {
$p = partage($tab, $deb, $fin); //On coupe
tri_rec($tab, $deb, $p-1); //On trie le 1er
tri_rec($tab, $p+1, $fin); //On trie le 2eme
}
}
function tri_rapide($tab) {
tri_rec($tab, 0, count($tab)-1);
return $tab;
}
print_r(tri_rapide(array(1, 2, 5, 6, 8, 7, 9, 6, 3, 42, 13, 37)));
let rec coupe pivot = function
| [] -> ([],[])
| t::q -> let (q1,q2)= coupe pivot q in
if t<=pivot then (t::q1,q2) else (q1,t::q2);;
let rec tri_rapide = function
| [] -> []
| t::q -> let (q1,q2) = coupe t q in (tri_rapide q1)@[t]@(tri_rapide q2);;
tri_rapide [5;6;4;9;8;9;4;6;55;4;5;56;66];;
La complexité est encore difficile à établir, cependant en moyenne elle est de . Ce tri a également la particularité d'avoir une complexité en pire cas de 
et le pire cas arrive quand le tableau initial est déjà trié!
Conclusion
Le tri est une opération courante en informatique et il existe bien d'autres manières que celles présentées de trier ici. Je donnerai dans un article à paraître des éléments complémentaires comme des preuves de complexité et des optimisations aux tris déjà présentés. En attendant vous pouvez vous amuser à les programmer dans les langages que vous maitrisez.