Chapitre II

Algorithmes de Tri
1. Définition
Les tableaux permettent de stocker plusieurs éléments de même type au sein d’une seule entité,
Lorsque le type de ces éléments possède un ordre total, on peut les ranger en ordre croissant ou
décroissant. Trier un tableau, c’est donc ranger ses éléments en ordre croissant ou décroissant. Dans
ce cours on ne fera que les tris en ordre croissant. Pour obtenir un ordre décroissant, il suffit
d’inverser le raisonnement.

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.

Notons que tous les algorithmes de tri utilisent une fonction qui permet d’échanger (de permuter)
les valeurs de deux variables. Dans le cas où les variables sont entières, la fonction échanger est la
suivante :

void echanger (int* a, int* b) {

int temp ;
temp = *a ;
*a = *b ;
*b = temp ;
}

2. Tri par sélection (ou minimum successif)

2.1. Principe
On parcourt le tableau de gauche à droite, et on positionne à chaque fois le plus petit élément qui se
trouve dans le sous tableau droit.

Plus généralement, pour trier le sous-tableau t[i..nbElements], il suffit de positionner au rang i le plus
petit élément de ce sous-tableau et de trier le sous-tableau t[i+1..nbElements].

Par exemple, pour trier <101, 115, 30, 63, 47, 20>, on va avoir les boucles suivantes :

Itération 1 : <20, 115, 30, 63, 47, 101>

Itération 2 : <20, 30, 115, 63, 47, 101>

Itération 3 : <20, 30, 47, 63, 115, 101>

Itération 4 : <20,30, 47, 63, 115, 101>

Donc, en sortie à l’itération 5 : <20, 30, 47, 63, 101, 155>

2.2. Algorithmique
Il nous faut donc une fonction qui soit capable de déterminer le plus petit élément (l’indice du plus
petit élément) d’un tableau à partir d’un certain rang :

int indiceDuMinimum (int* t, int rang, int nbElements) {

int i, indiceCherche ;

1
Matière : ASD 3 Chapitre 2 Algorithmes de Tri

indiceCherche = rang ;
for (i = rang+1 ; i < nbElements ; i++) {
if (t[i] < t[indiceCherche])
indiceCherche = i ;
}
return indiceCherche ;
}

L’algorithme de tri est donc :

void TriParSelection (int* t, int nbElements) {

int i, indice ;
for (i = 0 ; i < nbElements ; i++) {
indice = indiceDuMinimum (t, i, nbElements) ;
if (i != indice)
echanger(&t[i], &t[indice]) ;
}
}

2.3. Complexité
Notons ctri−select(n) le nombre de comparaisons des éléments du tableau à effectuer pour trier un
tableau de longueur n par le tri par sélection. Et notons cselect−min(k) le nombre de comparaisons à
effectuer pour sélectionner l'indice du minimum d'une tranche de tableau de longueur k.

ctri−select(n) = ∑𝑛𝑘=2 cselect−min (k), et comme cselect−min(k) = k – 1 :

𝑛(𝑛−1) 𝑛2
ctri−select(n) = ∑𝑛𝑘=2(𝑘 − 1) = 2
~ 2

Donc la complexité est en O(n2).

3. Tri à bulles
3.1. Principe
Il consiste à sélectionner le minimum du tableau en parcourant le tableau de la fin au début et en
échangeant tout couple d’éléments consécutifs non ordonnés.

Par exemple, pour trier <101, 115, 30, 63, 47, 20>, on va avoir les boucles suivantes :

i=1: <101, 115, 30, 63, 47, 20>

<101, 115, 30, 63, 20, 47>

<101, 115, 30, 20, 63, 47>

<101, 115, 20, 30, 63, 47>

<101, 20, 115, 30, 63, 47>

i=2: <20, 101, 115, 30, 63, 47>

i=3: <20, 30,101, 115, 47, 63>

i=4: <20, 30, 47, 101, 115, 63>

i=5: <20, 30, 47, 63, 101, 115>

2
Matière : ASD 3 Chapitre 2 Algorithmes de Tri

Donc en sortie : <20, 30, 47, 63, 101, 155>

3.2. Algorithmique
void TriBulles (int* t, int nbElements) {
int i, k ;
for (i = 0; i < nbElements-1; i++) {
for (k = nbElements-1; k > i; k--) {
if (t[k] < t[k-1])
echanger(&t[k], &t[k-1]) ;
}
}
}

3.3. Complexité
Identique au tri par sélection. Le nombre de tests (pire des cas) est : T(n) = n + T(n−1) ⇒ T(n) = n + (n-
1) + (n-2) + … + 1 = n(n+1)/2, donc complexité en O(n2).

4. Tri par insertion

4.1. Principe
L'algorithme du tri par insertion consiste à construire une tranche triée de longueur croissante en
insérant successivement le premier élément non considéré dans la tranche triée en construction.

Exemple :

i tableau
1 ITMOLEON
2 IMTOLEON
3 IMOTLEON
4 ILMOTEON
5 EILMOTON
6 EILMOOTN
7 EILMNOOT

