AFB: Algorithmique

Les algorithmes de tri

:Réalisé par :Encadré par

ZARGANE Chahrazad
EL GHAOUAL Ibtissam Dr. HRICH Najoua
 Les objectifs visées
● Comprendre le principe et l’utilité de tri
● Connaitre le fonctionnement de chaque algorithme
● Savoir la complexité de chaque algorithme de tri
 Pourquoi a-t-on besoin de trier ?
Les algorithmes de tri ont de nombreuses utilités et leur étude est un sujet majeur de
recherche en informatique.
 Utilité
Certains des meilleurs exemples de mise en œuvre dans le monde réel de la même
chose sont :
Le tri à bulles est utilisé dans la programmation TV pour trier les chaînes en fonction
du temps d'écoute de l'audience !
Les bases de données utilisent le tri par fusion externe pour trier des ensembles de
données trop volumineux pour être entièrement chargés en mémoire !
Les scores sportifs sont rapidement organisés par un algorithme de tri rapide en temps
réel !!
 Utilité
trier à l'avance une structure de données comme un tableau peut accélérer une
opération de recherche. De plus, il est nécessaire que certains algorithmes fonctionnent,
par exemple, la recherche binaire ne fonctionne que sur des données triées.
 Utilité
A l'école, les enfants d'une classe sont triés par ordre croissant de taille en faisant la
queue pour l'assemblée du matin. De même, le registre de présence présente les noms
des enfants classés par ordre alphabétique. Les annuaires téléphoniques ont également
les numéros de contact triés par nom de propriétaire par ordre alphabétique. Les
données triées sont préférées aux données non triées car elles sont plus faciles à
manipuler et à rechercher.
Une petite quantité de données, une classe de 60 à l'école, peut être triée
manuellement, mais les grandes données, par exemple, les données des employés dans
une grande entreprise ne peuvent pas être triées manuellement. 
 Utilité
Certains algorithmes comme l'algorithme de Prim, l'algorithme de Kruskal,
l'algorithme de dijkstra nécessitent que les données soient déjà triées avant de pouvoir
être appliquées.
Nous avons une variété d'algorithmes de tri allant du tri à bulles, du tri par sélection,
du tri par fusion, du tri rapide etc. Chacun d'eux a son propre ensemble de faiblesses et
de forces, sur la base desquelles ils peuvent être utilisés par les développeurs.
 Qu’est-ce qu’un algorithme de tri ?
On désigne par "tri" l'opération consistant à ordonner un ensemble d'éléments en
fonction de clés sur lesquelles est définie une relation d'ordre.

Un algorithme de tri est une suite finie d’opérations permettant d’organiser des

éléments dans un ordre déterminé préalablement. Le plus souvent, les informaticiens
trient des tableaux d’entiers du plus petit au plus grand.
01 Le tri à bulle 04 Le tri par fusion

02 Le tri par sélection 05 Le tri rapide

03 Le tri par insertion

11
Le tri à bulle

Le tri par sélection

Le tri par insertion

Le Tri par fusion
Le tri rapide

12
 L'algorithme parcourt la liste,
• et compare les couples d'éléments successifs.
• Lorsque deux éléments successifs ne sont pas dans l'ordre croissant, ils
sont échangés.
• Après chaque parcours complet de la liste, l'algorithme recommence
l'opération.
• Lorsqu'aucun échange n'a lieu pendant un parcours, cela signifie que la
liste est triée :
• l'algorithme peut s'arrêter.
13
 TRI A BULLES
Simulation

0 1 2 3 4
48 17 25 9 34

Etape 1 : On se positionne dans la première case 48 > 17  On

permute

0 1 2 3 4
17 48 25 9 34
 TRI A BULLES
Simulation

0 1 2 3 4
17 48 25 9 34

Etape 2 : On se positionne dans la deuxième case 48 > 25  On

permute

0 1 2 3 4
17 25 48 9 34
 TRI A BULLES
Simulation

0 1 2 3 4
17 25 48 9 34

Etape 3 : On se positionne dans la 3eme case 48 > 9  On permute

0 1 2 3 4
17 25 9 48 34
 TRI A BULLES
Simulation

0 1 2 3 4
17 25 9 48 34

Etape 4 : On se positionne dans la 4eme case 48 > 34  On permute

0 1 2 3 4
17 25 9 34 48
 0 1 2 3 4
17 25 9 34 48

0 1 2 3 4
17 9 25 34 48

0 1 2 3 4
9 17 25 34 48
18
Application
Algorithme tri_bulles 
Variables i,n: entier
   permut :booléen
