TRI RAPIDE

1 TRI RAPIDE

0(n2) liste L de longueur n, liste L' de longueur n/2, on tire L' 4 fois plus vite que L.

Si je veux trier 2 listes de taille n/2, on va 2 fois plus vite qu'une liste de taille n

1. Tri rapide:

Def tire rapide(L):

if len(L) <= 1

return L

Linf, Lsup= [],[]

for i range (1, len(l):

if L[i]<=L[0]:

Linf.append(L[i])

else:

Lsup.append(L[i])

return trirapide(Linf) + trirapide(Lsup) + (L[0])

Complexité <=CSTE*n*nombre d'étage

meilleurs de cas: -Linf même taille que Lsup (a 1 près)-> moins d'étages

Or le moins d'etage est k car: 2k<=n<2k+1

Donc complexité: cste*n*k --> 0(nlog2(n))

Pire des cas: Linf ou Lsup est vide a chaque fois --> (n-1) étages

Donc complexité 0(n2)

Complexité moyenne:

0(nlog(n))

2 TRI FUSION:

On force le meilleur des cas :on coupe la liste en 2 sous-listes de longueur égales (à 1 près)

On commence par écrire ue fonction (L1,L2) qui fusonne 2 listes triées en 1 liste triées.

1. Def fusion (L1,L2):

i,j =0,0

L=[]

While i<len(L1) and j<len(L2)

If L1[i]<L2[j]

L.append(L1[i])

i=i+1

Else:

L.append(L2[j])

j=j+1

Return L+L1[i:]+L2[j:]

2. Def trifusion(L):

If len(L)<=1:

Return L

Else:

Return fusion( trifusion(L[:len(l)//2]), trifusion(L[len(l)//2:]) )

COMPLEXITE:

cout fusion: cste*(len(L1) + len(L2))= cste*len(L). À chaque étage

Or log2(n) étages-------->

...