Livre_silo 30 août 2013 16:32 Page 319
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
319
13 – Algorithmes de tri
On commence par écrire une fonction echange pour échanger les éléments a[i] et a[j] d’un
tableau a :
def echange(a, i, j):
a[i], a[j] = a[j], a[i]
La fonction partition prend le tableau a et deux indices g et d en arguments, avec la convention que g est inclus et d exclu. On suppose qu’il y a au moins un élément dans ce segment,
ce que l’on vérifie avec assert :
def partition(a, g, d):
assert g < d
On choisit a[g] comme pivot :
v = a[g]
Le principe consiste alors à parcourir le tableau de la gauche vers la droite, entre les indices
g (inclus) et d (exclu), avec une boucle for. À chaque itération, la situation est la suivante :
g
m
i
d
v
< v
⩾ v
?
L’indice i de la boucle dénote le prochain élément à considérer et l’indice m partitionne la
portion déjà parcourue.
m = g
for i in range(g+1, d):
Si a[i] est supérieur ou égal à v, il n’y a rien à faire. Dans le cas contraire, pour conserver
l’invariant de boucle, il suffit d’incrémenter m et d’échanger a[i] et a[m] :
if a[i] < v:
m = m+1
echange(a, i, m)
Une fois sorti de la boucle, on met le pivot à sa place, c’est-à-dire à la position m, et on
renvoie cet indice :
if m != g:
echange(a, g, m)
return m
On écrit ensuite la partie récursive du tri rapide sous la forme d’une fonction tri_rapide_rec
qui prend les mêmes arguments que la fonction partition. Si g ⩾ d − 1, il y a au plus un
élément à trier et il n’y a donc rien à faire, ce qui assure au passage que l’on n’appelle pas
partition avec g ⩾ d :
def tri_rapide_rec(a, g, d):
if g >= d-1: return
Sinon, on partitionne les éléments entre g et d :
m = partition(a, g, d)
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
319
13 – Algorithmes de tri
On commence par écrire une fonction echange pour échanger les éléments a[i] et a[j] d’un
tableau a :
def echange(a, i, j):
a[i], a[j] = a[j], a[i]
La fonction partition prend le tableau a et deux indices g et d en arguments, avec la convention que g est inclus et d exclu. On suppose qu’il y a au moins un élément dans ce segment,
ce que l’on vérifie avec assert :
def partition(a, g, d):
assert g < d
On choisit a[g] comme pivot :
v = a[g]
Le principe consiste alors à parcourir le tableau de la gauche vers la droite, entre les indices
g (inclus) et d (exclu), avec une boucle for. À chaque itération, la situation est la suivante :
g
m
i
d
v
< v
⩾ v
?
L’indice i de la boucle dénote le prochain élément à considérer et l’indice m partitionne la
portion déjà parcourue.
m = g
for i in range(g+1, d):
Si a[i] est supérieur ou égal à v, il n’y a rien à faire. Dans le cas contraire, pour conserver
l’invariant de boucle, il suffit d’incrémenter m et d’échanger a[i] et a[m] :
if a[i] < v:
m = m+1
echange(a, i, m)
Une fois sorti de la boucle, on met le pivot à sa place, c’est-à-dire à la position m, et on
renvoie cet indice :
if m != g:
echange(a, g, m)
return m
On écrit ensuite la partie récursive du tri rapide sous la forme d’une fonction tri_rapide_rec
qui prend les mêmes arguments que la fonction partition. Si g ⩾ d − 1, il y a au plus un
élément à trier et il n’y a donc rien à faire, ce qui assure au passage que l’on n’appelle pas
partition avec g ⩾ d :
def tri_rapide_rec(a, g, d):
if g >= d-1: return
Sinon, on partitionne les éléments entre g et d :
m = partition(a, g, d)