Algorithmes de tri

1. Introduction

2. Tri par sélection

3. Tri par insertion

4. Tri à bulle

5. Tri rapide

6. Tri par fusion

1
 Introduction
• Le terme "trier" signifie «répartir des objets suivant certains
critères».
• En algorithmique, le terme "tri" est souvent attaché au
processus de classement d'une suite d’éléments dans un ordre
donné.
Exemple:
– Trier N entier dans un ordres croissant.
– Trier N étudiants dans l'ordre décroissant de leurs moyennes (réel).
– Trier N noms dans l'ordre alphabétique croissant.
– Trier des fichiers selon leurs tailles.

2
 Introduction
• D'une façon générale, tout ensemble muni d'un ordre total peut
fournir une suite d'éléments à trier.
• Deux catégories de tris :

– Les tris internes : méthodes destinées à des masses de

données limitées, stockées dans une structure de données se
trouvant dans la mémoire centrale (Exemple : tableaux).
– Les tris externes : méthodes destinées à de grandes masses
de données, stockées dans des structures de données telle
que les fichiers.

3
 Introduction
• Le tri est fondamental à beaucoup pour la résolution des
problèmes, et après le tri, beaucoup de problèmes deviennent
faciles à résoudre. par exemple :
• La recherche d’un élément.
• Unicité d’éléments: après le tri tester les éléments adjacents.
• Déterminer le plus petit et le plus grand élément.
• Déterminer le k-ième plus grand élément en O(1).

4
 Tri par sélection
Principe:
Répéter:
- Chercher le plus petit (plus grand) élément => Sélection.
- Mettre l’élément sélectionné au début de la partie non triée.

D’une autre manière

• Trouver le plus petit élément et le mettre au début du tableau
• Trouver le 2e plus petit éléments et le mettre en seconde position
• Trouver le 3e plus petit éléments et le mettre à la 3e place,
• ...

5
 Tri par sélection
Exemple: T 10 12 25 30 2 17 4

min = 2
Etape 1: Faire l’échange entre 2 (min) et 10
2 12 25 30 10 17 4

min = 4
Etape 2: Faire l’échange entre 4 (min) et 12
2 4 25 30 10 17 12

min = 10
6
 Tri par sélection

Etape 3: Faire l’échange entre 10 (min) et 25

2 4 10 30 25 17 12

Etape 4: Faire l’échange entre 12 (min) et 30

2 4 10 12 25 17 30

Etape 5: Faire l’échange entre 17 (min) et 25

2 4 10 12 17 25 30

Etape 6: 25 (min) est à sa palce

2 4 10 12 17 25 30 7
 Tri par sélection (Algorithme)
Procédure TriSelection (Var T : Tableau d’entiers, N : entier)
i, j, indMin , temp : entier;
Début
Pour i allant de 1 à N-1 faire
indMin = i; /* recherche de l’indice
Pour j allant de i+1 à N du minimum */
si (T[j] < T[indMin]) alors
indMin = j;
Fin Si
Fin Pour

temp = T[i]; /* échange des valeurs entre

T[i] = T[indMin]; la case courante et le
minimum */
T[indMin] = tmp;
Fin pour
Fin
8
 Tri par sélection (Algorithme)
Procédure TriSelection (Var T : Tableau d’entiers, N : entier)
i, j, indMin , temp : entier;
Début
Pour i allant de 1 à N-1 faire
indMin  indiceMin (T, i, N)
échanger (T, i, indMin);
Fin pour
Fin
• La fonction indiceMin retourne l’indice du minimum du la partie
du tableau [i, N]
• La fonction échanger faire la permutation entre l’élément i et le
minimum

9
 Tri par sélection
Exercice: appliquer l’algorithme de tri par sélection pour le tri d’une
liste chainée.

10
 Tri par sélection (Complexité)
• Le pire des cas, le plus mauvais cas et le cas moyen sont pareils.
• Pour trouver le plus petit élément, (n-1) itérations sont
nécessaires,
• Pour le 2ème plus petit élément, (n-2) itérations sont
effectuées, .…
• Pour trouver le dernier plus petit élément, 0 itérations sont
effectuées.
• Le nombre d’itérations que l’algorithme effectue est donc :
(n-1) * (n-2) /2 ➔ O (N2)

11
 Tri par Insertion
