Livre_silo 30 août 2013 16:32 Page 320
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
320
Informatique pour tous
Après cet appel, le pivot a[m] se retrouve à sa place définitive. On effectue alors deux appels
récursifs pour trier a[g..m[ et a[m+1..d[ :
tri_rapide_rec(a, g, m)
tri_rapide_rec(a, m+1, d)
Pour trier un tableau, il suffit d’appeler tri_rapide_rec sur la totalité de ses éléments :
def tri_rapide(a):
tri_rapide_rec(a, 0, len(a))
Tel qu’il est écrit, ce code présente deux inconvénients. D’une part, il atteint très vite le
nombre maximal d’appels récursifs (1 000 par défaut en Python). D’autre part, il peut
exhiber une complexité quadratique, notamment dans le cas d’un tableau déjà trié. On va
remédier à ces deux problèmes.
Pour rester sous la limite des 1 000 appels récursifs de Python, on va tout d’abord supprimer
l’un des deux appels récursifs au profit d’une boucle.
def tri_rapide_rec(a, g, d):
while g < d-1:
m = partition(a, g, d)
tri_rapide_rec(a, g, m)
g = m+1
Ici, le second appel a été remplacé par l’affectation g = m+1 et le tout a été placé dans une
boucle while, pour que le calcul soit répété tant que le segment contient au moins deux
éléments. Cela ne suffit pas pour autant, car l’appel récursif restant peut être répété un
grand nombre de fois, par exemple si le pivot se trouve plus souvent dans la moitié droite
que gauche. D’où l’idée d’utiliser l’appel récursif pour le plus petit segment et la boucle
pour le plus grand :
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
Pour ce qui est de la complexité quadratique dans le cas d’un tableau déjà trié (ou trié en
ordre inverse par exemple), une solution simple consiste à ne pas choisir systématiquement
le premier élément du segment comme pivot, mais plutôt un élément au hasard. Une façon
très simple de réaliser cette idée consiste à démarrer la fonction partition par un échange
aléatoire :
def partition(a, g, d):
echange(a, g, random.randint(g, d-1))
...
Le reste du code est alors inchangé. Le code complet est donné ci-après.
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
320
Informatique pour tous
Après cet appel, le pivot a[m] se retrouve à sa place définitive. On effectue alors deux appels
récursifs pour trier a[g..m[ et a[m+1..d[ :
tri_rapide_rec(a, g, m)
tri_rapide_rec(a, m+1, d)
Pour trier un tableau, il suffit d’appeler tri_rapide_rec sur la totalité de ses éléments :
def tri_rapide(a):
tri_rapide_rec(a, 0, len(a))
Tel qu’il est écrit, ce code présente deux inconvénients. D’une part, il atteint très vite le
nombre maximal d’appels récursifs (1 000 par défaut en Python). D’autre part, il peut
exhiber une complexité quadratique, notamment dans le cas d’un tableau déjà trié. On va
remédier à ces deux problèmes.
Pour rester sous la limite des 1 000 appels récursifs de Python, on va tout d’abord supprimer
l’un des deux appels récursifs au profit d’une boucle.
def tri_rapide_rec(a, g, d):
while g < d-1:
m = partition(a, g, d)
tri_rapide_rec(a, g, m)
g = m+1
Ici, le second appel a été remplacé par l’affectation g = m+1 et le tout a été placé dans une
boucle while, pour que le calcul soit répété tant que le segment contient au moins deux
éléments. Cela ne suffit pas pour autant, car l’appel récursif restant peut être répété un
grand nombre de fois, par exemple si le pivot se trouve plus souvent dans la moitié droite
que gauche. D’où l’idée d’utiliser l’appel récursif pour le plus petit segment et la boucle
pour le plus grand :
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
Pour ce qui est de la complexité quadratique dans le cas d’un tableau déjà trié (ou trié en
ordre inverse par exemple), une solution simple consiste à ne pas choisir systématiquement
le premier élément du segment comme pivot, mais plutôt un élément au hasard. Une façon
très simple de réaliser cette idée consiste à démarrer la fonction partition par un échange
aléatoire :
def partition(a, g, d):
echange(a, g, random.randint(g, d-1))
...
Le reste du code est alors inchangé. Le code complet est donné ci-après.