Universit Cadi Ayyad

Ecole Suprieure de Technologie

- Safi -

Programmation C & Structure de donnes

Cours N 3
(Tri & recherche)

Cours : SD 1 Pr. El Abdellaoui Sad

Tri
Trier un tableau est une opration algorithmique qui permet de ranger les lments
dun tableau en ordre croissant ou dcroissant.
Il existe plusieurs mthodes algorithmiques permettant de trier un tableau.

Exemple :
Tri itratif :
Tri par slection.
Tri bulles.
Tri par insertion.
Tri rcursif bas sur le principe diviser pour rgner
Tri par fusion.
Tri rapide

Cours : PC&SD 2 1
 Partie I

TRIS ITRATIF

Cours : PC&SD
6
 TRI PAR SLECTION

Cours : PC&SD
8
 TRI PAR SLECTION

Tri par slection :

Sur un tableau de n lments, le principe du tri par slection est le suivant :

rechercher le plus petit lment du tableau, et l'changer avec l'lment

d'indice 0 ;

rechercher le second plus petit lment du tableau, et l'changer avec

l'lment d'indice 1;

continuer de cette faon jusqu' ce que le tableau soit entirement tri.

Cours : PC&SD 5 1
 TRI PAR SLECTION
8 2 5 4 9 6 1 7

Permutation 1 : 2 8 5 4 9 6 1 7 1 2 4 6 9 8 5 7

Permutation 2 : 1 5 4 9 6 2 7 Permutation 9 : 1 2 4 5 9 8 6 7

Permutation 3 : 1 5 8 4 9 6 2 7 Permutation 10 : 1 2 4 5 8 9 6 7

Permutation 4 : 1 4 8 5 9 6 2 7 Permutation 11 : 1 2 4 5 6 9 8 7

Permutation 5 : 1 2 8 5 9 6 4 7 Permutation 12 : 1 2 4 5 6 8 9 7

Permutation 13 : 1 2 4 5 6 7 9 8
Permutation 6 : 1 2 5 8 9 6 4 7

1 2 4 8 9 6 5 7 Permutation 14 : 1 2 4 5 6 7 8 9
Permutation 7 :

Permutation 8 : 1 2 4 6 9 8 5 7

Cours : PC&SD 6 1
 TRI PAR SLECTION
La fonction se droule de la manire suivante:
- Le tableau est parcouru du premier lment (i=0) l'avant dernier (i=n-2).
- On compare l'lment i avec chaque lment j qui suit dans le tableau, cd de l'indice i+1 jusqu
l'indice n-1. Si l'lment d'indice j est plus petit que l'lment d'indice i alors on permute i et j.

Algorithme
fonction Trier_Selection (ELEMENT * t, ENTIER n):
i 0;
tant que (i < n - 1) faire
j i + 1;
tant que (j < n) faire
si ((t[j] < t[i])) alors
tmp t[j];
t[j] t[i];
t[i] tmp;
fin si;
j j + 1;
fin tant que;
i i + 1;
fin tant que;
fin fonction;

Cours : PC&SD 7 1
 TRI BULLE

Cours : PC&SD
12
 TRI BULLE
Le tri bulles (tri par propagation) est un algorithme de tri qui consiste faire remonter
progressivement les plus grands lments d'un tableau, comme les bulles d'air remontent la surface.
Le tri bulles a un principe simple mais avec une complexit, en moyenne, de l'ordre de n (o n
est la taille du tableau), ce qui le classe parmi les mauvais algorithmes de tri.

Cours : PC&SD 9 1
 TRI BULLE
8 2 5 4 9 6 1 7 2 5 4 8 6 1 7 9 2 4 5 6 1 7 8 9

22 88 55 44 99 66 11 77 2 5 4 8 6 1 7 9 2 4 5 6 1 7 8 9

2 5 8 4 9 6 1 7 2 4 5 8 6 1 7 9 2 4 5 6 1 7 8 9

2 5 4 8 9 6 1 7 2 4 5 8 6 1 7 9 2 4 5 6 1 7 8 9

2 5 4 8 9 6 1 7 2 4 5 6 8 1 7 9 2 4 5 1 6 7 8 9

2 5 4 8 6 9 1 7 2 4 5 6 1 8 7 9 2 4 5 1 6 7 8 9

2 5 4 8 6 1 9 7 2 4 5 6 1 7 8 9

2 5 4 8 6 1 7 9

