Cours: Algorithmique et Structures de données

Chapitre III :
1

Algorithmes de Tri

L’objectif de ce troisième chapitre est d’introduire la notion de Tri et de présenter quelques

algorithmes de tri existants dans la littérature tout en calculant leur complexité et ce dans le
but de comparer leurs performances

1. Définition

Soit un vecteur A[1..n] à n valeurs dans un ensemble E de valeurs muni d’une relation d’ordre
notée ≤, trier le vecteur A dans un ordre croisant consiste à permuter les éléments du vecteur
A[1..n] entre eux de sorte à ce que tous les éléments consécutifs du vecteur A vérifient la
condition suivante: A[i] ≤ A[i+1].

Il existe plusieurs méthodes de tri qui se différencient par leur complexité d’exécution et leur
complexité de compréhension pour le programmeur. La classification de ces algorithmes est
très importante, car elle permet de choisir l’algorithme le plus adapté au problème traité, tout
en tenant compte des contraintes imposées par celui-ci. Les principales caractéristiques qui
permettent de différencier les algorithmes de tri, outre leur principe de fonctionnement, sont
la complexité temporelle, la complexité spatiale et le caractère stable.

2. Les méthodes de Tri

2.1. Tri par Insertion

2.1.1. Principe du tri par insertion

Le principe du tri par insertion est de parcourir une liste non triée en la décomposant en deux
parties une partie déjà triée (initialement, le premier élément de la liste) et une partie non
triée.

L'opération de base consiste à prendre l'élément frontière dans la partie non triée, puis à
l'insérer à sa place dans la partie triée (place que l'on recherchera séquentiellement), puis à
déplacer la frontière d'une position vers la droite. Ces insertions s'effectuent tant qu'il reste un

Dr KHAMTACHE-KHOULALENE Nadjet
 Cours: Algorithmique et Structures de données

élément à ranger dans la partie non triée. L'insertion de l'élément frontière est effectuée par
2
décalages successifs d'une cellule.

Exemple : soit à trier le tableau A= [30, 9, 13, 7, 10]

Etape 1 : Initialement, la partie triée du tableau est le premier élément de ce dernier, soit le
30 car il est admis qu’un tableau ne contenant qu’un seul élément est considéré trié. La partie
non triée sera, quant à elle, constituée du reste des éléments du tableau, à savoir [9, 13, 7, 10].
L'élément frontière dans la partie non triée est le 9, qu'il va falloir placer, à la bonne place,
dans la partie triée. On obtient comme résultat de cette première étape, après le décalage du
30, le tableau suivant : A= [9, 30, 13, 7, 10].

Etape 2 : A présent, il sera question de placer le 13 (A= [9, 30, 13, 7, 10]) dans la partie triée
qui est [9, 30]. Le 13 <30, on fait donc un décalage du 30 vers la droite (A= [9, 30, 30, 7, 10])
puis on fait une comparaison entre le 13 et 9. Vu que 13>9, on arrête le processus de décalage
et on place le 13 juste après le 9. Le résultat sera comme suit:

A= [9, 13, 30, 7, 10]

Etape 3 : A cette étape, la partie triée est constituée des éléments [9, 13, 30] alors que la
partie non triée est [7, 10]. On procède à la comparaison de l'élément frontière de la partie non
triée, à savoir le 7, aux éléments de la partie triée, en commençant par le 30. On effectue un
décalage vers la droite à chaque fois que 7 est inférieur à un élément de la partie triée du
tableau et ce jusqu'à ce que le 7 trouve sa place (dans ce cas la première place, car le 7 est
inférieur à tous les éléments de la partie triée). On procède par décalage comme suit:

A= [9, 13, 30, 7, 10]

A= [9, 13, 30, 30, 10]

A= [9, 13, 13, 30, 10]

A= [9, 9, 13, 30, 10]

A= [7, 9, 13, 30, 10]

Etape 4 : il reste un seul élément à placer à savoir le 10, dans le sous-tableau trié A= [7, 9,
13, 30]. Le même processus de l'étape précédente sera adopté :

Dr KHAMTACHE-KHOULALENE Nadjet
 Cours: Algorithmique et Structures de données

A= [7, 9, 13, 30, 30]

3
A= [7, 9, 13, 13, 30]

On arrête le décalage car le 10 > 9 et on place le 10 au bon endroit (entre le 9 et le 13). Le

résultat sera comme suit: A= [7, 9, 10, 13, 30]

Etape 5 : Le processus s’arrête car le tableau est trié et qu'il ne reste plus d'éléments à
placer.

