Livre_silo 30 août 2013 16:32 Page 322
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
322
Informatique pour tous
On en déduit facilement C(N ) ∼ N log N .
En ce qui concerne le nombre d’affectations, on note que la fonction partition effectue
un appel à echange initial, autant d’appels à echange que d’incrémentations de m, et éventuellement un dernier appel lorsque m != g. Le meilleur des cas est atteint lorsque le pivot
est toujours à sa place. Il y a alors un seul appel à echange, soit deux affectations. Il est
important de noter que ce cas ne correspond pas à la meilleure complexité en termes de
comparaisons (qui est alors quadratique). Dans le pire des cas, le pivot se retrouve toujours
à la position r-1. La fonction partition effectue alors 2(d − g) affectations, d’où un total de
N
2 affectations.
meilleur cas
moyenne
pire cas
comparaisons N log N
2N log N
N 2 /2
affectations
2N
2N log N
N 2
Exercice 13.4 Dérouler à la main l’algorithme de tri rapide sur le tableau [15,4,2,8,17,23,0,1].
Exercice 13.5 * Proposer un exemple de tableau sur lequel le tri rapide a un coût en O(N log N ) (meilleur
cas). Proposer également un exemple de tableau sur lequel il a un coût quadratique (pire cas).
13.3 Tri fusion
Comme le tri rapide, le tri fusion applique le principe diviser pour régner. Il partage les
éléments à trier en deux parties de même taille, sans chercher à comparer leurs éléments.
Une fois les deux parties triées récursivement, il les fusionne, d’où le nom de tri fusion.
Ainsi on évite le pire cas du tri rapide où les deux parties sont de tailles disproportionnées.
• Pour trier a[0:8], on trie a[0:4] et a[4:8].
7 6 3 5 4 2 1 8
• Pour trier a[0:4], on trie a[0:2] et a[2:4].
7 6 3 5
• Pour trier a[0:2], on trie a[0:1] et a[1:2].
7 6
• On fusionne a[0:1] et a[1:2].
6 7
• Pour trier a[2:4], on trie a[2:3] et a[3:4].
3 5
• On fusionne a[2:3] et a[3:4].
3 5
• On fusionne a[0:2] et a[2:4].
3 5 6 7
• Pour trier a[4:8], on trie a[4:6] et a[6:8].
4 2 1 8
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
322
Informatique pour tous
On en déduit facilement C(N ) ∼ N log N .
En ce qui concerne le nombre d’affectations, on note que la fonction partition effectue
un appel à echange initial, autant d’appels à echange que d’incrémentations de m, et éventuellement un dernier appel lorsque m != g. Le meilleur des cas est atteint lorsque le pivot
est toujours à sa place. Il y a alors un seul appel à echange, soit deux affectations. Il est
important de noter que ce cas ne correspond pas à la meilleure complexité en termes de
comparaisons (qui est alors quadratique). Dans le pire des cas, le pivot se retrouve toujours
à la position r-1. La fonction partition effectue alors 2(d − g) affectations, d’où un total de
N
2 affectations.
meilleur cas
moyenne
pire cas
comparaisons N log N
2N log N
N 2 /2
affectations
2N
2N log N
N 2
Exercice 13.4 Dérouler à la main l’algorithme de tri rapide sur le tableau [15,4,2,8,17,23,0,1].
Exercice 13.5 * Proposer un exemple de tableau sur lequel le tri rapide a un coût en O(N log N ) (meilleur
cas). Proposer également un exemple de tableau sur lequel il a un coût quadratique (pire cas).
13.3 Tri fusion
Comme le tri rapide, le tri fusion applique le principe diviser pour régner. Il partage les
éléments à trier en deux parties de même taille, sans chercher à comparer leurs éléments.
Une fois les deux parties triées récursivement, il les fusionne, d’où le nom de tri fusion.
Ainsi on évite le pire cas du tri rapide où les deux parties sont de tailles disproportionnées.
• Pour trier a[0:8], on trie a[0:4] et a[4:8].
7 6 3 5 4 2 1 8
• Pour trier a[0:4], on trie a[0:2] et a[2:4].
7 6 3 5
• Pour trier a[0:2], on trie a[0:1] et a[1:2].
7 6
• On fusionne a[0:1] et a[1:2].
6 7
• Pour trier a[2:4], on trie a[2:3] et a[3:4].
3 5
• On fusionne a[2:3] et a[3:4].
3 5
• On fusionne a[0:2] et a[2:4].
3 5 6 7
• Pour trier a[4:8], on trie a[4:6] et a[6:8].
4 2 1 8