Principe:
Répéter:
• Insertion du prochain élément dans la partie qui est déjà triée
précédemment.
• La partie de départ qui est triée est le premier élément.
• Il se pourrait qu’on a à déplacer plusieurs éléments pour l’insertion.

1 i N
Les i-1 premiers éléments
Eléments à Les éléments non triés
déjà triés
insérer

12
 Tri par Insertion
Principe:
(le tri du joueur de cartes !)
• Ordonner les deux premiers éléments
• Insérer le 3e élément de manière à ce que les 3
premiers éléments soient triés
• Insérer le 4e élément à “sa” place pour que. . .
•...
• Insérer le nième élément à sa place.

A la fin de la i ème itération, les i premiers éléments de T sont tries.

13
 Tri par Insertion
Exemple:
T 10 12 5 30 2 17 4

Etape 1: insérer 12 à sa place

10 12 5 30 2 17 4

Etape 2: insérer 5 à sa place

5 10 12 30 2 17 4

14
 Tri par Insertion

Etape 3: insérer 30 à sa place

5 10 12 30 2 17 4

Etape 4: insérer 2 à sa place

2 5 10 12 30 17 4

Etape 5: insérer 17 à sa place

2 5 10 12 17 30 4

Etape 6: insérer 4 à sa place

2 4 5 10 12 17 30 15
 Tri par Insertion (Algorithme)
Procédure TriInsertion (Var T : Tableau d’entiers, N : entier)
i, k : naturels;
temp : entier;
Début
Pour i=2 à N faire
temp  t[i]; k  i;
Tant que (k > 1 et t[k-1] > temp) faire
T [k]  T[k - 1];
k  k - 1;
Fin tant que
T[k]  temp;
Fin pour
Fin

16
 Tri par Insertion (Complexité)
• Comme nous n’avons pas nécessairement à scanner toute la
partie déjà triée, le pire cas, le meilleur cas et le cas moyen
peuvent différer entre eux.

• Meilleur des cas: Chaque élément est inséré à la fin de la partie

triée. Dans ce cas, nous n’avons à déplacer aucun élément.
Comme nous avons à insérer (n-1) éléments, chacun générant
seulement une comparaison, la complexité est en O(n).

• Pire des cas: Chaque élément est inséré au début de la partie

trié. Dans ce cas, tous les éléments de la partie triée doivent être
déplacés à chaque itération.
La ième itération génère (i-1) comparaisons et échanges de
valeurs. 𝑂( 𝑛2 )

17
 Tri à bulle
Principe:
Répéter:
• Parcourir le tableau en comparant deux à deux les éléments
successifs, permuter s'ils ne sont pas dans l'ordre.
• Répéter tant que des permutations sont effectuées.

• Après le premier parcours, le plus grand élément étant à sa position

définitive, il n'a plus à être traité.
• Le reste du tableau est en revanche encore en désordre. Il faut donc le
parcourir à nouveau, en s'arrêtant à l'avant-dernier élément.
• Après ce deuxième parcours, les deux plus grands éléments sont à leur
position définitive.
• Il faut donc répéter les parcours du tableau, jusqu'à ce que les deux plus
petits éléments soient placés à leur position définitive.
18
 Tri à Bulle
Exemple: T 12 10 5 30 2 17

Itération 1:
12 10 5 30 2 17

10 12 5 30 2 17

10 5 12 30 2 17

10 5 12 30 2 17

10 5 12 2 30 17

10 5 12 2 17 30 19
 Tri à Bulle
Itération 2:

10 5 12 2 17 30

5 10 12 2 17 30

5 10 12 2 17 30

5 10 2 12 17 30

5 10 2 12 17 30

20
 Tri à Bulle
Itération 3:

5 10 2 12 17 30

5 10 2 12 17 30

5 2 10 12 17 30

5 2 10 12 17 30

21
 Tri à Bulle
Itération 4:

5 2 10 12 17 30

2 5 10 12 17 30

2 5 10 12 17 30

22
 Tri à Bulle

Itération 5:

2 5 10 12 17 30

2 5 10 12 17 30

Aucun changement arrêt de l’algorithme

23
 Tri à Bulle (Algorithme)
Procédure TriBulle (Var T : Tableau d’entiers, N : entier)
i : naturels;
B: Bouléen;
Début
Répéter
B  Faux;
Pour i allant de 1 à N -1 faire
Si T[i] >T[i+1] alors
Echanger (T, i, I+1);
B Vrai;
Finsi
Fin pour
NN-1;
Jusqu'à B=faux
Fin
24
 Tri à Bulle (Complexité)