Tableau t[200]:entier
Début
Faire
Permut=faux
pour i0 A n-2 faire
si (t[i]>t[i+1]) alors
échanger t[i] et t[i+1]
permut=vrai
finsi
finpour
Tanque (Permut=vrai)
Fin
 Complexité du tri par sélection

Dans le pire des cas

21
Le tri à bulle

Le tri par sélection

Le tri par insertion

Le Tri par fusion
Le tri rapide

22
Le tri par sélection (ou tri par extraction) est un des algorithmes de tri les
plus triviaux.
Il consiste en la recherche soit du plus grand élément (ou le plus petit)
que l'on va replacer à sa position finale c'est-à-dire en dernière position
(ou en première), puis on recherche le second plus grand élément (ou le
second plus petit) que l'on va replacer également à sa position finale c'est-
à-dire en avant-dernière position (ou en seconde), etc., jusqu'à ce que le
tableau soit entièrement trié.
23
 TRI PAR SELECTION
Simulation

0 1 2 3 4
9 4 1 7 3

Itération Min=1 On échange T[0] avec

1 imin=2 T[2]

0 1 2 3 4
1 4 9 7 3
 TRI PAR SELECTION
Simulation

0 1 2 3 4
1 4 9 7 3

Itération Min=3 On échange T[1] avec

2 imin=4 T[4]

0 1 2 3 4
1 3 9 7 4
 TRI PAR SELECTION
Simulation

0 1 2 3 4
1 3 9 7 4

Itération Min=4 On échange T[2] avec

3 imin=4 T[4]

0 1 2 3 4
1 3 4 7 9
 TRI PAR SELECTION
Simulation

0 1 2 3 4
1 3 4 7 9

Itération Min=7 On garde l’élément a sa

4 imin=3 place

0 1 2 3 4
1 3 4 7 9
Application
TRI PAR SELECTION
Algorithme tri-selection
Variable: i, j, min, temp, n : entiers
Tableau tab[200] :entier
Début
Pour i  0 a n-2 faire
min i

pour j i+1 a n-1 faire

si (tab[j]<tab[min]) alors Cette boucle cherche l’indice du
minimum
min j
finsi
finpour

temp  tab[min]
Permutation
tab[min]  tab[i]
tab[i]  temp
Fin pour
fin
Complexité du tri par sélection

29
Le tri à bulle

Le tri par sélection

Le tri par insertion

Le Tri par fusion
Le tri rapide

30
Le tri par insertion consiste à parcourir la liste:
on prend les éléments dans l'ordre.
Ensuite, on les compare avec les éléments précédents jusqu'à trouver la
place de l'élément qu'on considère.
Il ne reste plus qu'à décaler les éléments du tableau pour insérer l'élément
considéré à sa place dans la partie déjà triée.

31
 TRI PAR INSERTION

Principe

Ordonner les deux premiers éléments

• Insérer le 3e élément de manière a ce que les 3 premiers
éléments soient tries
• Insérer le 4e élément a sa place pour que. . .
•...
• Insérer le ne élément a sa place.
A la fin de la ie itération, les i premiers éléments de T sont
tries et ranges au début du tableau T′
 TRI PAR INSERTION

i 1 2 3 4 5
T[i] 96 69 1 4 8

9 > 6 donc je décale vers la

tmp 6 droite

 Déclarer une variable tmp

 Se positionner dans la deuxième case de
tableau
Je suis arrive au début du
 Stocke la valeur de cette deuxieme case dans la
tableau donc je place mon
variable tmp puis Comparer les valeurs qui sont
élément
a sa gauche dans ce exemple on a la valeur 9
 TRI PAR INSERTION

i 1 2 3 4 5
T[i] 61 96 19 4 8

9 > 1 donc je décale vers la

tmp 1 droite
6 > 1 donc je décale vers la
droite

Je suis arrive au début du

tableau donc je place mon
élément
 TRI PAR INSERTION

i 1 2 3 4 5
T[i] 1 46 6
9 49 8

9 > 4 donc je décale vers la

tmp 4 droite
6 > 1 donc je décale vers la
droite
1 <4 donc j’insère l’élément
dans la case vide
 TRI PAR INSERTION

i 1 2 3 4 5
T[i] 1 4 6 98 89

9 > 8 donc je décale vers la

