CPGE - AGADIR MP-PSI-TSI

MTHODES DE TRIS

M.Gueroihi
1
DEFINITION
Un algorithme de tri est, en informatique ou en
mathmatiques, est un algorithme qui permet
d'organiser une collection d'objets selon un ordre
dtermin. Les objets trier font donc partie d'un
ensemble muni d'une relation d'ordre. Les ordres
les plus utiliss sont lordre numrique et l'ordre
lexicographique.

Source : Wikipdia

2
 I- TRI A BULLES

Principe :
Comparaison 2 2 des lments adjacents
et change s'ils ne sont pas ordonns. Le
programme s'arrte lorsqu'on parcourt la liste
sans faire d'change
Comme les bulles, les plus grands lments
remontent en fin de liste

3
 I- TRI A BULLES
def triBulles (T):
echange = True
while echange == True :
echange = False
for i in range(0,len(T)-1) :
if(T[i]> T[i+1]):
T[i],T[i+1]=T[i+1],T[i]
echange = True

Complexit : O(n2)
4
 II- TRI PAR SLECTION
Principe :
Recherche du plus petit lment du tableau et change
avec le premier lment
Recherche du plus petit lment du tableau entre les
positions 2 et n-1 et change avec le second lment
...

Recherche du plus petit lment entre les positions n-2 et n-1

et change avec lment en position n-2

5
 II- TRI PAR SLECTION
def triSelection (T):
for i in range(0,len(T)-1):
pmin= i
for j in range (i+1, len(T)):
if T[j] < T [pmin]:
pmin= j
if pmin!= i:
T[i],T [pmin] = T[pmin], T[i]

Complexit : O(n2)
6
 III- TRI PAR INSERTION :

Principe :
La liste tant trie jusqu' l'lment i-1,
insrer l'lment i sa place parmi les i
premiers lments

7
III- TRI PAR INSERTION :
def tri_Insertion(T) :
n=len(T)
for i in range(1,n):
v = T[i]
j = i
while j>0 and T[j-1]> V :
T[j]= T[j-1]
j = j-1
T[j]= v

Complexit : O(n2)
8
 IV- TRI RAPIDE
QUICK SORT

Le tri rapide (en anglais quick sort) est un

algorithme de tri invent par C.A.R. Hoare en
1961 et fond sur la mthode de conception
diviser pour rgner.
Son principe consiste sparer lensemble des
lments en deux parties.

9
 IV- TRI RAPIDE
Principe :

L'algorithme peut seffectuer rcursivement:

une valeur pivot est choisie au hasard. (peut aussi tre
le premier ou le dernier lment de la liste trier).
On cre un premier sous-ensemble constitu des
lments plus petits que le pivot. On les place gauche
du pivot.
On cre de la mme faon un deuxime sous-ensemble
constitu des lments plus grands que le pivot. On les
place droite de celui-ci.
On procde de mme, par rcursivit, sur les deux sous-
ensembles jusqu obtenir des sous ensembles d'un
seul lment.
10
 IV- TRI RAPIDE
Exemple1 :

11
 IV- TRI RAPIDE

Exemple 2 :

Soit la liste : L = [ 4, 23, 3, 42, 2, 14, 45, 18, 38, 16 ]

Prenons comme pivot la dernire valeur
pivot = 16
Nous obtenons donc :
L1 = [4, 14, 3, 2]
L2 = [23, 45, 18, 38, 42]
A cette tape voici l'arrangement de L :
L = L1 + [pivot] + L2 = [4, 14, 3, 2, 16, 23, 45, 18, 38, 42]

12
 IV- TRI RAPIDE

En appliquant la mme dmarche au deux sous-

listes : L1 (pivot=2) et L2 (pivot=42)
[4, 14, 3, 2, 16, 23, 45, 18, 38, 42]
nous obtenons :
L11=[ ] liste vide L21=[23, 38, 18]
L12=[3, 4, 14] L22=[45]
L1=L11 + pivot + L12 = (2,3, 4, 14) L2=L21 + pivot + L22 = (23, 38, 18, 42, 45)

13
 TRI PRAPIDE PYTHON-
SOLUTION 1
def Trirapide(L):
if L==[]: return[]
#on va balayer la liste L et repartir les valeurs
n=len(L)
L1=[]
L2=[]
pivot=L[0] #ici on a pris le premier lment comme pivot.
for k in range(1,n):
if L[k]<= pivot:
#L1 reoit les lments plus petits
L1.append(L[k])
else:
#L2 reoit les lments plus grands
L2.append(L[k])
L = Trirapide(L1) + [pivot] + Trirapide(L2)
return L
14
 TRI PRAPIDE PYTHON-
SOLUTION 2
Pour implmenter l'algorithme tri rapide on a besoin de programmer trois
fonctions:

1. La fonction :
partitionner(T, premier, dernier) prend le tableau T et deux
indices premier et dernier en arguments, (avec premier et dernier inclus).
On suppose qu'il y a au moins un lment dans ce segment,

2. La fonction :
tri_Rapide_Partition(T,premier,dernier): qui permet de
trier le tableau T en le partitionnant rcursivement en sous-tableaux.

3. La fonction :
triRapide(T) permettant de trier le tableau T en utilisant la fonction
tri_Rapide_Partition.

15
 TRI PRAPIDE PYTHON-