1 2 4 5 6 7 8 9

Cours : PC&SD 10 1
 TRI BULLE

Algorithme
// version non optimise Lalgorithme parcourt le tableau et compare les
procdure Tri_Bulle (ELEMENT * t, ENTIER n): couples d lments successifs.
pour i allant de n-1 1 pas -1 faire
pour j allant de 0 i pas 1 faire Lorsque deux lments successifs ne sont pas
si (t[j] > t[j+1]) alors dans lordre croissant, ils sont changs.
tmp t[j]
t[j] t[j+1] Aprs chaque parcours complet du tableau,
t[j+1] tmp l'algorithme recommence l'opration.
fin si
fin pour
fin pour
fin procdure

Cours : PC&SD 11 1
 TRI BULLE
Algorithme
// version optimise
procdure Tri_Bulle_Opt (ELEMENT * t, ENTIER n):
i n-1 Aprs chaque parcours complet du tableau,
change vrai
tant que ((i>0) ET (change)) faire l'algorithme recommence l'opration.
change = faux Lorsqu'aucun change n'a lieu pendant un
pour j allant de 0 i-1 pas 1 faire
si (t[j] > t[j + 1]) alors parcours, cela signifie que le tableau est trie :
tmp t[j] l'algorithme peut s'arrter.
t[j] t[j+1]
t[j+1] tmp
change vrai
fin si
fin pour
ii-1
fin tant que
fin procdure

Cours : PC&SD 12 1
 TRI PAR INSERTION

Cours : PC&SD
17
 TRI PAR INSERTION
Le tri par insertion est un algorithme de tri classique, que la plupart des personnes utilisent
naturellement pour trier des cartes.
Il est considr comme le tri le plus efficace et rapide sur des entres de petite taille. Pour ces
raisons, il est utilis en pratique en combinaison avec d'autres mthodes comme le tri
rapide (ou Quicksort).

Algorithme
procdure Tri_Insertion (ELEMENT * t, ENTIER n):
pour i de 1 n-1
x T[i]
ji
tant que j > 0 et T[j - 1] > x
T[j] T[j - 1]
jj-1
fin tant que
T[j] x
fin pour
fin procdure

Cours : PC&SD 14 1
 Partie II

TRI RCURSIF

Cours : PC&SD
20
TRI RCURSIF

Lapproche diviser pour rgner est une technique pour la conception des algorithmes.

En effet, un algorithme bas sur cette approche suit 3 tapes :

1) Sparer le problme en plusieurs sous problmes semblables au problme

initial avec une taille inferieure,
2) Rsoudre les sous-problmes de faon rcursive,
3) Combiner toutes les solutions pour produire une solution.

Cours : PC&SD 16 1
 TRI PAR FUSION

Cours : PC&SD
20
TRI PAR FUSION

Principe : La mthode "diviser pour rgner" est tout fait applicable au problme de tri
plutt que de trier le tableau complet, il est prfrable de trier deux sous tableaux de taille
gale, puis de fusionner les rsultats. Lalgorithme propos ici est rcursif. En effet, les deux
sous tableaux seront eux mme tris laide de lalgorithme de tri fusion. Un tableau ne
comportant quun seul lment sera considr comme tri : cest la condition darrt.

Mthodes :
1) Diviser le tableau trier en deux sous-tableaux plus ou moins de mme taille,
2) Trier les deux sous-tableaux de manire rcursive en utilisant le tri fusion,
3) Fusionner les deux sous-tableaux tris pour avoir le tableau initial tri.

Cours : PC&SD 18 1
 TRI PAR FUSION
Illustration :

8 2 5 4 9 6 1 7

Diviser
8 2 5 4 9 6 1 7

8 2 5 4 9 6 1 7

8 2 5 4 9 6 1 7

2 8 4 5 6 9 1 7

Fusionner 2 4 5 8 1 6 7 9

1 2 4 5 6 7 8 9

Cours : PC&SD 19 1
 TRI RAPIDE

Cours : PC&SD
23
TRI RAPIDE

Principe : La mthode consiste placer un lment du tableau (appel pivot) sa place

dfinitive, en permutant tous les lments de telle sorte que tous ceux qui lui sont infrieurs
soient sa gauche et que tous ceux qui lui sont suprieurs soient sa droite. Cette opration
s'appelle le partitionnement. Pour chacun des sous tableaux, on dfinit un nouveau pivot et on
rpte l'opration de partitionnement. Ce processus est rpt rcursivement, jusqu' ce que
l'ensemble des lments soit tri.