• Le tri à bulles est souvent enseigné en tant qu'exemple
algorithmique, car son principe est simple. Mais c'est le plus lent
des algorithmes de tri communément enseignés, et il n'est donc
guère utilisé en pratique.

• Meilleur des cas: le tableau est trié. Dans ce cas, nous n’avons à
déplacer aucun élément. la complexité est en O(n).

• Pire des cas: le tableau est trié dans l’ordre inverse. Dans ce cas,
la complexité est 𝑂( 𝑛2 ).

25
 Tri rapide
Principe:
Inventé en 1960 par Sir Charles Antony Richard Hoare basé sur le
paradigme diviser pour régner consiste à:
• Choisir un élément « pivot »
• Diviser l’ensemble ou le tableau à deux sous-ensembles
• Un sous ensemble contient les éléments inférieurs au pivot et la
deuxième contient les éléments supérieurs au pivot.
(Partitionnement)
• Répéter la procédure récursivement jusqu’au chaque ensemble
contient un seul élément.

26
 Tri rapide
Principe:
Éléments inferieurs au pivot Éléments supérieurs au pivot
pivot

pivot pivot

27
 Tri Rapide
Exemple: T 12 10 5 30 2 25 17

- Choisir un pivot (17)

- Mettre les éléments <17 dans la partie gauche du pivot et les
éléments >=17 dans la partie droite

12 10 5 2 17 25 30

12 10 5 2 25 30

5 2 10 12 25 30

28
 Tri Rapide

12 10 5 2 17 25 30

12 10 5 2 25 30

5 2 10 12 25 30

5 2 10 12 25 30

2 5 10 12 25 30

2 5 10 12
12 25 30

2 5 10 12 25 30 29
 Tri Rapide(Algorithme)
Procédure TriRapide (Var T : Tableau d’entiers, deb, fin: entier)
pivot: entier
Début
Si deb <fin alors
pivot  partitionner (T, deb, fin);
TriRapide (T, deb, pivot -1);
TriRapide (T, pivot +1, fin);
Finsi
Fin

30
 Tri Rapide(Algorithme)
Fonction partitionner (Var T : Tableau d’entiers, deb, fin: entier):
entier
pivot: entier
Début
pivot  T[(deb + fin) /2];
ideb; jfin;
Tantque i<j faire
Tantque T[i] < pivot faire ii+1; Fin Tantque
Tantque T[j] > pivot faire jj-1; Fin Tantque
Echanger (T, i, j);
Fin Tantque
Retourne i;
Fin

31
 Tri Rapide(Complexité)
• La partie du tri la plus sensible reste le choix du pivot. Le choix
peut se révéler catastrophique : si le pivot est à chaque choix le
plus petit élément du tableau, alors le tri rapide dégénère en tri
par sélection.
• La complexité de ce tri est :
– Le meilleur des cas, en O (N log2 N) ;
– En moyenne, en O (N log2 N) ;
– Dans le pire des cas, en O (N2).

32
 Tri par fusion
Principe:
Inventé en 1948 par Goldstine et Von Neumann en 1948.
• Applique le principe « diviser pour régner ».
• Basé sur l’idée que s’il y a deux suites d’éléments triés, il est
très facile d’obtenir une troisième suite d’éléments triés, par «
interclassement » (ou fusion) des deux précédentes suites. Le
principe de ce tri consiste:
– Diviser l’ensemble ou le tableau en deux sous-ensembles
– Trier les deux sous ensembles.
– Fusionner les deux sous ensembles

33
 Tri par fusion
Principe:
Etant donné un tableau (ou une liste) de T[1, ...,n] :
• Si n = 1, retourner le tableau T !
• Sinon :
▪ Trier le sous-tableau T[1 . . .n/2 ]
▪ Trier le sous-tableau T[ n/2 + 1 . . . n]
▪ Fusionner ces deux sous-tableaux. . .
• Il s’agit d’un algorithme “diviser-pour-régner”.

34
 Tri par fusion
Principe:
T[1..N/2] T[N/2 +1 …N]
7 1 15 20 8 24 8 22 9 4 30

7 1 15 20 8 24 8 22 9 4 30

1 7 8 15 20 24 4 8 9 22 30

