Introduction aux algorithmes de tri
Eugène C. Ezin
1 Enseignant-Chercheur
Université d’Abomey-Calavi.
Eugène C. Ezin (Université d’Abomey-Calavi) Introduction aux algorithmes de tri 1 / 29
Définition de tri
Un algorithme de tri est, en informatique est un algorithme qui
permet d’organiser une collection d’objets selon une relation d’ordre
déterminée.
Les objets à trier sont des éléments d’un ensemble muni d’un ordre
total.
Les algorithmes de tri sont utilisés dans de très nombreuses situations.
Les algorithmes de tri sont en particulier utiles à de nombreux
algorithmes plus complexes dont certains algorithmes de recherche,
comme la recherche par dichotomie.
Eugène C. Ezin (Université d’Abomey-Calavi) Introduction aux algorithmes de tri 2 / 29
Différents algorithmes de tri
Il existe plusieurs algorithmes de tri qu’on peut classer en deux catégories:
les algorithmes de tri lents;
les algorithmes de troi rapides.
C’est la notion de complexité que nous n’évoquerons pas en détail qui
permet de classifier les catégories en terme de lent et de rapide.
Retenons simplement
La complexité en temps d’un algorithme désigne le nombre d’opérations
élémentaires qui sont effectuées par cet algorithme.
Eugène C. Ezin (Université d’Abomey-Calavi) Introduction aux algorithmes de tri 3 / 29
Les algorithmes de tri lent
On peut citer:
le tri à bulles;
le tri par sélection;
le tri par insertion;
etc.
Nous présenterons seulement le tri à bulles dans la suite de cette
présentation.
Eugène C. Ezin (Université d’Abomey-Calavi) Introduction aux algorithmes de tri 4 / 29
Tri à bulles
Le principe du tri à bulles est le suivant:
L’algorithme du tri à bulles parcourt le tableau et compare les
éléments consécutifs. Lorsque deux éléments consécutifs ne sont pas
dans l’ordre, ils sont échangés.
Après un premier parcours complet du tableau, le plus grand élément
est forcément se trouve à la fin du tableau.
Le reste du tableau est en revanche encore en désordre. On le
parcourt à nouveau avec le même principe 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.
Ce processus est répété sur les différents sous-tableaux jusqu’à ce que
les deux plus petits éléments soient placés à leur position définitive.
Eugène C. Ezin (Université d’Abomey-Calavi) Introduction aux algorithmes de tri 5 / 29
Exercice d’application
Enoncé
Soit à trier par ordre croissant le tableau composé d’entiers composé des
huits éléments suivants:
10, 8, 6, 14, 9, 12, 5, 2 avec la méthode du tri à bulles.
Eugène C. Ezin (Université d’Abomey-Calavi) Introduction aux algorithmes de tri 6 / 29
Première étape
10 8 6 14 9 12 5 2
Eugène C. Ezin (Université d’Abomey-Calavi) Introduction aux algorithmes de tri 7 / 29
Première étape
10 8 6 14 9 12 5 2
8 10 6 14 9 12 5 2
Eugène C. Ezin (Université d’Abomey-Calavi) Introduction aux algorithmes de tri 7 / 29
Première étape
10 8 6 14 9 12 5 2
8 10 6 14 9 12 5 2
8 6 10 14 9 12 5 2
Eugène C. Ezin (Université d’Abomey-Calavi) Introduction aux algorithmes de tri 7 / 29
Première étape
10 8 6 14 9 12 5 2
8 10 6 14 9 12 5 2
8 6 10 14 9 12 5 2
8 6 10 9 14 12 5 2
Eugène C. Ezin (Université d’Abomey-Calavi) Introduction aux algorithmes de tri 7 / 29
Première étape
10 8 6 14 9 12 5 2
8 10 6 14 9 12 5 2
8 6 10 14 9 12 5 2
8 6 10 9 14 12 5 2
8 6 10 9 12 14 5 2
Eugène C. Ezin (Université d’Abomey-Calavi) Introduction aux algorithmes de tri 7 / 29
Première étape
10 8 6 14 9 12 5 2
8 10 6 14 9 12 5 2
8 6 10 14 9 12 5 2
8 6 10 9 14 12 5 2
8 6 10 9 12 14 5 2
8 6 10 9 12 5 14 2
Eugène C. Ezin (Université d’Abomey-Calavi) Introduction aux algorithmes de tri 7 / 29
Première étape
10 8 6 14 9 12 5 2
8 10 6 14 9 12 5 2
8 6 10 14 9 12 5 2
8 6 10 9 14 12 5 2
8 6 10 9 12 14 5 2
8 6 10 9 12 5 14 2
8 6 10 9 12 5 2 14
Eugène C. Ezin (Université d’Abomey-Calavi) Introduction aux algorithmes de tri 7 / 29
Deuxième étape
8 6 10 9 12 5 2 14
6 8 10 9 12 5 2 14
6 8 10 9 12 5 2 14
6 8 9 10 12 5 2 14
6 8 9 10 12 5 2 14
6 8 9 10 5 12 2 14
6 8 9 10 5 2 12 14
Eugène C. Ezin (Université d’Abomey-Calavi) Introduction aux algorithmes de tri 8 / 29
Troisième étape
6 8 9 10 5 2 12 14
6 8 9 5 10 2 12 14
6 8 9 5 2 10 12 14
Eugène C. Ezin (Université d’Abomey-Calavi) Introduction aux algorithmes de tri 9 / 29
Quatrième étape
6 8 9 5 2 10 12 14
6 8 5 9 2 10 12 14
6 8 5 2 9 10 12 14
Eugène C. Ezin (Université d’Abomey-Calavi) Introduction aux algorithmes de tri 10 / 29
Cinquième étape
6 8 5 2 9 10 12 14
6 5 8 2 9 10 12 14
6 5 2 8 9 10 12 14
Eugène C. Ezin (Université d’Abomey-Calavi) Introduction aux algorithmes de tri 11 / 29
Sixième étape
5 6 2 8 9 10 12 14
5 2 6 8 9 10 12 14
5 2 6 8 9 10 12 14
Eugène C. Ezin (Université d’Abomey-Calavi) Introduction aux algorithmes de tri 12 / 29
Septième étape
2 5 6 8 9 10 12 14
Le tableau est donc trié!
Eugène C. Ezin (Université d’Abomey-Calavi) Introduction aux algorithmes de tri 13 / 29
Algorithme de tri à bulles
La définition de la fonction de tri a bulles() se présente comme suit:
Fonction de tri à bulles
Fonction tri a bulles(Tableau T : Entier ) Retourne Vide
Variables : i, j : Entier;
Debut
Repeter ∀i ∈ [Taille − 1, 1]
Repeter ∀j ∈ [0, i − 1]
Si (T [j + 1] < T [j]) Alors
echange(T [j + 1], T [j]);
FinSi
Fin
Remarquons qu’il existe d’autres variantes de l’algorithme du tri à bulles
par exemple le tri cocktail ou tri shaker, le tri à peigne ou combsort.
Eugène C. Ezin (Université d’Abomey-Calavi) Introduction aux algorithmes de tri 14 / 29
Algorithme de tri à bulles (suite et fin)
La définition de la fonction echanger() se présente comme suit:
Fonction de tri à bulles
Fonction echange(Entier a, Entier b) Retourne Vide
Variables:tmp: Entier;
Debut
Si (a < b)
tmp ←− a;
a ←− b;
b ←− tmp;
FinSi
Fin
Eugène C. Ezin (Université d’Abomey-Calavi) Introduction aux algorithmes de tri 15 / 29
Les algorithmes de tri rapide
On peut citer:
le tri par dichotomie;
le tri par fusion;
le tri rapide;
etc.
Nous allons présenter par la suite le tri rapide.
Eugène C. Ezin (Université d’Abomey-Calavi) Introduction aux algorithmes de tri 16 / 29
Principe du tri rapide
La méthode consiste à placer un élément du tableau (appelé pivot) à
sa place définitive, en permutant tous les éléments de telle sorte que
tous ceux qui sont inférieurs au pivot soient à sa gauche et que tous
ceux qui sont supérieurs au pivot soient à sa droite.
Cette opération s’appelle le partitionnement.
Pour chacun des sous-tableaux, on définit un nouveau pivot et on
répète l’opération de partitionnement. Ce processus est répété
récursivement, jusqu’à ce que l’ensemble des éléments soit trié.
Eugène C. Ezin (Université d’Abomey-Calavi) Introduction aux algorithmes de tri 17 / 29
Pratiquement
Concrètement, pour partitionner un sous-tableau :
le pivot est placé à la fin (arbitrairement), en l’échangeant avec le
dernier élément du sous-tableau ;
tous les éléments inférieurs au pivot sont placés en début du
sous-tableau ;
le pivot est déplacé à la fin des éléments déplacés.
Eugène C. Ezin (Université d’Abomey-Calavi) Introduction aux algorithmes de tri 18 / 29
Exercice d’application
Enoncé
Soit à trier par ordre croissant le tableau composé d’entiers composé des
huits éléments suivants:
10, 8, 6, 14, 9, 12, 5, 2 avec la méthode du tri rapide.
Eugène C. Ezin (Université d’Abomey-Calavi) Introduction aux algorithmes de tri 19 / 29
Exercice d’application
Enoncé
Soit à trier par ordre croissant le tableau composé d’entiers composé des
huits éléments suivants:
10, 8, 6, 14, 9, 12, 5, 2 avec la méthode du tri rapide.
Eugène C. Ezin (Université d’Abomey-Calavi) Introduction aux algorithmes de tri 20 / 29
Première étape
En choisissant l’entier 8 comme pivot, on obtient:
6 5 2 8 9 10 14 12
Tous les éléments inférieurs sont placés avant 8 et tous les éléments
plus grands après 8.
Eugène C. Ezin (Université d’Abomey-Calavi) Introduction aux algorithmes de tri 21 / 29
Deuxième étape
On considère chaque sous-tableau et on considère le pivot comme
étant le premier élément à permuter avec le dernier élément.
La position du pivot ne sera pas changé.
On applique le même principe de positionnement des éléments par
rapport au pivot: tous les éléments plus petits avant le pivot et tous
les éléments plus grands après le pivot.
2 5 6 8 12 10 14 9
Eugène C. Ezin (Université d’Abomey-Calavi) Introduction aux algorithmes de tri 22 / 29
Deuxième étape
On considère chaque sous-tableau et on considère le pivot comme
étant le premier élément à permuter avec le dernier élément.
La position du pivot ne sera pas changé.
On applique le même principe de positionnement des éléments par
rapport au pivot: tous les éléments plus petits avant le pivot et tous
les éléments plus grands après le pivot.
2 5 6 8 12 10 14 9
2 5 6 8 9 12 10 14
Tous les éléments inférieurs sont placés avant 6 et tous les éléments plus
grands après 8.
Eugène C. Ezin (Université d’Abomey-Calavi) Introduction aux algorithmes de tri 22 / 29
Troisième étape (suite et fin)
On considère chaque sous-tableau et on considère le pivot comme
étant le premier élément à permuter avec le dernier élément.
La position du pivot ne sera pas changé.
On applique le même principe de positionnement des éléments par
rapport au pivot: tous les éléments plus petits avant le pivot et tous
les éléments plus grands après le pivot.
5 2 6 8 9 14 10 12
Eugène C. Ezin (Université d’Abomey-Calavi) Introduction aux algorithmes de tri 23 / 29
Troisième étape (suite et fin)
On considère chaque sous-tableau et on considère le pivot comme
étant le premier élément à permuter avec le dernier élément.
La position du pivot ne sera pas changé.
On applique le même principe de positionnement des éléments par
rapport au pivot: tous les éléments plus petits avant le pivot et tous
les éléments plus grands après le pivot.
5 2 6 8 9 14 10 12
2 5 6 8 9 10 12 14
Eugène C. Ezin (Université d’Abomey-Calavi) Introduction aux algorithmes de tri 23 / 29
Troisième étape (suite et fin)
On considère chaque sous-tableau et on considère le pivot comme
étant le premier élément à permuter avec le dernier élément.
La position du pivot ne sera pas changé.
On applique le même principe de positionnement des éléments par
rapport au pivot: tous les éléments plus petits avant le pivot et tous
les éléments plus grands après le pivot.
5 2 6 8 9 14 10 12
2 5 6 8 9 10 12 14
Tous les éléments du tableau sont ainsi triés.
Eugène C. Ezin (Université d’Abomey-Calavi) Introduction aux algorithmes de tri 23 / 29
Présentation des fonctions de tri rapide
Il y a trois fonctions qui peuvent être mise en exergue à savoir:
partionner(). Cette fonction permet de faire le partionnement du
tableau.
echanger(). Elle est utiliser pour la permutation des éléments
notamment le pivot et le dernier élément du sous-tableau.
triRapide(). Cette fonction fait appel aux deux autres et à elle-meme
de façon résursive.
Eugène C. Ezin (Université d’Abomey-Calavi) Introduction aux algorithmes de tri 24 / 29
Présentation du partionnement
Fonction partitionner()
Fonction partitionner(Tableau T:Entier, Entier premier, Entier dernier, Entier
pivot) Retourne Entier
Variables: i, j: Entier;
Debut
echange (T[pivot], T[dernier]);
j ←− premier;
Repeter ∀i ∈ [premier , dernier − 1]
Si (T[i] ≤ T[j]) Alors
Debut
echange(T[i],T[j])
j ←− j+1;
Fin
FinSi
echange(T[dernier],T[j]);
Retourne j;
Fin
Eugène C. Ezin (Université d’Abomey-Calavi) Introduction aux algorithmes de tri 25 / 29
Présentation de l’échange
Fonction echange()
Fonction echange (a Entier, b Entier) Retourne Vide
Variable: tmp: Entier;
Debut
Si(a ≤ b) Alors
tmp ←− a;
a ←− b;
b ←− tmp;
FinSi
Fin
Eugène C. Ezin (Université d’Abomey-Calavi) Introduction aux algorithmes de tri 26 / 29
Présentation de la fonction du tri rapide
Fonction TriRapide()
Fonction triRapide (Tableau T, entier premier, entier dernier) Retourne
Vide
Variable:
; Debut
Si(premier ≤ dernier) Alors
pivot ←− choixPivot(T, premier, dernier);
pivot ←− partionner(T, premier, dernier, pivot);
pivot ←− triRapide(T, premier, pivot-1);
pivot ←− triRapide(T, pivot+1, dernier);
Finsi
Fin
Eugène C. Ezin (Université d’Abomey-Calavi) Introduction aux algorithmes de tri 27 / 29
Exercices
Utiliser le principe du tri rapide pour trier par ordre décroissant puis
par ordre croissant le tableau d’entiers composé de
6, 5, 2, 5, 9, 19, 3, 9, 1, 7.
Utiliser le principe du tri à bulles pour trier par ordre décroissant puis
par ordre croissant le tableau d’entiers composé de
6, 5, 2, 5, 9, 19, 3, 9, 1, 7.
Faites des recherches sur le tri dichotomique et le tri de fusion.
Appliquer ces algorithmes de tri sur le tableau précédent.
Eugène C. Ezin (Université d’Abomey-Calavi) Introduction aux algorithmes de tri 28 / 29
Conclusion
Merci pour votre attention.
Eugène C. Ezin (Université d’Abomey-Calavi) Introduction aux algorithmes de tri 29 / 29