Mthodes :
1) Partitionner le tableau trier en deux sous-tableaux o tous les lments du sous-
tableau gauche soient plus petits ou gaux un lment appel Blue qui est lui-
mme inferieur tous les lments de sous-tableau droit,
2) Trier les deux sous-tableaux de manire rcursive en utilisant le tri rapide.

Cours : PC&SD 21 1
 Partie III

RECHERCHE

Cours : PC&SD
25
 RECHERCHE SQUENTIELLE

Cours : PC&SD
26
 RECHERCHE SQUENTIELLE
La recherche linaire compare les diffrents lments d'un tableau la clef reherche.
Cette algorithme fonctionne bien pour les petits tableaux ou pour les tableaux non tris.
La recherche squentielle (sequential search en anglais) parcourt, case aprs case, les
n lments d'un tableau T et s'arrte au premier lment rencontr qui est gal
llment recherch. Dans ce cas l'information renvoye est la position (l'indice)
contenant l'lment recherch.

Algorithme Programme itratif Algorithme Programme rcursif

int RechSeqItr(int* t,int n,int v) int RechSeqRec(int* t, int n, int i, int v)

{ {
int i; if (i==n)
for (i=0; i<n; i++){ return -1;
if (t[i]==v) if (t[i]==v)
return i; return i;
return-1; return RechSeqRec(t, n, i+1, v);
} }
}

Cours : PC&SD 24 1
 RECHERCHE DICHOTOMIQUE

Cours : PC&SD
28
RECHERCHE DICHOTOMIQUE

La recherche dichotomie (binaire) n'est applicable que si le tableau a t tri auparavant

(croissant).
Cet algorithme commence par l'lment central et le compare la clef recherch.
Si les deux valeurs sont gales alors la valeur de l'indice est retourne.
Si l'lment recherch est infrieur, la recherche est poursuivie de manire
analogue dans la premire partie du tableau.
Sinon elle est suprieure et la recherche se poursuit dans seconde partie du
tableau.
La recherche continue jusqu' ce que la clef soit gale l'lment central d'un sous
tableau ou jusqu' ce que le sous tableau comporte un lment dont la valeur diffre de
celle de la clef de recherche c'est dire que la clef recherche n'a pas t trouve.

Cours : PC&SD 26 1
 RECHERCHE DICHOTOMIQUE
La recherche dans un tableau tri : on cherche 17

<9 9

Milieu

< 15 15

Milieu
15 19 > 19

Milieu
15 17

Milieu
Cours : PC&SD 27 1
RECHERCHE DICHOTOMIQUE

12

g Milieu d

12 19 23

g Milieu d

12 19 23

g Milieu d

12 17 19 23

g d

Milieu
Cours : PC&SD 28 1
 RECHERCHE DICHOTOMIQUE
La recherche dichotomique est une manire efficace et rapide de rechercher un
lment dans une structure de donnes trie.

Algorithme Itratif Algorithme Rcursif

int RechDicIter(int*t, int n, int v) int RechDicRec (int * t , int d ,int
{ f, int v)
int i, deb=0, fin=n-1; {
do int i;
{ i=(d+f)/2;
i=(deb+fin)/2; if(d>f)
if(t[i]==v) return-1;
return i; if(t[i]==v)
if(t[i]>v) return i;
fin=i-1; if(t[i]>v)
else deb=i+1; return RechDicRec(t,d,i-1,v);
} while(deb<=fin); return RechDicRec(t,i+1,f,v);
return-1; }
}

Cours : PC&SD 29 1
MINI PROJET
Le travail demand : Le mini projet tudie les diffrents algorithmes de tri savoir :

a) Le tri par slection ( vu en cours )

b) Le tri par insertion ( vu en cours )
c) Le tri bulle ( vu en cours )
d) Le tri rapide
e) Le tri par fusion

Le programme va se drouler comme suit :

1) La demande dentrer la taille du tableau par lutilisateur

2) Le remplissage du tableau.
3) Le choix entre les algorithmes de tri proposs gestion des erreurs-
4) Laffichage du tableau tri dans ordre croissant et dcroissant.

Remarques : - Travail par binme.

- A rendre le 8 mars (programme & word).
- Mail : elabdellaoui.said@yahoo.fr
Cours : PC&SD 30 1