2.1.2. Algorithme du tri par insertion

L’algorithme du tri par insertion est comme suit:

Procédure Tri_insertion (Var A : Tableau [1..100] d’entiers ; n : entier) ;

Var i, j, X: entier ;
Début
Pour j allant de 2 à n Faire
X  A[j] ;
i  j-1 ;
Tant que ( i>0) et (A[i]>X) Faire
A[i+1] A[i] ;
ii-1 ;
Fin
A[i+1]X ;
Fin
Fin

2.1.3. Complexité de l'algorithme du tri par insertion

Le pire des cas pour cet algorithme est le cas où le tableau, en entrée, est initialement trié dans
un ordre décroissant. Dans ce cas, le coût C(n) de cet algorithme est calculé comme suit:

Dr KHAMTACHE-KHOULALENE Nadjet
 Cours: Algorithmique et Structures de données

Instruction Nombre d’opérations Nombre d’exécution

4
j← 2 1 1
j≤n 1 n
X← A[j] 1 n-1
i← j-1 2 n-1
𝑛
(i>0) et A[i]>X 3
∑𝑖
𝑖=2
𝑛−1
A[i+1] ← A[i] 2
∑𝑖
𝑖=1

2 𝑛−1
i←i-1
∑𝑖
𝑖=1

A[i+1] ← X 2 n-1
j← j+1 2 n-1
n n−1

C(n) = 1 + n + 7(n − 1) + 3 ∑ i + 4 ∑ i
i=2 i=1

n n

C(n) = 8n − 6 + 3(∑ i − 1) + 4(∑ i − n)

i=1 i=1

C(n) = 8n − 6 − 3 − 4n + 7 ∑ i
i=1

C(n) = 4n − 9 + 7 ∑ i
i=1

n(n + 1)
C(n) = 4n − 9 + 7
2

n2 + n
C(n) = 4n − 9 + 7
2

𝑛2 n
C(n) = 7 + 15 − 9
2 2

Ainsi, la complexité de l’algorithme du tri par insertion est en O(n2).

Dr KHAMTACHE-KHOULALENE Nadjet
 Cours: Algorithmique et Structures de données

2.2. Tri à Bulles

5
2.2.1. Principe du tri à bulles

Le principe du tri à bulles consiste à comparer deux à deux les éléments consécutifs A[i] et
A[i+1] d'un vecteur et d'effecteur une permutation dans le cas où A[i] > A[i+1]. On continue
de trier jusqu'à ce qu'il n'y ait plus de permutation à effectuer. En d'autres termes, on s'arrête
dès que l'on détecte que le tableau est trié : si aucune permutation n'a été faite au cours d'une
passe.
Exemple : soit à trier le tableau A= [1, 4, 2, 10, 0]
Etape 1 :
 On commence par comparer A[1] et A[2] et comme A[1] < A[2], le tableau reste
inchangé. 1 4 2 10 0

 Par la suite on compare A[2] et A[3] et comme A[2]>A[3], on effectue une permutation:

1 2 4 10 0

 Comparaison entre A[3] et A[4] et le tableau reste inchangé car A[3] < A[4].

1 2 4 10 0

 Enfin, comparaison entre A[4] et A[5]. Une permutation sera effectuée car A[5]<A[4].

1 2 4 0 10

Etape 2 : A l'issue de l'étape précédente, nous avons pu placer la plus grande valeur du
tableau au niveau la dernière case de ce dernier mais nous n'avons pas encore trier tout le
tableau. De ce fait, nous allons réitérer le même processus en ne considérant que les 4
premiers éléments du tableau.

1 2 4 0 10

1 2 4 0 10

1 2 4 0 10

1 2 0 4 10

Dr KHAMTACHE-KHOULALENE Nadjet
 Cours: Algorithmique et Structures de données

Etape 3: A présent, nous n'allons considérer que les 3 premiers éléments du tableau car la
6
deuxième plus grande valeur du tableau est placée au niveau de l'avant dernière case de ce
dernier (quatrième case).
1 2 0 4 10

1 0 2 4 10

1 0 2 4 10

Etape 4: Il ne reste plus qu'un couple de valeurs à comparer à savoir A[1] et A[2] et vu que
A[1] < A[2], on effectue une permutation.

0 1 2 4 10

2.2.2. Algorithme du tri à bulles

L’algorithme de tri à bulles est comme suit:

Procédure Tri_bulles (Var A : Tableau [1..100] d’entiers ; n : entier) ;