1 4 7 8 8 9 15 20 22 24 30
35
 Tri par fusion(Algorithme)
Fonction Tri_Fusion (Var T : Tableau d’entiers, deb, fin: entier)
mil: entier
Début
Si deb < fin alors
mil ← (deb + fin)/2
Tri_fusion (T,deb,mil);
Tri_fusion (T, mil+1, fin);
Fusion (T, deb, mil, fin);
Finsi
Fin

36
 Tri par fusion
Procédure Fusionner (var T: Tableau, deb, mil, fin : entier )
T1: Tableau
Début
i 1; jMil+1;
Pour k de deb à fin aire
Si (j> fin) ou (i ≤ mil et T[i] ≤ T[j] ) alors
T1 [k] ← T[i];
ii+1
Sinon
T1 [k] ← T[j];
jj+1
Fin si
Fin pour
Copier (T, T1, K);
Fin
37
 Tri par fusion(Complexité)
• Le tri par fusion est un tri optimal sur les listes (tableaux), de
complexité O(n log (n)). Il s’agit de décomposer une liste en deux
sous-listes chacune deux fois plus petites, de les trier
séparément, puis de fusionner les résultats en une liste triée.

• Le nombre de comparaisons nécessaires est de l'ordre de :

• 0 (n log n).
• L'espace mémoire requis est en O (n).

38
Complexité des algorithmes de tri

39
 Propriété des algorithmes de tris
Tri stable:
• Un algorithme de tri est dit stable si deux éléments
ayant la même valeur conservent leur ordre relatif
initial après le tri.
– Algorithmes stables :
• Tri par insertion
• Tri par fusion
• Tri par bulles
– Algorithmes non stables :
• Tri rapide
• Tri par sélection

40
 Propriété des algorithmes de tris
• Type de tri
– Tri interne : Lorsque toutes les données
tiennent en mémoire principale.
• Exemples : Tri par sélection, insertion, bulles,
rapide.
– Tri externe : Pour des volumes de données
dépassant la mémoire disponible (utilise des
fichiers ou un stockage secondaire).
• Exemples : Tri par fusion dans les bases de
données.

41
 Propriété des algorithmes de tris
• Mesure l’espace mémoire supplémentaire
nécessaire pour exécuter l’algorithme.
– In-place : Les algorithmes qui ne nécessitent
pas d’espace supplémentaire important pour
effectuer le tri.
• Exemples : Tri rapide, tri par sélection, tri par
insertion.
– Non in-place : Nécessitent un espace
supplémentaire pour stocker des copies des
données.
• Exemples : Tri par fusion. 42
 Propriété des algorithmes de tris
• Tri par sélection :
• Sélectionne l’élément minimum à chaque
itération et l’échange avec le premier
élément non trié.

• Simple à implémenter, mais inefficace

pour de grands ensembles de données.

43
 Propriété des algorithmes de tris
• Tri par insertion :
• Insère chaque élément dans sa position
correcte dans la partie triée.

• Très efficace pour de petites listes ou pour

des listes presque triées.

44
 Propriété des algorithmes de tris
• Tri par bulles :
• Compare des paires d’éléments adjacents
et les échange si nécessaire, jusqu'à ce
que la liste soit triée.

• Simple mais inefficace pour de grands

ensembles de données.

45
 Propriété des algorithmes de tris
• Tri par rapide :
• Divise et conquiert : partitionne les
données autour d’un pivot, puis trie
récursivement les sous-tableaux.

• Très rapide en pratique, mais sensible à la

sélection du pivot.

46
 Propriété des algorithmes de tris
• Tri par fusion :
• Divise et conquiert : divise les données en
sous-tableaux, les trie récursivement, puis
les fusionne.

• Très efficace pour les grands ensembles

de données, mais nécessite un espace
supplémentaire.

47
 Choix d’un algorithme
• Le choix d’un algorithme de tri dépend des critères suivants :
• Taille des données :
– Petites tailles : tri par insertion ou tri à bulles.
– Grandes tailles : tri rapide ou tri par fusion.
• Stabilité requise :
– Stable : tri par insertion ou tri par fusion.
– Non stable : tri rapide ou tri par sélection.
• Espace mémoire disponible :
– Si l’espace est limité : tri rapide ou tri par sélection (in-place).
• Nature des données :
– Données presque triées : tri par insertion ou tri à bulles.
– Données non structurées : tri rapide ou tri par fusion.

48