Partie 5 : le tri rapide#
Le principe#
Pour ranger une pile de copies par note, vous pourriez choisir une copie au hasard comme référence, puis faire deux tas : à gauche les copies moins bien notées que la référence, à droite les mieux notées. La copie de référence se retrouve alors exactement à sa place définitive, entre les deux tas. Il ne reste plus qu'à ranger chacun des deux tas... de la même manière !
C'est le principe du tri rapide (quicksort en anglais), lui aussi récursif et basé sur l'idée diviser pour régner :
on choisit un élément de la liste, appelé le pivot (ici, toujours le dernier élément de la zone à trier) ;
on réorganise la zone pour placer les éléments plus petits que le pivot à sa gauche, et les plus grands à sa droite : c'est la partition. Le pivot est alors à sa place définitive ;
on trie la partie gauche et la partie droite, avec le tri rapide lui-même.
Le cas de base est une zone de 0 ou 1 élément, qui n'a pas besoin d'être triée. Contrairement au tri fusion, le tri rapide ne crée pas de nouvelles listes : il travaille sur une zone de la liste d'origine, délimitée par deux positions debut et fin.
1Pour trier la zone de la liste comprise entre les positions debut et fin :
2 Si la zone contient au plus un élément : ne rien faire
3 Sinon :
4 Partitionner la zone autour du pivot, et noter la position finale p du pivot
5 Trier la zone de debut à p - 1 (avec le tri rapide)
6 Trier la zone de p + 1 à fin (avec le tri rapide)
Le tri fusion fait le gros du travail après les appels (en fusionnant), alors que le tri rapide le fait avant (en partitionnant). Observez-le dans la visualisation : l'arbre des appels et la pile d'appels fonctionnent comme pour le tri fusion.
La partition#
Pour partitionner la zone, on la parcourt de gauche à droite en maintenant, au début de la zone, une zone des petits qui contient tous les éléments plus petits que le pivot rencontrés jusque-là. La variable i indique la position où commence la zone des grands, c'est-à-dire où ranger le prochain petit élément. Chaque élément est comparé au pivot :
s'il est plus petit, on l'échange avec l'élément en position
i, ce qui l'ajoute à la zone des petits, etiavance d'une case ;sinon, on ne fait rien : il reste dans la zone des grands.
Pour finir, on échange le pivot avec l'élément en position i : il se retrouve juste après les petits, à sa place définitive. On ne fait pas d'échange inutile lorsqu'un élément est déjà au bon endroit.
Voici la partition de [7, 3, 9, 1, 5], avec le pivot 5 :
Élément examiné |
Comparaison |
Opération |
Liste |
|
|---|---|---|---|---|
|
|
aucune |
|
|
|
|
échange de |
|
|
|
|
aucune |
|
|
|
|
échange de |
|
|
fin du parcours |
échange du pivot |
|
|
Le pivot 5 est maintenant en position 2, avec les petits [3, 1] à sa gauche et les grands [7, 9] à sa droite. Le tri rapide trie ensuite la zone des positions 0 à 1, puis celle des positions 3 à 4.
À vous de jouer#
Triez la liste ci-dessous en suivant exactement le tri rapide : chaque comparaison avec le pivot et chaque échange doivent être faits dans le bon ordre. Les appels se font automatiquement.
Complexité#
Le travail du tri rapide dépend de la qualité des pivots, c'est-à-dire de la manière dont ils coupent les zones. Sur une liste mélangée, le pivot coupe en général la zone en deux parties de tailles comparables. On retrouve alors la situation du tri fusion : environ \(\log_2(n)\) niveaux d'appels, et chaque niveau compare tous les éléments à leur pivot, soit environ \(n\) opérations par niveau. Le tri rapide est donc en \(O(n \log n)\) en moyenne. En pratique, il est même souvent plus rapide que le tri fusion, car il travaille sur place, sans créer de nouvelles listes : d'où son nom. Mais attention, ce n'est pas toujours le cas...
Questions#
Question 12#
Effectuez à la main la première partition du tri rapide de la liste [6, 1, 8, 3, 5, 2, 7, 4], dont le pivot est 4. Présentez chaque étape dans un tableau comme celui de l'exemple. Quelle est la position finale du pivot ? Quelles zones de la liste le tri rapide trie-t-il ensuite ?
Question 13#
Dans la visualisation, triez une liste aléatoire de 16 éléments, puis une liste déjà triée de 16 éléments. Comparez la forme des deux arbres des appels et le nombre de comparaisons.
Expliquez pourquoi le tri rapide est lent sur une liste déjà triée. Combien de comparaisons effectue-t-il dans ce cas pour une liste de \(n\) éléments ? Quelle est alors sa complexité ?
Proposez une autre manière de choisir le pivot qui éviterait ce problème sur une liste déjà triée.
Comparer les quatre tris#
Dans la visualisation ci-dessous, vous pouvez choisir l'algorithme dans le menu déroulant. La liste ne change pas lorsque vous changez d'algorithme, ce qui permet de comparer les quatre tris sur exactement la même liste. Essayez-la avec une liste aléatoire, puis avec une liste déjà triée et une liste triée à l'envers.