Var i, X: entier ;
Trier: Booléen;
Début
Trier Faux;
TQ (Trier=faux) Faire
Trier Vrai;
Pour i=1 à (n-1) Faire
Si (A[i]> A[i+1]) Alors
X  A[i];
A[i]  A[i+1];
A[i+1] X;
Trier Faux;
Fin ;
Fin ;
n  n-1;
Fin ;
Fin ;

Dr KHAMTACHE-KHOULALENE Nadjet
 Cours: Algorithmique et Structures de données

2.2.3. Complexité de l'algorithme du tri à bulles

7
Dans le meilleur des cas, avec des données déjà triées, l'algorithme du tri à Bulles effectuera
seulement (n-1) opérations de comparaisons. Sa complexité dans le meilleur des cas est donc
en Θ(n).
Dans le pire des cas, avec des données triées à l'envers, les parcours successifs du tableau
imposent d'effectuer (n2-n)/2 comparaisons et échanges. On a donc une complexité dans le
pire des cas du tri à bulles en Θ(n2).

2.3. Tri par sélection

2.3.1. Principe du tri par sélection

Le tri par sélection est l’un des tris les plus instinctifs. Le principe est que pour classer n
valeurs, il faut rechercher la plus grande valeur et la placer en fin de liste, puis rechercher la
plus grande valeur dans les valeurs restantes et la placer en avant dernière position,... etc.

 Exemple : Soit à trier le tableau suivant : A= [7, 13, 3, 9, 2]

Etape 1 : le maximum dans le tableau A est le 13, on le place au niveau de la dernière case.
Un échange de valeurs entre A[2] et A[5] sera effectué. On obtient le tableau suivant : A=
[7, 2, 3, 9, 13]

Etape 2 : Même principe en considérant un tableau de taille 4 (partie non triée du tableau):
recherche du maximum parmi ces valeurs [7, 2, 3, 9]. Dans ce cas c’est le 9, qui est à la
bonne place. Le tableau reste donc inchangé : A= [7, 2, 3, 9, 13]

Etape 3 : A cette étape, la taille du sous-tableau non trié est égale à 3 et le maximum parmi
les trois valeurs restantes est le 7 : permutation entre A[1] et A[3]. On obtient le tableau
suivant : A= [3, 2, 7, 9, 13]

Etape 4 : Il reste un couple de valeur (3,2) à trier. On effectue une permutation entre A[1]
et A[2] car A[1] > A[2]. On obtient ce qui suit : A= [3, 2, 7, 9, 13]

Etape 5 : Le processus s’arrête car il ne reste plus qu’une seule case à exploiter et c’est
forcément la plus petite valeur du tableau (le minimum est A[1]).

Dr KHAMTACHE-KHOULALENE Nadjet
 Cours: Algorithmique et Structures de données

2.3.2. Algorithme du tri par sélection

8
L’algorithme du tri par sélection est comme suit :

Procédure Tri_Selection (Var T : Tableau [1..100] d’entiers ; n :entier) ;

Var i, indMax, V : entier ;
Début
TQ (n>1) Faire
indMax  1;
Pour i=2 à n Faire
Si (T[i]> T[indMax]) Alors
indMax  i;
Fin ;
Fin ;
Si (n<> indMax) Alors
V  T[indMax];
T[indMax]  T[n];
T[n] V;
Fin ;
n  n-1;
Fin ;
Fin ;

2.3.3. Complexité de l'algorithme du tri par sélection

Pour effectuer le tri par sélection, il faut procéder à la recherche de la position (l’indice) de la
plus grande valeur dans le tableau. La plus grande valeur est alors échangée avec la dernière
valeur du tableau. Par la suite, on réitère l’algorithme sur le tableau constitué des (n-p)
premiers éléments du tableau où p est le nombre de fois que l’algorithme a été itéré.
L’algorithme se termine quand p=n-1, c’est-à-dire quand il ne reste qu’une seule valeur ;
celle-ci est alors la plus petite valeur du tableau.

Le pire des cas pour cet algorithme est le cas où le tableau, en entrée, est initialement trié dans
un ordre décroissant. Dans ce cas, le coût de cet algorithme est calculé comme suit:

Dr KHAMTACHE-KHOULALENE Nadjet
 Cours: Algorithmique et Structures de données

Instruction Nombre d’opérations Nombre d’exécution

9
Taille paire Taille impaire
n>1 1 n n
indMax  1 1 n-1 n-1
i← 2 1 n-1 n-1
𝑛 𝑛
i≤n 1
∑𝑖 ∑𝑖
𝑖=2 𝑖=2
T[i]> T[indMax] 1 𝑛−1 𝑛−1