4.2. Algorithmique
void TriInsertion (int* t, int nbElements) {
int i, k, aux ;
for (i = 1; i < nbElements; i++) {
aux = t[i];
k = i;
while ((k > 0) && (aux < t[k – 1])) {
t[k] = t[k – 1];
k = k – 1;
}
t[k] = aux ;
}
}

3
Matière : ASD 3 Chapitre 2 Algorithmes de Tri

4.3. Complexité
Notons ctri−insert(n) le nombre de comparaisons d'éléments du tableau à effectuer pour trier un
tableau de longueur n par le tri par insertion.

n − 1 ≤ ctri−insert(n) ≤ (n − 1)(n − 2)/2 ∼ n2/2

La minoration (meilleur des cas) est atteinte pour un tableau trié. Et la majoration (pire des cas) est
atteinte pour un tableau trié dans l'ordre inverse, donc complexité en O(n2)

5. Tri par fusion

5.1. Principe
Le tri fusion est construit suivant la stratégie "diviser pour régner". Ce principe est tout à fait
applicable au problème de tri : plutôt que de trier le tableau complet, il est préférable de trier deux
sous tableaux de taille égale, puis de fusionner les résultats.

Un algorithme récursif est très pratique. En effet, les deux sous tableaux seront eux même triés à
l'aide du même algorithme de tri fusion. Un tableau ne comportant qu'un seul élément sera
considéré comme trié : c'est la condition d’arrêt de fin du tri.

La méthode de tri par fusion nécessite un tableau intermédiaire aussi grand que le tableau initial à
trier, et c'est là où réside le principal inconvénient.

Exemple :

Soit le tableau T Suivant :

T : 12 3 0 15 -5 22 23 -7 10 8 8 12 34 35 3

On peut diviser ce tableau en deux sous tableaux d'entiers T1 et T2 de longueurs respectives 7 et 8.

T1 : 12 3 0 15 -5 22 23
T2 : -7 10 8 8 12 34 35 3

Triés par ordre croissant les deux sous tableaux T1 et T2

T1 : -5 0 3 12 15 22 23
T2 : -7 3 8 8 10 12 34 35

Le résultat sera rangé dans le tableau T.

Etape 1 : On commence par :

- comparer le premier élément de chacun des deux tableaux T1 et T2. Le plus petit est T2[0]==
-7
- placer -7 dans T[0] et se pointer à l'élément n°2 de T2
- se pointer à l'élément n°2 de T. T : -7

Etape 2 :

- comparer le premier élément de T1 et le deuxième élément de T2. Le plus petit est T1[0]==-5
- placer -5 dans T [1] et se pointer à l'élément n°2 de T1
- se pointer à l'élément n°3 de T. T : -7 -5

Etape 3 :

4
Matière : ASD 3 Chapitre 2 Algorithmes de Tri

- comparer T1 [1] et T2 [1]. Le plus petit est T1 [1] == 0

- placer 0 dans T [3] et se pointer à l'élément n°3 de T1
- se pointer à l'élément n°4 de T. T : -7 -5 0

On poursuit la fusion de cette façon jusqu'à la fin de l'un des deux tableaux

T : -7 -5 0 3 3 8 8 10 12 12 15 22 23

Tous les éléments du tableau T1 ont été rangés dans le tableau T, il ne reste que des éléments dans
le tableau T2. Ces éléments vont être transférés directement dans le tableau T.

T : -7 -5 0 3 3 8 8 10 12 12 15 22 23 34 35

5.2. Algorithmique
int a[n];

int b[n];

void sort (int debut, int fin) {

int milieu;
if (debut < fin) {
milieu = (debut + fin) / 2;
sort(debut, milieu);
sort(milieu +1, fin);
merging(debut, milieu, fin);
} else {
return;
}
}
void merging (int debut, int milieu, int fin) {
int l1, l2, i;

for (l1 = debut, l2 = milieu + 1, i = debut; l1 <= milieu && l2 <= fin; i++) {
if (a[l1] <= a[l2])
b[i] = a[l1++];
else
b[i] = a[l2++];
}

While (l1 <= milieu)

b[i++] = a[l1++];

while(l2 <= fin)

b[i++] = a[l2++];

for(i = debut; i <= fin; i++)

a[i] = b[i];
}
5.3. Complexité
Voir document annexe au chapitre.

5
Matière : ASD 3 Chapitre 2 Algorithmes de Tri

6. Tri rapide
6.1. Principe
Il consiste à choisir un élément du tableau appelé pivot, puis ordonner les éléments du tableau par
rapport au pivot ; appeler récursivement le tri sur les parties du tableau, i.e. à gauche et à droite du
pivot.

Choisir un élément (le “pivot”) p dans le tableau T

• Placer les éléments inférieurs à p au début de T

• Placer p à sa place dans T
• Placer les éléments supérieurs à p à la fin de T
• Trier la première partie de T puis la seconde. . .

Exemple :

L = [ 4, 23, 3, 42, 2, 14, 45, 18, 38, 16 ]

