Tri rapide

Présentation

L’algorithme de tri rapide, "quick sort" en anglais, est un algorithme de type dichotomique. Son principe consiste à séparer l’ensemble des éléments en deux parties. La différence par rapport au tri fusion, vu précédemment, est que la séparation des différentes valeurs ne s’effectue pas n’importe comment. Pour effectuer la séparation, une valeur pivot est choisie. Les valeurs sont réparties en deux ensembles suivant qu’elles sont plus grandes ou plus petites que le pivot. Ensuite, les deux ensembles sont triés séparément, suivant la même méthode. L’algorithme, tout comme le tri fusion, est récursif, mais cette fois, il n’est pas nécessaire de fusionner les deux ensembles. Le résultat du tri est égal au tri de l’ensemble dont les valeurs sont inférieures au pivot concaténé à l’ensemble des valeurs supérieures au pivot, ce dernier étant pris en sandwich entre les deux ensembles.

Choix du pivot

Le choix du pivot est le problème central de cet algorithme. En effet, l’idéal serait de pouvoir répartir les deux ensembles en deux parties de taille à peu prés égales. Cependant, la recherche du pivot qui permettrait une partition parfaite de l’ensemble en deux parties égales aurait un coût trop important. C’est pour cela que le pivot est choisit de façon aléatoire parmi les valeurs de l’ensemble. Dans la pratique, le pivot est le premier ou le dernier élément de l’ensemble à fractionner. En moyenne, les deux ensembles seront donc de taille sensiblement égale.

Exemple

Grandes étapes de l’évolution du tableau au fil de l’algorithme : En bleu, les valeurs déjà positionnées, en rose, les valeurs qui servent de pivot pour passer à la ligne suivante.

Complexité

La complexité du tri rapide pour trier une liste de n éléments est égale à la complexité pour le tri de p et de q éléments ou p+q+1=n. Soit T(n)=T(p)+T(q)+constante. Dans le meilleur des cas, p=q=n/2, soit T(n)=2T(q). On retrouve une complexité dans le meilleur des cas en O(n.ln(n)) , ce qui est analogue à la complexité du tri fusion. Cependant, si dans le meilleur des cas, le tri rapide est plus rapide que le tri fusion puisque l’étape "fusion" n’est pas nécessaire, il n’en va pas toujours de même. En effet, le choix du pivot est totalement aléatoire, or le hasard ne fait pas toujours bien les choses. Ainsi, dans le pire des cas, c’est à dire si l’ensemble des éléments à trier est préalablement classé de manière décroissante, le choix de la première valeur de la liste comme pivot produira deux ensembles de taille 0 et (n-1). Ce qui est loin d’être deux ensembles de taille égale. L’application de l’algorithme de tri rapide à ce type de liste reviens, en fait, à effectuer le tri par sélection, qui est en O(n²). Comme quoi, dans certains cas particuliers, le tri rapide n’est pas si rapide que cela. Avec le tri fusion, il n’y a aucun facteur aléatoire et la complexité en O(n.ln(n)) est garantie. Dans la majorité des cas, le tri rapide sera donc préféré au tri fusion, sauf pour la réalisation d’applications ou la rapidité d’exécution doit être garantie, comme dans le cas d’applications en temps réel.

 Accueil des algorithmes de tri
 Article précédent : le tri fusion
 Article suivant : le tri par Arbre Binaire de Recherche