tmp 8 droite
6 < 8 donc j’insère l’élément
dans la case vide
Application
Algorithme tri_insertion
Variables i, j, n, tmp: entiers;
Tableau tab[200]:entiers
Pour i  1 a n-1 faire
Tmp  tab[i]
ji
Tanque (j>0) et (tab[j-1]>tmp) faire
tab[j]  t[j-1]
j  j-1
FinTanque
tab[j]  tmp
Finpour 37
 Complexité du tri par insertion

Dans le pire des cas

38
Le tri à bulle

Le tri par sélection

Le tri par insertion

Le Tri par fusion
Le tri rapide

39
 Diviser
Découper un problème initial en sous- problèmes

Régner
Résoudre les sous-problèmes(récursivement ou directement s’ils sont
assez petits)
Combiner
40
Trouver une solution au problème initial à partir des solutions des sous-problèmes
Le tri fusion est construit suivant la stratégie "diviser pour régner",
pour résoudre un gros problème, il est souvent plus facile de le diviser en
petits problèmes élémentaires.
Une fois chaque petit problème résolu, il n’y a plus qu’à combiner les
différentes solutions pour résoudre le problème global.
La méthode "diviser pour régner" 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,
41
 puis de fusionner les résultats.
L’algorithme proposé ici est récursif. En effet, les deux sous tableaux
seront eux même triés à l’aide de l’algorithme de tri fusion.
Un tableau ne comportant qu’un seul élément sera considéré comme trié
Étapes de l’algorithme :

Division de l’ensemble de valeurs en deux parties

 Tri de chacun des deux ensembles
 Fusion des deux ensembles
42
 Analyse

Étant donné un tableau de T[1,…n]

Si n= 1, retourner le tableau T!
Entrée: sinon:
Tableau de Trier le sous-tableau[1,…n/2] Sortie:
taille n Trier le sous-tableau[(n/2)+1,…n] Tableau trié
Fusionner ces deux sous-tableaux.

43
Procedure triFusion(Tableau T[], n:Entier;)
si n ≤ 1 retourne T;
sinon fusion(triFusion(T[1, …, n/2]), triFusion(T[n/2 + 1, …, n]))
fin si
Fin Procedure

44
Void fusion(int *t, int deb1, int fin1, int fin2)
int *table1;
int deb2=fin1+1;
int compt1=deb1;
int compt2=deb2;
int i;table1=(Int *)malloc((fin1-deb1+1)*sizeof(int ));
for (i=deb1;i<=fin1;i++) table1[i-deb1]=t[i];//met le t dans table1
for (i=deb1;i<=fin2;i++){
if (compt1==deb2) • break;
else If (compt2==(fin2+1)) {
t[i]=table1[compt1-deb1];compt1++;}
else if(table1[compt1-deb1] <t[compt2])){t[i]=table1[compt1-deb1];compt1++;}
else{t[i]=t[compt2];compt2++;}}
free(table1);}

45
Le tri à bulle

Le tri par sélection

Le tri par insertion

Le Tri par fusion
Le tri rapide

46
 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 lui sont
inférieurs soient à sa gauche et que tous ceux qui lui sont supérieurs
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é. 47
procedure triRapide(tableau tab[1:N], N:entier;)
triRapideR(tab, 0, N-1);
fin procedure
procedure triRapideR(tableau tab[1:n], debut, fin:entier;)
Variable:
pivot :entier;
si (debut<fin) alors
pivot partition(tab, debut, fin);
triRapideR(tab, debut, pivot - 1);
triRapideR(tab, pivot + 1, fin);
fin si
fin procedure

48
fonction partition(tableau tab[1:n], debut, fin:entier;):entier
variable:
compt, pivot, i:entier;
pour (i de debut+1 à fin en incrémentant de 1) faire
si (tab[i] < pivot)alors
comptcompt+1;
tab[i] <- tab[k+1];
echanger(t,compt,i); fin si
fin pour
echanger(t,compt,deutb);
retourner compt;
fin fonction

49
Complexité des algorithmes

50
La complexité temporelle est le temps requis par l'algorithme pour
s'exécuter en fonction de la taille de l'entrée. De même, la complexité de
l'espace fait référence à la quantité d'espace requise par l'algorithme pour
s'exécuter en fonction de la taille de l'entrée.

51
52
Temps d’Exécution / tailles des données

53
Nous avons vu que de nombreux algorithmes permettent de trier un
tableau. Cependant, certains sont plus efficaces que d’autres, car leur
complexité est plus faible.
Sur des petits tableaux, la différence est minime, mais lorsque ceux-ci
possèdent plusieurs millions d’éléments, il devient indispensable de choisir
un algorithme ayant une complexité minimale. 🧐

54