∑𝑖 ∑𝑖
𝑖=1 𝑖=1
𝐧 𝐧
indMax  i 1 −𝟏  −𝟏 𝐧
2 ∑𝟐𝒊=𝟏 𝒊 2 ∑𝒊=𝟏
𝟐
𝒊+ 
𝟐

2 𝑛−1 𝑛−1
i← i+1
∑𝑖 ∑𝑖
𝑖=1 𝑖=1

n<> indMax 1 𝑛−1 𝑛−1

V  T[indMax] 1 𝒏 𝒏−𝟏
𝟐 𝟐
T[indMax]  T[n] 1 𝒏 𝒏−𝟏
𝟐 𝟐
T[n] V 1 𝒏 𝒏−𝟏
𝟐 𝟐
n← n-1 2 n-1 n-1

De ce fait, la complexité de l’algorithme du tri par sélection est en O(n2).

2.4. Le Tri par fusion

2.4.1. Principe du tri par fusion

Le principe de l’algorithme du tri par fusion est de diviser le tableau à trier de taille n en deux
sous-tableaux de taille n/2 et ensuite de les fusionner une fois triés. Cet algorithme est
récursif ; il s’agit d’un tri suivant le paradigme Diviser pour Régner : on divise le tableau en
deux sous-tableaux qui eux même sont divisés en deux sous-tableaux,…etc. La condition
d’arrêt est d'avoir un tableau ne contenant qu’un seul élément.

Dr KHAMTACHE-KHOULALENE Nadjet
 Cours: Algorithmique et Structures de données

10
Exemple :
Soit à trier le tableau suivant : A [7, 14, 12, 4, 3, 20, 17, 1]

7 14 12 4 3 20 17 1

7 14 12 4
3 20 17 1

Division
17 1
7 14 12 4
3 20
A chaque étape, le
tableau est divisé en
2 jusqu’à l’obtention 12 4 3 17 1
7 14 20
d’un tableau de taille
1

7 14 4 12 3 20 1 17

A chaque étape, on
fusionne les sous- 4 7 12 14 1 3 17 20
tableaux de sorte à
avoir des sous-
tableaux triés Fusion

1 3 4 7 12 14 17 20

Dr KHAMTACHE-KHOULALENE Nadjet
 Cours: Algorithmique et Structures de données

2.4.2. Algorithme du tri par fusion

11
L'algorithme du tri par fusion est comme suit:

Procédure triFusion(var A : Tableau [1..100] d’entiers, début, fin : Entier) ;

Variables milieu : entier
Début
Si (début < fin) Alors
milieu ←(début + fin) Div2 ;
triFusion(A, début, milieu) ;
triFusion(A, milieu+1, fin) ;
fusionner(A,debut,milieu,fin) ;
FinSi ;
Fin ;

Procédure Fusionner(var A: Tableau [1..100] d’entiers , début, milieu, fin : entier) ;

Variables i, i1, i2 : entier ; tmp: Tableau [1..100] d’entiers ;

Début
i ←0 ; i1 ←début ; i2 ←milieu + 1 ;
Tantque (i1 <= milieu) et (i2 <= fin) Faire
Si A[i1] < A[i2] Alors
tmp[i] ←A[i1] ;
i1 ←i1 +1 ;
Sinon
tmp[i] ←A[i2] ;
i2 ←i2 + 1;
FinSi ;
i ←i + 1 ;
FinTantque ;

Tantque ( i1 <= milieu) Faire

tmp[i] ←A[i1] ; i ←i + 1 ; i1 ←i1 + 1 ;
FinTantque ;

Tantque (i2 <= fin) Faire

Tmp[i] ←A[i2] ; i ←i + 1 ; i2 ←i2 + 1 ;
FinTantque ;

A ← Tmp ;
Fin ;

Dr KHAMTACHE-KHOULALENE Nadjet
 Cours: Algorithmique et Structures de données

2.4.3. Complexité de l'algorithme du tri par fusion 12

a) Forme générale d'un algorithme Diviser pour Régner et théorème maître :

La forme générale d’un algorithme diviser pour régner est comme suit :
1) Diviser : en découpe le problème initial en ′𝑎′ sous problème de taille 𝑛⁄𝑏 qui sont de
même nature avec 𝑎 ≥ 1 𝑒𝑡 𝑏 > 1.
2) Régner: les sous-problèmes sont résolus récursivement.
3) Recombiner : on utilise les solutions des sous-problèmes pour reconstruire la solution
du problème initial.
L’équation qu’on aura à résoudre, quand on traduit l’algorithme en équation sur la
complexité, est la suivante :
𝒏
𝑻(𝒏) = 𝑫(𝒏) + 𝒂 𝑻 ( ) + 𝑪(𝒏)
𝒃
Avec :
 𝑫(𝒏) le coût de la division
 𝑪(𝒏) e coût la reconstitution