SOLUTION 2
1. La fonction :
partitionner(T, premier, dernier) prend le tableau T et deux
indices premier et dernier qui permet de partitionner le tableau T en 2 parties et
positionne le pivot sa position dfinitive et retourne son indice.

def partitionner(T, premier, dernier):

#on prend le dernier lment comme pivot.
pivot = T[dernier]
j = premier
for i in range(premier, dernier) :
if T[i]<=pivot :
T[i],T[j]=T[j],T[i]
j=j+1
T[dernier],T[j]=T[j],T[dernier]
return j #position dfinitive du pivot 16
 TRI PRAPIDE PYTHON-
SOLUTION 2
2. La fonction :
tri_Rapide_Partition(T,premier,dernier): qui permet de trier le
tableau T en le partitionnant rcursivement en sous-tableaux.

def tri_Rapide_Partition (T, premier, dernier):

if premier < dernier :
#dterminer la position dun pivot
p=partitionner(T, premier, dernier)

#Trier le sous-Tableau gauche

tri_Rapide_Partition(T, premier, p-1)

#Trier le sous-Tableau droit

tri_Rapide_Partition(T, p+1, dernier)

17
 TRI PRAPIDE PYTHON-
SOLUTION 2
3. La fonction :
triRapide(T) permettant de trier le tableau T en appelant la fonction
tri_Rapide_Partition.

def triRapide(T):
tri_Rapide_Partition( T, 0, len(T) -1 )

Appel.

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

>>> triRapide(L)
>>> L
[2, 3, 4, 4, 14, 16, 18, 23, 38, 42, 45]

18
 TRI PRAPIDE
COMPLEXIT
La fonction partitionner fait toujours exactement dernier premier- 1
comparaisons.
Si La fonction partitionner dtermine un segment de longueur K et un autre
de longueur N-1-k, la fonction tri_ Rapide_Partition va donc effectuer N- 1
comparaisons par l'intermdiaire de partitionner, puis d'autres
comparaisons par l'intermdiaire des deux appels rcursifs la fonction
tri_Rapide_Partition
Le pire des cas correspond K=0 (c'est dire quand une des parties est
vide et l'autre contient n-1), ce qui donne, en notant C(N) la complexit du
tri d'un tableau de longueur N, l'quation de rcurrence suivante:
C(N)= N-1+ C(N-1)
Donc C(N)= N2/2 , d'o la complexit est O(N2)
Le meilleur des cas correspond un segment coup en deux moitis
gales, c'est--dire K = N/2. L'quation de rcurrence devient alors:
C(N)= N-1+2.C(N/2)
On dduit que C(N)= N.log(N), donc la complexit est O(N.log(N))
19
 V- TRI PAR FUSION

Principe :
Le tri par fusion est un
algorithme de tri bas sur la
technique algorithmique
diviser pour rgner.
L'opration principale de
l'algorithme est la fusion, qui
consiste runir deux listes
tries en une seule.

20
 V- TRI PAR FUSION
Principe :
Le principe de cet algorithme tend adopter une formulation
rcursive :

On dcoupe les donnes trier en deux parties plus ou moins

gales

On trie les 2 sous-parties ainsi dtermines

On fusionne les deux sous-parties pour retrouver les donnes de

dpart

21
V- TRI PAR FUSION
Exemple:

22
 V- TRI PAR FUSION
Implmentation :

L'implmentation de cet algorithme repose

essentiellement en 2 fonctions :

Fusion :Permet de fusionner deux listes tries

de telle sorte que la liste rsultante la soit aussi.

triFusion: Une fonction rcursive qui assure le

dcoupage de la liste et l'appel de la fonction de
fusion.

23
 V- TRI PAR FUSION
Fonction Fusion :

def fusion(L1, L2):

res = [ ]
i, j= 0, 0
while i< len(L1) and j< len(L2):
if L1[i] <= L2[j]:
res.append(L1[i])
i += 1
else:
res.append(L2[j])
j += 1
if i!=len(L1): res+=L1[i:]
if j!=len(L2): res+=L2[j:]
return res
24
 V- TRI PAR FUSION
Fonction triFusion :

def triFusion(L):
if len(L) <= 1: return L
m = len(L) // 2
return fusion( triFusion(L[:m]),
triFusion(L[m:]))

Appel.

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

>>> triFusion(L)
[2, 3, 4, 4, 14, 16, 18, 23, 38, 42, 45]

25
 V- TRI PAR FUSION
COMPLEXIT
Si on note :
C(N) : le nombre total de comparaisons effectues par la fonction triFusion
f (N) : le nombre total de comparaisons effectues par la fonction Fusion
Pour trier un tableau de longueur N, on a lquation de rcurrence suivante:
C(N)=2.C(N/2)+ f (N)
Les deux appels rcursifs se font sur deux segments de mme longueur N/2
Dans le meilleur des cas, la fonction Fusion n'examine que les lments de l'un
des deux segments car ils sont tous plus petits que ceux de l'autre segment.
Dans ce cas f (N)= N/2, donc C(N)= ().N.log(N) , d'o la complexit est :
O(N.log(N))

Dans le pire des cas, tous les lments sont examins par la fonction Fusion
Dans ce cas f (N)= N-1,
donc C(N)= N.log(N). D'o la complexit est :
O(N.log(N))
26
COMPARAISON DE COMPLEXIT DE
DIFFRENTES METHODES DE TRIS

27