UNIVERSITÉ DE BLIDA 1
DÉPARTEMENT D’INFORMATIQUE
ALGORITHMIQUES ET
COMPLÉXITÉ
Resp.: H. YKHLEF
Email: [email protected]
Algorithmes de Tri des
Tableaux
INTRODUCTION
• Un tri consiste à ordonner de façon croissante (ou décroissante) une suite
d’éléments à partir des clés qui leur sont associées.
• Pour une suite de n éléments, il s’agit donc de trouver une permutation
particulière des éléments parmi les n! permutations possibles.
CATÉGORIES DE TRI
On distingue les tris internes des tris externes.
• Un tri est dit interne, si l’ensemble des clés à trier réside en mémoire principale.
• Les éléments à trier sont généralement placés dans des tableaux.
• Un tri est externe lorsque l’ensemble des clés ne peut résider en mémoire
centrale, et doit être conservé dans des fichiers.
• Ces tris utilisent des méthodes d’interclassement et cherchent à minimiser le
nombre de fichiers auxiliaires utilisés.
TRI PAR SÉLECTION: PRINCIPE
• Etant donné un tableau T de n nombres
• On sélectionne le maximum (le plus grand) de tous les éléments, et on le place
en dernière position n-1 par un échange.
• Il ne reste plus qu’à trier les n-1 premiers éléments, pour lesquels on itère le
procédé.
TRI PAR SÉLECTION: EXEMPLE
• Soit le tableau
• Le maximum de ce tableau est 7. Plaçons le 7 en dernière position par un échange.
• Le 7 est à sa position définitive ; il ne reste plus qu’à trier les cinq premiers éléments. Le
maximum de ces cinq éléments est 6. Plaçons-le à la fin par un échange :
TRI PAR SÉLECTION: EXEMPLE
• Le maximum parmi les nombres restant à trier est 5. Plaçons-le en dernière position par un
échange :
• Enfin le maximum parmi les nombres à trier est 3. On le place en dernier et le tableau est
trié.
TRI PAR SÉLECTION: ALGORITHME
Procedure tri_selection(Var T: Tableau d’Entier, n: Entier)
Var
max_i, tmp: Entier;
Debut
Pour i=n-1 à 1, i ←i-1 faire
max_i ← i;
Pour j=0 à i-1, j ←j+1 faire
Si T[max_i] < T[ j] alors
max_i ← j;
Fsi;
Fait;
tmp ← T[max_i];
T[max_i] ← T[i];
T[i] ← tmp;
Fait;
Fin.
TRI À BULLE: PRINCIPE
• Etant donné un tableau T de n nombres
• On échange deux éléments successifs T[ j] et T[ j+1] s’ils ne sont pas dans l’ordre.
• Plus précisément, on fait remonter le maximum à sa place définitive par
échanges successifs avec ses voisins.
• Évidemment, il faut faire cela un grand nombre de fois pour obtenir un tableau
trié.
TRI À BULLE: EXEMPLE
• Voici la succession des échanges d’éléments successifs effectués sur un exemple (itération 1).
0 1 2 3 4 5
6 3 4 2 3 5
3 6 4 2 3 5
3 4 6 2 3 5
3 4 2 6 3 5
3 4 2 3 6 5
3 4 2 3 5 6
TRI À BULLE: EXEMPLE
• On fait une deuxième passe :
0 1 2 3 4 5
3 4 2 3 5 6
Trié
3 4 2 3 5 6
3 2 4 3 5 6
3 2 3 4 5 6
3 2 3 4 5 6
TRI À BULLE: EXEMPLE
• On fait une troisième passe :
0 1 2 3 4 5
3 2 3 4 5 6
Trié
2 3 3 4 5 6
2 3 3 4 5 6
2 3 3 4 5 6
TRI À BULLE: EXEMPLE
• On fait une quatrième passe :
0 1 2 3 4 5
2 3 3 4 5 6
Trié
2 3 3 4 5 6
2 3 3 4 5 6
TRI À BULLE: ALGORITHME
Procedure tri_bulle(Var T: Tableau d’Entier, n: Entier)
Var
i,j, tmp: Entier; trie: Bool;
Debut
trie ← faux;
i←n-1;
Tant que i>0 Et trie=faux faire
trie ← vrai;
Pour j=0 à i-1, j ←j+1 faire
Si T[ j] > T[ j+1] alors
tmp ← T[ j];
T[ j] ← T[ j+1];
T[ j+1] ← tmp;
trie ← faux;
Fsi;
Fait;
i ←i-1;
Fait;
Fin.
TRI PAR INSERTION: PRINCIPE
• Etant donné un tableau T de n nombres
• On trie d’abord les deux premiers éléments;
• Puis on insère le 3ème à sa place pour faire une liste triée de 3 éléments;
• Puis on insère le 4ème élément dans la liste triée;
• La liste triée grossit jusqu’à contenir les n éléments.
TRI PAR INSERTION: EXEMPLE
• Soit le tableau
• En triant les deux premiers éléments on obtient :
• En insérant le troisième élément à sa place dans la liste triée :
TRI PAR INSERTION: EXEMPLE
• En insérant le quatrième élément à sa place dans la liste triée :
• En insérant le cinquième élément à sa place dans la liste triée :
• En insérant le sixième élément à sa place dans la liste triée :
TRI PAR INSERTION: ALGORITHME
Procedure tri_insertion(Var T: Tableau d’Entier, n: Entier)
Var
i,j, ins: Entier;
Debut
Pour i=1 à n-1, i ←i+1 faire
ins ← T[i];
Pour j=i-1 à 0, j ←j-1 faire
Si T[ j] >ins alors
T[ j+1] ← T[ j];
Sinon
Break;
Fsi;
Fait;
T[ j+1] ←ins;
Fait;
Fin.
TRI PAR FUSION: PRINCIPE
L’algorithme du tri par fusion suit la méthodologie diviser-pour-régner. Il agit de :
• Diviser : Diviser la suite de n éléments à trier en deux sous-suites de n/2
éléments chacune.
• Régner : Trier les deux sous-suites de manière récursive en utilisant le tri par
fusion.
• Combiner : Fusionner les deux sous-suites triées pour produire la réponse triée.
La récursivité s’arrête quand la séquence à trier a une longueur 1, auquel cas il n’y a
plus rien à faire puisqu’une suite de longueur 1 est déjà triée.
TRI PAR FUSION: PRINCIPE
• La procédure Tri_Fusion est donnée par :
Procedure Tri_Fusion(Var T: Tableau d’Entier, d,f: Entier)
Var m: Entier;
Debut
Si d<f alors
m ← (d+f) Div 2;
Tri_Fusion(T, d, m);
Tri_Fusion(T,m+1,f);
Fusion(T, d,m,f);
Fsi;
Fin.
• Pour trier toute la séquence T on fait l’appel initial Tri_Fusion(T, 0, n-1). « n » est le
nombre d’éléments de T.
TRI PAR FUSION: FUSION
• La clé de voûte de l’algorithme du tri par fusion est la fusion de deux séquences
triées dans l’étape « combiner ».
• Pour faire cette fusion, nous utilisons une procédure auxiliaire Fusion(T, d, m, f), T
étant un tableau et d, m et f étant des indices numérotant des éléments du
tableau tels que d ≤ m < f.
• La procédure suppose que les sous-tableaux T[d . . m] et T[m + 1 . . f] sont triés.
• Elle les fusionne pour en faire un même sous-tableau trié, qui remplace le sous-
tableau courant T[d . . f].
Procedure Fusion(Var T: Tableau d’Entier, d,m,f: Entier)
Var n1, n2: Entier; L: Tableau [n1+1] d’Entier; R: Tableau [n2+1] d’Entier;
Debut
1 n1 ← m − d + 1; 2 n2 ← f − m;
// créer tableaux L[0 . . n1-1] (T[d,...d+n1-1]) et R[0 . . n2-1] (T[m+1,....m+1+n2-1])
3 pour i ← 0 à n1-1 faire
4 L[i] ← T[d+i];
5 pour j ← 0 à n2-1 faire
6 R[ j] ← T[m +1+ j];
7 L[n1] ← ∞; 8 R[n2] ← ∞;
9 i ← 0; 10 j ← 0;
11 pour k ← d à f faire
12 si L[i] ≤ R[ j] alors
13 T[k] ← L[i]; 14 i ← i + 1;
15 sinon
16 T[k] ← R[ j]; 17 j ← j + 1;
Fin.
TRI PAR FUSION: EXEMPLE FUSION
m ← (d+f) Div 2 = 12
d m m+1 f
9 10 11 12 13 14 15 16
... 0 4 5 7 1 2 3 6 ...
0 1 2 3 4 0 1 2 3 4
L 0 4 5 7 ∞ R 1 2 3 6 ∞
i← 0 à 3 (n1-1) j ← 0 à 3 (n2-1)
n1 ← m-d +1 = 4 n2 ← f-(m +1)+1 = 4
Taille L est n1+1 Taille R est n2+1
TRI PAR FUSION: EXEMPLE FUSION
m ← (d+f) Div 2 = 12
d m m+1 f
9 10 11 12 13 14 15 16
... 0 4 5 7 1 2 3 6 ...
k
0 1 2 3 4 0 1 2 3 4
L 0 4 5 7 ∞ R 1 2 3 6 ∞
i j
n1 ← m-d +1 = 4 n2 ← f-(m +1)+1 = 4
Taille L est n1+1 Taille R est n2+1
TRI PAR FUSION: EXEMPLE FUSION
m ← (d+f) Div 2 = 12
d m m+1 f
9 10 11 12 13 14 15 16
... 0 1 5 7 1 2 3 6 ...
k
0 1 2 3 4 0 1 2 3 4
L 0 4 5 7 ∞ R 1 2 3 6 ∞
i j
n1 ← m-d +1 = 4 n2 ← f-(m +1)+1 = 4
Taille L est n1+1 Taille R est n2+1
TRI PAR FUSION: EXEMPLE FUSION
m ← (d+f) Div 2 = 12
d m m+1 f
9 10 11 12 13 14 15 16
... 0 1 2 7 1 2 3 6 ...
k
0 1 2 3 4 0 1 2 3 4
L 0 4 5 7 ∞ R 1 2 3 6 ∞
i j
n1 ← m-d +1 = 4 n2 ← f-(m +1)+1 = 4
Taille L est n1+1 Taille R est n2+1
TRI PAR FUSION: EXEMPLE FUSION
m ← (d+f) Div 2 = 12
d m m+1 f
9 10 11 12 13 14 15 16
... 0 1 2 3 1 2 3 6 ...
k
0 1 2 3 4 0 1 2 3 4
L 0 4 5 7 ∞ R 1 2 3 6 ∞
i j
n1 ← m-d +1 = 4 n2 ← f-(m +1)+1 = 4
Taille L est n1+1 Taille R est n2+1
TRI PAR FUSION: EXEMPLE FUSION
m ← (d+f) Div 2 = 12
d m m+1 f
9 10 11 12 13 14 15 16
... 0 1 2 3 4 2 3 6 ...
k
0 1 2 3 4 0 1 2 3 4
L 0 4 5 7 ∞ R 1 2 3 6 ∞
i j
n1 ← m-d +1 = 4 n2 ← f-(m +1)+1 = 4
Taille L est n1+1 Taille R est n2+1
TRI PAR FUSION: EXEMPLE TRI PAR FUSION
m ← (d+f) Div 2 = 3
d m m+1 f
0 1 2 3 4 5 6 7
Tri_Fusion( 5 4 2 8 9 14 1 6 )
1
0 1 2 3
Tri_Fusion( 5 4 2 8 )
2
Tri_Fusion( 5 4 )
3 4
Tri_Fusion( 5 ) Tri_Fusion( 4 )
TRI PAR FUSION: EXEMPLE TRI PAR FUSION
m ← (d+f) Div 2 = 3
d m m+1 f
0 1 2 3 4 5 6 7
Tri_Fusion( 5 4 2 8 9 14 1 6 )
1
0 1 2 3
Tri_Fusion( 5 4 2 8 )
5
2
Tri_Fusion( 4 5 ) Tri_Fusion( 2 8 )
3 6 7
4
Tri_Fusion( 5 ) Tri_Fusion( 4 ) Tri_Fusion( 2 ) Tri_Fusion( 8 )
TRI PAR FUSION: EXEMPLE TRI PAR FUSION
m ← (d+f) Div 2 = 3
d m m+1 f
0 1 2 3 4 5 6 7
Tri_Fusion( 5 4 2 8 9 14 1 6 )
1
0 1 2 3
Tri_Fusion( 2 4 5 8 )
5
2
Tri_Fusion( 4 5 ) Tri_Fusion( 2 8 )
3 6 7
4
Tri_Fusion( 5 ) Tri_Fusion( 4 ) Tri_Fusion( 2 ) Tri_Fusion( 8 )
TRI PAR FUSION: EXEMPLE TRI PAR FUSION
m ← (d+f) Div 2 = 3
d m m+1 f
0 1 2 3 4 5 6 7
Tri_Fusion( 5 4 2 8 9 14 1 6 )
1 8
0 1 2 3 4 5 6 7
Tri_Fusion( 2 4 5 8 ) Tri_Fusion( 9 14 1 6 )
5
2
.........
Tri_Fusion( 4 5 ) Tri_Fusion( 2 8 )
3 6 7
4
Tri_Fusion( 5 ) Tri_Fusion( 4 ) Tri_Fusion( 2 ) Tri_Fusion( 8 )
TRI RAPIDE: PRINCIPE
Le tri rapide est fondé sur le paradigme diviser-pour-régner. Voici les étapes de ce
paradigme:
Diviser : Le tableau T[d . . f] est partitionné (réarrangé) en deux sous-tableaux
(éventuellement vides) T[d . . q − 1] et T[q + 1 . . f] tels que chaque élément de T[d . .
q − 1] soit ≤ à T[q] qui, lui-même, est ≤ à chaque élément de T[q + 1 . . f]. L’indice q
(pivot) est calculé dans le cadre de cette procédure de partitionnement.
Régner : Les deux sous-tableaux T[d . . q−1] et T[q+1 . . f] sont triés par des appels
récursifs au tri rapide.
TRI RAPIDE: PRINCIPE
• La procédure suivante implémente le tri rapide. Quick sort
Procedure TRI_RAPIDE(T: Tableau d’Entier, d, f:Entier)
Var q: Entier;
Debut
Si d < f alors
q ← PARTITION(T, d, f);
TRI_RAPIDE(T, d, q − 1);
TRI_RAPIDE(T, q + 1, f);
Fsi;
Fin.
• Pour trier un tableau T entier, l’appel initial est TRI_RAPIDE(T, 0, n-1).
d f
0 1 2 3 4 5 6 7 8
TRI_RAPIDE( 2 8 7 1 3 15 16 6 4 )
PARTITION 2 1 3 4 7 15 16 6 8
d q f
1 Pivot 4
d0 1 2 f d4 5 6 7 8f
TRI_RAPIDE( 2 1 3 ) TRI_RAPIDE( 7 15 16 6 8 )
PARTITION 2 1 3 PARTITION 7 6 8 15 16
d qf d q f
2 …
5
d f
0 1
TRI_RAPIDE( 2 1 ) .........
PARTITION 1 2
dq f
3
d 0 f
TRI_RAPIDE( 2 )
TRI RAPIDE: PARTITIONNER LE TABLEAU
• Le point principal de l’algorithme est la procédure PARTITION, qui réarrange le sous-tableau
T[d . . f] sur place. La fonction retourne l’indice du pivot.
Fonction PARTITION(T: Tableau d’Entier, d, f: Entier)
Var x, i , j : Entier;
Debut
x ← T[f]; i ← d − 1;
Pour j ← d à f – 1 faire
Si T[ j] ≤ x alors
i ← i + 1; permuter T[i] ↔ T[ j];
Fsi;
Fait;
permuter T[i + 1] ↔ T[f];
Retourner i + 1;
Fin.
d 0 1 2 3 4 5 6 7 f
Pivot
2 8 7 1 3 5 6 4
TRI RAPIDE: PARTITIONNER LE i j
TABLEAU
2 8 7 1 3 5 6 4
Fonction PARTITION(T: Tableau d’Entier, d, f: Entier)
i j
Var x, i , j : Entier;
2 8 7 1 3 5 6 4
Debut
i j
x ← T[f]; i ← d − 1;
2 8 7 1 3 5 6 4
Pour j ← d à f – 1 faire i j
Si T[ j] ≤ x alors 2 1 7 8 3 5 6 4
i ← i + 1; permuter T[i] ↔ T[ j]; i j
Fsi; 2 1 3 8 7 5 6 4
Fait; i j
permuter T[i + 1] ↔ T[f]; 2 1 3 8 7 5 6 4
Retourner i + 1; i j
Fin.
2 1 3 8 7 5 6 4
i j
2 1 3 4 7 5 6 8
i j
