Trier veut dire ordonner un ensemble
d’éléments, les ranger en ordre
croissant ou décroissant :
· Tri croissant : si l’élément d’indice i
est inférieur ou égal à l’élément d’indice i+1.
· Tri décroissant : si l’élément d’indice i
est supérieur ou égal à l’élément d’indice
i+1.
Le but du tri est de faciliter l’utilisation d’un ensemble de données, par exemple pour un algorithme de recherche, fusion, éclatement . . .
Tri Interne – Tri Externe :
Un tri interne s’effectue sur des données présentes en mémoire centrale. L’accès aux informations ne prend que peu de temps. Pour évaluer le temps de calcul, on ne considère que le nombre de combinaisons et de permutations.
Un tri externe s’effectue sur des données résidant en mémoires secondaires (disquettes, disques durs…). Dans ce cas le temps d’accès aux informations devient plus important car il s’agit d’un organe mécanique qui tourne. C’est pourquoi en général, on cherche à minimiser le nombre d’accès aux mémoires secondaires.
Très souvent, tri interne est équivalent à tri de tableaux, et tri externe est équivalent à tri de fichiers rangés séquentiellement.
Quelques méthodes de tri :
Il existe plusieurs méthodes de tris. Nous allons présenter quelques-unes.
Dans tous les algorithmes qui suivront, on considère un tableau de 100 cases, dont n remplies par des valeurs réelles. Nous nous intéresserons au tri croissant. La saisie et l’affichage des éléments sont supposées faites par d’autres algorithmes appelants.
Tri par SELECTION :
C’est l’une des méthodes les plus simples pour trier les éléments d’un tableau : T [1], T [2], T [3]…, T [n] en ordre croissant par exemple.
Nous allons balayer tous les éléments pour chercher le plus petit que nous échangeons avec T [1].
Nous répétons en cherchant le plus petit élément parmi T [2] jusqu’à T[n] que nous échangeons avec T [2] et ainsi de suite.
Après (n-1) application de cette recherche et échange, les éléments du tableau sont triés.
Algorithme de sélection :
Var
T : tableau : [1..100] de réels ;
n,s,min,i,j : entiers ;
Début
(* Tri des éléments du tableau *)
Pour i <-- 1 à (n-1) faire
Min <-- T[i] ;
Pour j <-- i+1 à n faire
Si min > T[j] alors
Min <-- T[j] ;
s <-- j ;
FinSi
FinPour j
Si min < T[i] alors
T[s] <-- T[i] ;
T[i] <-- min ;
FinSi
FinPour i
Fin
On note min la valeur de minimum et s l’indice de cette valeur.
N.B : La présentation des autres algorithmes se
fera dans les prochains articles.
Principe du tri par extraction :
Cette méthode utilise en plus du tableau à trier un deuxième tableau dans lequel on place les éléments triès.
On cherche le plus petit élément dans le premier tableau et on le place au début du deuxième tableau
Ensuite on cherche le plus petit élément parmi ceux non encore sélectionnées du premier tableau et on le place dans le deuxième tableau jusqu’à ce que tous les éléments soient recopiés dans le deuxième tableau. A chaque fois qu’un élément est sélectionné, il est remplacé par une valeur spéciale pour ne pas être présélectionné une deuxième fois.
Algorithme du tri par extraction :
Var
T,T1 : tableau [1..100] de réels ;
n,ind,i,j : entiers ;
max : reel;
Début
Pour i <-- 1 à n faire
Ind <-- 1 ;
Pour j <-- 2 à n faire
Si T[ind] > T[j] alors
ind <-- j ;
FinSi
FinPour j
T1[i] <-- T[ind] ;
T[ind] <-- max ;
FinPour i
Fin
On note max la valeur spéciale, plus grande que tous les éléments du tableau(dans le cas d’un tri croissant) et plus petite que tous les éléments du tableau (dans le cas d’un tri décroissant). Avant de lancer l’algorithme de tri par extraction, on peut appliquer au tableau T un algorithme de recherche du maximum auquel on ajoute 1 pour déterminer la valeur de max (max=max(T) + 1), ind est l’indice du plus petit élément trouvé.
Exemple d’utilisation :
Soit le tableau suivant composé de 6 éléments (n=6) .
15
|
2
|
24
|
-8
|
0
|
4
|
max = maximum(T) + 1 = 24 + 1 = 25.
i=1 :
15
|
2
|
24
|
25
|
0
|
4
|
I=2 :
15
|
2
|
24
|
25
|
25
|
4
|
i=3
15
|
25
|
24
|
25
|
25
|
4
|
i=4
15
|
25
|
24
|
25
|
25
|
25
|
i=5
25
|
25
|
24
|
25
|
25
|
25
|
i=6
25
|
25
|
25
|
25
|
25
|
25
|
Le résultat dans le tableau T1 :
-8
|
0
|
2
|
4
|
15
|
24
|
Remarquons qu’à la fin, le tableau T ne contient plus que les valeurs spéciales 25. Et T1 contient les anciens éléments de T triés par ordre croissant.
Conclusion :
Le tri par extraction est un algorithme de tri par comparaison. Il est particulièrement simple, mais inefficace sur de grandes entrées, car il s'exécute en temps quadratique en le nombre d'éléments à trier.
Le tri à bulles ou tri par propagation est un algorithme detri qui consiste à faire remonter progressivement les plus grands éléments d'un tableau, comme lesbulles d'air remontent à la surface d'un liquide.
Le principe du tri Bulles :
La méthode consiste à faire plusieurs balayages du tableau en ordonnant les paires d’éléments adjacents, de bas en haut.
A la fin du premier balayage, l’élément le plus grand est remonté au sommet du tableau comme une bulle d’air dans l’eau.
Lors du deuxième balayage, on ne considère que la partie non triée du tableau pour obtenir à la fin le deuxième plus grand élément sous le plus grand et ainsi de suite jusqu’à ce que le tableau soit complétement trié (par ordre croissant).
Algorithme du tri par Bulles :
Var
T : tableau [1..100] de réels ;
n,v,i : entiers ;
aux : réel ;
Début
v <-- n ;
Tantque v>1 faire
Pour i <--1 à (v-1) faire
Si T[i] > T[i+1] alors
Aux = T[i] ;
T[i] = T [i+1] ;
T [i+1] = aux ;
FinSi
FinPour i
v <-- v-1 ;
Fin
On note que v est le compteur des balayages, il varie entre n et 2 et dans chaque cas de figure i variera entre 1 et (v-1).
aux est la variable auxiliaire servant pour la permutation des éléments comparés, s’ils sont en désordre.
Exemple d’utilisation :
Soit le tableau suivant composé de 5 éléments (n=5).
7
|
3
|
14
|
5
|
10
|
1er Balayage
|
7
|
3
|
14
|
5
|
10
|
7
|
3
|
14
|
10
|
5
|
7
|
14
|
3
|
10
|
5
|
14
|
7
|
3
|
10
|
5
|
A la fin du 1er Balayage l’élément 14 est au sommet du tableau.
2ème Balayage
|
14
|
7
|
3
|
10
|
5
|
14
|
7
|
10
|
3
|
5
|
14
|
10
|
7
|
3
|
5
|
A la fin du 2eme Balayage l’élément 10 est en dessous du plus grand élément.
3ème Balayage
|
14
|
10
|
7
|
3
|
5
|
14
|
10
|
7
|
5
|
3
|
14
|
10
|
7
|
5
|
3
|
A la fin du 3ème balayage le tableau est bel et bien trié.
Conclusion :
Le tri à bulles est souvent enseigné en tant qu'exemple algorithmique. Cependant, sa complexité est de l'ordre de n² en moyenne (où n est la taille du tableau), ce qui le classe parmi les mauvais algorithmes de tri. Il n'est donc quasiment pas utilisé en pratique.
Tags
algorithme