CPGE ALQALAM-AGADIR MP-PSI
METHODES DE TRIS
1 - TRI A BULLES
❖ Principe :
Comparaison 2 à 2 des éléments adjacents et échange s'ils ne sont
pas ordonnés. Le programme s'arrête lorsqu'on parcourt la liste
sans faire d'échange
Comme les bulles, les plus grands éléments remontent en fin de liste.
❖ Programme :
T[i],T [pmin] = T[pmin], T[i]
def triBulles (T):
echange = True
n=len(T)
while echange == True :
echange = False
for i in range(0,n-1) :
if(T[i]> T[i+1]):
T[i],T[i+1]=T[i+1],T[i]
echange = True
n=n-1
2 - TRI PAR SELECTION
Complexité : O(N2)
❖ Principe :
∙Recherche du plus petit élément du tableau et écha
le premier élément
∙Recherche du plus petit élément du tableau entre le
et n -1 et échange avec le second élément
∙ ...
∙Recherche du plus petit élément entre les positions
et échange avec élément en position n-2
❖ Programme:
def triSelection (T):
for i in range(0,len(T)-1):
pmin= i Complexité : O(N2)
for j in range (i+1, len(T)
if T[j] < T [pmin]: pmin
Algorithmes de tri 1 /6 M.GUEROIHI
3 - TRI PAR INSERTION
❖ Principe : 4- TRI RAPIDE (QUICK SORT)
∙ La liste étant triée jusqu'à l'élément i-1,
∙ insérer l'élément i à sa place parmi les i premiers él
❖ Programme:
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 Complexité : O(N2)
T[j]= v
Le tri rapide (en anglais quick sort) est un algorithme de tri inventé par C.A.R. Hoare en 1961 et fondé
sur la méthode de conception diviser pour régner.
Son principe consiste à séparer l’ensemble des éléments en deux parties.
❖ Principe :
L'algorithme peut s’effectuer récursivement:
∙ une valeur pivot est choisie au hasard. (peut aussi être le premier ou le dernier élément de la liste
à trier).
∙On crée un premier sous-ensemble constitué des éléments plus petits que le pivot. On les place
à gauche du pivot.
∙On crée de la même façon un deuxième sous-ensemble constitué des éléments plus grands que
le pivot. On les place à droite de celui-ci.
∙On procède de même, par récursivité, sur les deux sous-ensembles jusqu’à obtenir des
sous ensembles d'un seul élément.
Algorithmes de tri 2 /6 M.GUEROIHI
Exemple :
On va illustrer le tri rapide sur le tableau T=[4,6,3,5,7,2,1] (Pivot=T[0]).
❖ Programme:
def Trirapide(L):
if len(L)<2: return L
#on va balayer la liste L et repartir les valeurs
n=len(L)
L1=[]
L2=[]
pivot=L[0] #ici on a pris le premier élément comme pivot.
for k in range(1,n):
if L[k]<= pivot:
L1.append(L[k]) #L1 reçoit les éléments plus petits
else:
L2.append(L[k]) #L2 reçoit les éléments plus grands
return (Trirapide(L1) + [pivot] + Trirapide(L2))
Exécution:
>>> L =[4,6,3,5,7,2,1]
>>> L= Trirapide (L)
>>> L
[1, 2, 3, 4, 5, 6, 7]
Algorithmes de tri 3 /6 M.GUEROIHI
❖ Calcul de complexité :
∙ Comptons le nombre de comparaisons
∙ La boucle for fait N-1 comparaisons
∙ Le pire des cas correspond au cas dans lequel 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
récurrence suivante:
C(N)= N-1+ C(N-1)
d'où la complexité est O(N2)
∙ Le meilleur des cas correspond à un segment coupé en deux moitiés égales. L'équation de
récurrence devient alors:
C(N)= N-1+2.C(N/2)
donc la complexité est O(N.log(N))
Algorithmes de tri 4 /6 M.GUEROIHI
5- TRI PAR FUSION
❖ Principe :
Le tri par fusion est un algorithme de tri basé sur la technique algorithmique diviser pour régner.
L'opération principale de l'algorithme est la fusion, qui consiste à réunir deux listes triées en une
seule.
Le principe de cet algorithme tend à adopter une formulation récursive :
∙ On découpe les données à trier en deux parties plus ou moins égales
∙ On trie les 2 sous-parties ainsi déterminées
∙ On fusionne les deux sous-parties pour retrouver les données de départ
Exemple :
❖ Implémentation :
L'implémentation de cet algorithme repose essentiellement en 2 fonctions :
∙ fusion : Permet de fusionner deux listes triées de telle sorte que la liste résultante la soit aussi. ∙
triFusion : Une fonction récursive qui assure le découpage de la liste et l'appel de la fonction de
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
return res+L1[i:]+L2[j:]
def triFusion(L):
if len(L) <= 1: return L
m = len(L) // 2
return fusion( triFusion(L[:m]),triFusion(L[m:]))
Algorithmes de tri 5 /6 M.GUEROIHI
>>> L = [ 4, 23, 3, 42, 2, 14, 4,45, 18, 38, 16 ]
>>> L=triFusion(L)
>>> L
[2, 3, 4, 4, 14, 16, 18, 23, 38, 42, 45]
❖ Calcul de complexité (tri par fusion):
Si on note :
∙ C(N) : le nombre total de comparaisons effectuées par la fonction triFusion
∙ f (N) : le nombre total de comparaisons effectuées par la fonction Fusion
∙ Pour trier un tableau de longueur N, on a l’équation de récurrence suivante:
C(N)=2.C(N/2)+ f (N)
Les deux appels récursifs se font sur deux segments de même longueur N/2
∙ Dans le meilleur des cas, la fonction fusion n'examine que les éléments 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)= 2.C(N/2)+ N/2
d'où la complexité est : O(N.log(N))
∙ Dans le pire des cas, tous les éléments sont examinés par la fonction fusion
Dans ce cas f (N)= N-1,
donc C(N)= 2.C(N/2)+ N-1 D'où la complexité est :
O(N.log(N))
❖ Comparaison DE COMPLEXITE DE DIFFERENTES METHODES DE TRIS
ALGORITHME DE TRI MEILLEUR CAS PIRE CAS
Insertion N N2
Sélection N2 N2
Bulle N N2
Rapide N.log(N) N2
Fusion N.log(N) N.log(N)
Algorithmes de tri 6 /6 M.GUEROIHI
