Livre_silo 30 août 2013 16:32 Page 317
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
317
13 – Algorithmes de tri
On commence par une boucle for pour parcourir le tableau :
def tri_insertion(a):
for i, v in enumerate(a):
Pour insérer l’élément a[i] à la bonne place, on utilise alors une boucle while qui décale vers
la droite les éléments tant qu’ils sont supérieurs à a[i] :
j = i
while 0 < j and v < a[j-1]:
a[j] = a[j-1]
j = j-1
Une fois sorti de la boucle, il reste à positionner a[i] à sa place :
a[j] = v
Le code complet est donné programme 16 ci-dessous.
PROGRAMME 16 Tri par insertion
def tri_insertion(a):
for i, v in enumerate(a):
j = i
while 0 < j and v < a[j-1]:
a[j] = a[j-1]
j = j-1
a[j] = v
13.1.2 Complexité
On note que la fonction tri_insertion effectue exactement le même nombre de comparaisons et d’affectations. Lorsque la boucle while insère l’élément a[i] à la position i−k, elle
effectue k + 1 comparaisons. Au mieux, k vaut 0 et au pire, k vaut i, avec i qui varie de 1
à N − 1, ce qui donne au final le tableau suivant :
meilleur cas moyenne pire cas
comparaisons
N
N 2 /4
N 2 /2
affectations
N
N 2 /4
N 2 /2
Exercice 13.1 Dérouler à la main l’algorithme de tri par insertion sur le tableau [15,4,2,9,55,16,0,1].
Exercice 13.2 * Démontrer la correction du tri par insertion.
Exercice 13.3 Proposer un exemple de tableau sur lequel le tri par insertion a un coût linéaire (meilleur
cas). Proposer également un exemple de tableau sur lequel il a un coût quadratique (pire cas).
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
317
13 – Algorithmes de tri
On commence par une boucle for pour parcourir le tableau :
def tri_insertion(a):
for i, v in enumerate(a):
Pour insérer l’élément a[i] à la bonne place, on utilise alors une boucle while qui décale vers
la droite les éléments tant qu’ils sont supérieurs à a[i] :
j = i
while 0 < j and v < a[j-1]:
a[j] = a[j-1]
j = j-1
Une fois sorti de la boucle, il reste à positionner a[i] à sa place :
a[j] = v
Le code complet est donné programme 16 ci-dessous.
PROGRAMME 16 Tri par insertion
def tri_insertion(a):
for i, v in enumerate(a):
j = i
while 0 < j and v < a[j-1]:
a[j] = a[j-1]
j = j-1
a[j] = v
13.1.2 Complexité
On note que la fonction tri_insertion effectue exactement le même nombre de comparaisons et d’affectations. Lorsque la boucle while insère l’élément a[i] à la position i−k, elle
effectue k + 1 comparaisons. Au mieux, k vaut 0 et au pire, k vaut i, avec i qui varie de 1
à N − 1, ce qui donne au final le tableau suivant :
meilleur cas moyenne pire cas
comparaisons
N
N 2 /4
N 2 /2
affectations
N
N 2 /4
N 2 /2
Exercice 13.1 Dérouler à la main l’algorithme de tri par insertion sur le tableau [15,4,2,9,55,16,0,1].
Exercice 13.2 * Démontrer la correction du tri par insertion.
Exercice 13.3 Proposer un exemple de tableau sur lequel le tri par insertion a un coût linéaire (meilleur
cas). Proposer également un exemple de tableau sur lequel il a un coût quadratique (pire cas).