Livre_silo 30 août 2013 16:32 Page 321
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
321
13 – Algorithmes de tri
PROGRAMME 17 Tri rapide
def echange(a, i, j):
a[i], a[j] = a[j], a[i]
def partition(a, g, d):
assert g < d
echange(a, g, random.randint(g, d-1))
v = a[g]
m = g
for i in range(g+1, d):
if a[i] < v:
m = m+1
echange(a, i, m)
if m != g:
echange(a, g, m)
return m
def tri_rapide_rec(a, g, d):
while g < d-1:
m = partition(a, g, d)
if m-g < d-m-1:
tri_rapide_rec(a, g, m)
g = m+1
else:
tri_rapide_rec(a, m+1, d)
d = m
def tri_rapide(a):
tri_rapide_rec(a, 0, len(a))
13.2.2 Complexité
La fonction partition fait toujours exactement d − g − 1 comparaisons. Si la fonction
partition détermine un segment de longueur K et un autre de longueur N −1−K, la fonction tri_rapide_rec va donc effectuer N − 1 comparaisons par l’intermédiaire de partition,
puis d’autres comparaisons par l’intermédiaire des deux appels récursifs à tri_rapide_rec (la
fonction réécrite avec un seul appel récursif a la même complexité en temps). Le pire des
cas correspond à K = 0, 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ù C(N ) ∼
N
2
2 . Le meilleur des cas correspond à un segment coupé en deux moitiés
égales, c’est-à-dire K = N/2. L’ équation de récurrence devient alors :
C(N ) = N − 1 + 2C(N/2).