Choix arbitraire du pivot : l'élément le plus à droite ici 16

• Balayage à gauche :

4 < 16 => il est dans la bonne sous-liste, on continue

liste en cours de construction : [ 4,16 ]
23 > 16 => il est mal placé il n'est pas dans la bonne sous-liste, on arrête le balayage gauche,
liste en cours de construction :[ 4,23, 16 ]
• Balayage à droite :
38 > 16 => il est dans la bonne sous-liste, on continue
liste en cours de construction : [ 4,23, 16, 38 ]
18 > 16 => il est dans la bonne sous-liste, on continue
liste en cours de construction : [ 4,23, 16, 18, 38 ]
45 > 16 => il est dans la bonne sous-liste, on continue
liste en cours de construction : [ 4,23, 16, 45, 18, 38 ]
14 < 16 => il est mal placé il n'est pas dans la bonne sous-liste, on arrête le balayage droit,
liste en cours de construction : [ 4,23, 16, 14, 45, 18, 38 ]
• Echange des deux éléments mal placés :

[ 4, 23, 16, 14, 45, 18, 38 ] ----> [ 4,14, 16, 23, 45, 18, 38 ]

 On reprend le balayage gauche à l'endroit où l'on s'était arrêté :

-------------------------------------
[ 4, 14, 3, 42, 2, 23, 45, 18, 38, 16 ]

3 < 16 => il est dans la bonne sous-liste, on continue

liste en cours de construction : [ 4,14, 3 ,16, 23, 45, 18, 38 ]
42 > 16 => il est mal placé il n'est pas dans la bonne sous-liste, on arrête de nouveau le
balayage gauche,
liste en cours de construction : [ 4, 14, 3, 42, 16, 23, 45, 18, 38 ]

 On reprend le balayage droit à l'endroit où l'on s'était arrêté :

-------------------------------------
[ 4, 14, 3, 42, 2, 23, 45, 18, 38, 16 ]
2 < 16 => il est mal placé il n'est pas dans la bonne sous-liste, on arrête le balayage droit,
liste en cours de construction : [ 4,14, 3, 42, 16, 2, 23, 45, 18, 38 ]

6
Matière : ASD 3 Chapitre 2 Algorithmes de Tri

 On procède à l'échange :
[ 4, 14, 3, 2, 16, 42, 23, 45, 18, 38 ]
et l'on arrête la construction puisque nous sommes arrivés au pivot la fonction partition a
terminé son travail elle a évalué :
- le pivot : 16
- la sous-liste de gauche : L1 = [4, 14, 3, 2]
- la sous-liste de droite : L2 = [23, 45, 18, 38, 42]
- la liste réarrangée : [ 4,14, 3, 2, 16, 42, 23, 45, 18, 38 ]
Il reste à recommencer les mêmes opérations sur les parties L1 et L2 jusqu'à ce que les partitions ne
contiennent plus qu'un seul élément.

6.2. Algorithmique
int Partition(int* Tab, int G, int D) {
int i, j, piv, temp;
piv = Tab[D];
i = G-1;
j = D;
do {
do { i = i+1; } while (Tab[i] < piv && i < D);
do { j = j-1; } while (Tab[j] > piv && j > G);
temp = Tab[i];
echanger(&Tab[i], &Tab[j]) ;
}
while (j > i);
Tab[j] = Tab[i];
Tab[i] = Tab[D];
Tab[D] = temp;
return (i);
}

TriRapide(int* Tab, int G, int D) {

int i;
if (D > G) {
i = Partition(Tab, G, D);
TriRapide(Tab, G, i-1);
TriRapide(Tab, i+1, D);
}
}

6.3. Complexité
Comme tous les algorithmes qui divisent et traitent le problème en sous-problèmes tel que le tri par
fusion, le nombre moyen de comparaisons est en O([Link](n)) que l'on nomme complexité moyenne.

L'expérience pratique montre que cette complexité moyenne en O([Link](n)) n’est atteinte que
lorsque les pivots successifs divisent la liste en deux sous-listes de taille à peu près équivalente.

Dans le pire des cas (par exemple le pivot choisi est systématiquement à chaque fois la plus grande
ou la plus petite valeur) on montre que la complexité est en O(n²).

Soit T(n) le temps total pour le pire des cas. On a :

7
Matière : ASD 3 Chapitre 2 Algorithmes de Tri

T(n) = T(n-1) + n

Puisque nous divisons le tableau en deux parties, l'une consiste en un seul élément et l'autre en n-1
et nous traverserons un tableau individuel.

T(n) = T(n-2) + (n-1) + n = T(n-2) + 2n - 1

T(n) = T(n-3) + 3n - 2 - 1

T(n) = T(n-k) + k*n - (k-1) - ..... - 2 - 1

T(n) = T(n-k) + k* n - [(k-1) .... + 3 + 2 + 1]

T(n) = T(n-k) + k*n - [k*(k-1)/2]

Mettons n=k

T(n) = T(0) + n*n - [n*(n-1)/2] = ½n2 - ½ n

Donc T(n) = O(n2)