Les structures de
donnes
Rajae El Ouazzani
Les mthodes de tri des
lments dun tableau
2
Dfinition
Les mthodes de tri permettent le rarrangement de donnes.
Par exemple, le tableau suivant :
peut tre tri par nom :
ou tri par ge :
3
Salma 21
Sami 33
Laila 27
Laila 27
Salma 21
Sami 33
Salma 21
Laila 27
Sami 33
Les mthodes de tri dans un tableau
Il existe plusieurs mthodes de tri.
Dans ce cours, nous allons voir:
Tri par slection (rappel);
Tri par insertion (rappel);
Tri bulles;
Tri rapide (quick sort).
4
Tri par slection
Principe :
Dabord, on cherche llment de plus petite valeur dans le
tableau pour lchanger avec llment qui se trouve en premire
position;
Puis, on cherche llment ayant la deuxime plus petite valeur
pour lchanger avec llment qui se trouve en deuxime position;
Et ainsi de suite.
NB: Le tri par slection consiste slectionner le minimum
5
Pour raliser le tri par slection, il faut :
1 boucle pour parcourir le tableau et slectionner tous les
lments;
1 boucle pour rechercher le minimum parmi les lments
non tris.
Algorithme du tri par slection
6
j
N-1 i+1
0
i
N-2
Droulement de
lalgorithme
7
N=6
i=0;min=0; j=1 5 >min=2; 20<>1
i=1;min=1; j=2 5 >min=4; 6<>1
i=2;min=2; j=3 5 >min=3; 20<>3
i=3;min=3; j=4 5 >min=4; 20<>6
i=4;min=4; j=5 >min=5; 20<>7
Arrt: i=N-2=4
0 1 2 3 4 5
Exercice
Traduire lalgorithme en C
8
Tri par slection en C
9
void tri_selection(int t[], int n) {
int i, min, j , tmp;
for(i = 0 ; i < n - 1 ; i++)
{
min = i;
for(j = i+1 ; j < n ; j++)
if(t[j] < t[min])
min = j;
if(min != i) // Si min i, on fait lchange.
{
tmp = t[i];
t[i] = t[min];
t[min] = tmp;
}
}
}
Exercice
Trier par la mthode de slection le tableau suivant:
Tourner le programme de tri par slection. Monter les
valeurs de i, j, min, tmp, t[i], t[j] et t[min]aprs
chaque itration.
10
Tri par insertion
Principe :
On prend les lments les uns aprs les autres en insrant chacun
sa place parmi les lments dj tris.
11
Pour raliser le tri par insertion, il faut :
1 boucle pour parcourir le tableau et slectionner llment
insrer;
1 boucle pour dcaler les lments plus grands que llment
insrer;
insrer llment.
Algorithme du tri par insertion
12
i 1
1
i
N-1
j
Droulement de lalgorithme
13
i=1; mem=6; j=1; 20>6: t[1]=20 ; j=0 t[0]=6
i=2; mem=1; j=2; 20>1: t[2]=20,j=1; 6>1: t[1]=6, j=0; t[0]=1
i=3; mem=3; j=3; 20>3: t[3]=20, j=2; 6>3: t[2]=6, j=1; 1<3:stop. t[1]=3
i=4; mem=1; j=4; 3 dc(20,6,3):t[4]=20, t[3]=6, t[2]=3; 1=1: stop t[1]=1
i=5; mem=7; j=5; 20>7: t[5]=20, j=4; 6<7: arrt t[4]=7
Arrt: i=N-1=5
0 1 2 3 4 5
Exercice
Traduire lalgorithme en C
14
Tri par insertion en C
15
void tri_insertion(int t[], int n)
{
int i ,j, mem;
for (i = 1; i < n; i++)
{
mem = t[i];
j = i;
while (j>0 && t[j-1]>mem) {
t[j]= t[j-1];
j=j-1;
}
t[j] = mem;
}
}
Exercice
Appliquer lalgorithme du tri par insertion sur le
tableau suivant:
Tourner le programme de tri par insertion. Monter
les valeurs de i, j, j-1, mem, t[i], t[j]et t[j-1]aprs
chaque itration.
16
17
Tri bulles
Principe :
On parcours autant de fois le tableau en permutant 2
lments adjacents (voisins) mal classs jusqu ce
que le tableau soit tri.
18
Pour raliser le tri bulles, il faut:
1 boucle pour parcourir tout le tableau et slectionner les
lments un un;
1 boucle pour permuter les lments adjacents.
Algorithme du tri bulles
19
i
N-1 0
1
j
i
Droulement de lalgorithme
20
i=5, j=1 5;
20<>6, 20<>1,
20<>3, 20<>1,
20<>7
i=4, j=1 4;
1<>6, 6<>3,
6<>1
i=3, j=1 3;
3<>1
i=2
i=1
i=0
0 changmt
Exercice
Traduire lalgorithme en C
21
Tri bulles en C
22
void tri_a_bulle(int t[],int n){
int i, j, tmp;
for(i=n-1;i--;i>=0){
for (j=1 ;j<=i ; j++){
if (t[j-1]>t[j]){
tmp = t[j-1];
t[j-1] = t[j];
t[j] = tmp;
}
}
}
}
Exercice
Faites tourner lalgorithme de tri bulles sur le
tableau suivant:
Monter les valeurs de i, j, tmp, t[j]et t[j-1] aprs
chaque itration.
23
Solution
24
Comparaison des performances
des tris lmentaires
25
Tri rapide (Quick Sort)
Principe: diviser pour rsoudre
1. Choisir un seuil (pivot) ;
2. Mettre les lments plus petits que le seuil
gauche du seuil et les lments plus grands
droite;
3. Recommencer sparment sur les parties droite
et gauche.
26
Algorithme du tri rapide
27
3 7 8 5 2
i j
g d
p
Exercice
Traduire lalgorithme en C
28
Tri rapide en C
void tri_rapide(int t[], int n, int g, int d) {
int i, j, p, x, tmp ;
i=g; j=d; p=t[(i+j)/2];
do {
while (t[i]<p) i++;
while (t[j]>p) j--;
if(i<=j){
tmp=t[i];
t[i]=t[j];
t[j]=tmp;
i++;
j--;
}
} while(i<=j);
if( g<j) tri_rapide(t,n,g,j);
if (i<d) tri_rapide(t,n,i,d);
}
29
Exemple
30
3 7 8 5 2
i j
g d
p
1
re
itration
3 7 8 5 2
i
j
g d
p
3 et 7<8=> i=3
2<8 =>j =5 ( reste fixe)
3 7 2 5 8
i
j
g d
p
i<=j : 8<>2
i=4 et j=4
31
3 7 2 5 8
j
i
g d
p
5<8=> i =5
5<8=>j =4 (reste fixe)
i>j => arrt
Rsultat: i>j et g<j => trier la partie gauche du tableau
i<=j alors rpter 3 7 2 5 8
i
j
g d
p
32
3 7 2 5 8
j i
g d
p
Changer les indices de g et d
avec un nouveau tableau
Calculer le pivot p=7
2
me
itration
3 7 2 5 8
j
i
g d
p
3<7=> i =2
5<7=> j=4 (reste fixe)
3 5 2 7 8
j
i
g d
p
i<=j : 7<>5
i=3 et j=3
33
3 5 2 7 8
g d
2<7=> i =4
2<7=> j =3 (reste fixe)
i>j => arrt
i>j et g<j => trier la partie gauche
3 5 2 7 8
i j
g d
p
g=g et d=j
Calculer le pivot: p=5
i
j p
3 5 2 7 8
j
i
g d
p
i<=j alors rpter
34
2<=3: 5<>2
i =3et j=2
3 2 5 7 8
i
j
g
d
p
i>j et g<j => trier la partie gauche
3
me
itration
3<5=> i =2
2<5=> j =3 (reste fixe)
3 5 2 7 8
i
j
g
d
p
3 5 2 7 8
i j
g
d
p
g=g et d=j
Calculer le pivot: p=5
35
i>j et g=j => la partie gauche est trie
Et d=i => la partie droite est trie aussi
ARRET
2 3 5 7 8
i j
g
d
p
4
me
itration
3 2 5 7 8
i j
g
d
p
g=g et d=j
Calculer le pivot: p=3
3 2 5 7 8
j
g
d
p
i
i<j : 3<>2
i =2 et j=1
3 2 5 7 8
i j
g
d
p
3=3=> i=1 (reste fixe)
2<3=> j=2 (reste fixe)
Autre version de lalgorithme du
tri rapide
36
37
Performance du tri rapide
Le Tri le plus utilis :
relativement simple;
de lordre de NlogN oprations, en moyenne, pour trier
N lments;
de lordre de N
2
oprations dans le pire des cas : le
tableau est tri de manire dcroissante.
38
