Livre_silo 30 août 2013 16:32 Page 318
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
318
Informatique pour tous
13.2 Tri rapide
Le tri rapide consiste à appliquer la méthode diviser pour régner : on partage les éléments
à trier en deux sous-ensembles, les éléments du premier étant plus petits que les éléments
du second, puis on trie récursivement chaque sous-ensemble. En pratique, on réalise le
partage à l’aide d’un élément p arbitraire de l’ensemble à trier, appelé pivot. Les deux
sous-ensembles sont alors respectivement les éléments plus petits et plus grands que p.
Le tri rapide d’un tableau s’effectue en place. On va illustrer le tri rapide sur le tableau
[7,6,3,5,4,2,1].
Pour trier a[0:7], on choisit
au hasard 4 comme pivot.
7 6 3 5 4 2 1
On place les éléments plus petits que 4,
puis 4, puis les autres.
3 2 1 4 7 6 5
Pour trier a[0:3], on choisit 3 comme pivot.
3 2 1
On place les éléments plus petits que 3,
puis 3, puis les autres.
2 1 3
Pour trier a[0:2], on choisit 2 comme pivot.
2 1
On place les éléments plus petits que 2,
puis 2, puis les autres.
1 2
Pour trier a[4:7], on choisit
au hasard 6 comme pivot.
7 6 5
On place les éléments plus petits que 6,
puis 6, puis les autres.
5 6 7
On obtient finalement :
1 2 3 4 5 6 7
13.2.1 Réalisation
Pour réaliser ce tri, on écrit deux fonctions. Une fonction de partition organise les éléments
autour d’un pivot et renvoie la position de ce dernier. Une autre fonction trie récursivement
les deux portions du tableau à gauche et à droite du pivot. Les fonctions de partition et de
tri prennent en arguments le tableau et deux indices délimitant la portion à considérer.