𝑛
On pose 𝑓(𝑛) = 𝐷(𝑛) + 𝐶 (𝑛) ainsi 𝑇(𝑛) = 𝑎 𝑇 (𝑏 ) + 𝑓(𝑛)

Ainsi, T(n) peut être borné asymptotiquement comme suit :

 si 𝑓(𝑛) = 𝑂(𝑛(𝑙𝑜𝑔𝑏𝑎)−𝜀 ) pour une certaine constante 𝛆 >0 , alors 𝑇(𝑛) = Θ(𝑛𝑙𝑜𝑔𝑏𝑎 )
 si 𝑓(𝑛) = Θ(𝑛𝑙𝑜𝑔𝑏𝑎 ) alors 𝑇(𝑛) = Θ(𝑛𝑙𝑜𝑔𝑏𝑎 log 𝑛)
 si 𝑓(𝑛) = 𝛺(𝑛(𝑙𝑜𝑔𝑏𝑎)+𝜀 ) alors 𝑇(𝑛) = Θ(𝑓(𝑛))

2.5. Tri Rapide

2.5.1. Principe du tri rapide

Le tri rapide est basé sur le paradigme diviser pour régner. Ainsi, pour trier un tableau A[p,r],
on utilise les trois étapes du paradigme Diviser pour Régner, à savoir:

1) Diviser: On choisit un élément de A[p, r] qu'on notera pivot. Par la suite, on

partitionne le tableau A[p, r] en deux sous-tableaux A[p, q] et A[q + 1, r] tels que :
 A[q] = pivot
 Les éléments de A[p, q] sont ≤pivot
 Les éléments de A[q + 1, r] sont > pivot.

Dr KHAMTACHE-KHOULALENE Nadjet
 Cours: Algorithmique et Structures de données

2) Régner: On trie récursivement les sous-tableaux A[p, q] et T[q + 1, r].

13
3) Combiner: Par construction, il n'y a rien à faire

Exemple : Soit à trier le tableau suivant : A [27, 63, 1, 71, 64, 58, 94, 9]

On choisit comme pivot le 27 63 1 71 64 58 94 9

premier élément du
tableau: Pivot=27

On place toutes les valeurs

9 1 27 71 64 58 94 63 inferieurs à 27 avant le 27 et
toutes les valeurs supérieure à 27
après.

Le pivot est premier élément Le pivot est premier élément

du premier sous-tableau: du deuxième sous-tableau:
Pivot=9 Pivot=71

9 1 27 71 64 58 94 63

1 9 27 63 64 58 71 94 Sous-tableau
contenant un seul
élément (il est trié)
Il ne reste que ce
sous-tableau à trier:
Pivot=63

1 9 27 58 63 64 71 94

2.5.2. Algorithme du tri rapide

L’algorithme du tri rapide est comme suit:

Procédure triRapide(var A : Tableau [1..100] d’entiers, début, fin : entier) ;

Variables indexPivot : entier ;
Début
Si (début < fin) Alors
partitionner(A, début, fin, indexPivot) ;
triRapide(A, début, indexPivot -1) ;
triRapide(A, indexPivot +1, fin) ;
FinSi ;
Fin ;

Dr KHAMTACHE-KHOULALENE Nadjet
 Cours: Algorithmique et Structures de données

14
Procédure Partitionner(var A :Tableau[1..100] d’entiers; début, fin:entier, var indexPivot:
entier) ;
Variables i, pivot, cpt : entier ;
Début
cpt← début ;
pivot ← A[début] ;
Pour i ←début+1 à fin Faire
si A[i] < pivot Alors
cpt ← cpt+1
permuter(A[i],A[cpt]);
FinSi ;
FinPour ;
permuter(A[cpt],A[début]) ;
indexPivot ← cpt ;
Fin ;

Conclusion:

Le tri est un problème fondamental de l’algorithmique. En général, son but est de

préparer des données pour permettre d’y rechercher rapidement une information. Il existe bon
nombres d'algorithmes de Tri, mais certains sont bien plus utilisés que d'autres en pratique.
Le tri par insertion est souvent plébiscité pour des données de petite taille, tandis que des
algorithmes asymptotiquement efficaces, comme le tri par fusion ou le Tri rapide seront
utilisés pour des données de plus grande taille.

Dr KHAMTACHE-KHOULALENE Nadjet