Tri rapide

Le tri rapide (en Anglais : quicksort) est peut-être l'algorithme de tri le plus utilisé. Il est relativement simple à comprendre et à implémenter et, comme son nom l'indique, très rapide.

L'idée de l'algorithme est très simple. Étant donné un vecteur d'éléments à trier :

Si l'étape numéro

ci-dessus peut se faire avec une complexité

et si le nombre d'éléments de la partie gauche et le nombre d'éléments de la partie droite ainsi obtenues ne sont pas trop différents, alors, la complexité de l'algorithme est $O(n\texttt{log} n)$ .

Pour que les deux parties extrêmes soient de tailles similaires, le pivot doit être proche de l'élément médian du vecteur. Malheureusement, un algorithme optimal pour calculer l'élément médian d'un vecteur est assez coûteux en temps. C'est pourquoi dans la présentation traditionnelle de l'algorithme de tri rapide, on sélectionne le pivot autrement. Il est à noter que si le pivot est systématiquement le plus petit ou le plus grand, alors la complexité de l'algorithme de tri rapide n'est plus en $O(n \texttt{log} n)$ . Cependant même avec un pivot choisi arbitrairement, l'algorithme de tri rapide reste très rapide. Nous allons d'abord suivre la présentation traditionnelle et choisir le pivot au milieu du vecteur. L'idée est que, si par hasard le vecteur est déjà trié, alors cet élément est aussi l'élément médian. Dans les autres cas, c'est un choix arbitraire. De cette manière, on évite un comportement anormal pour le cas supposé fréquent où le vecteur est déjà trié ou presque.

Il est malheureusement difficile de programmer l'étape numéro

ci-dessus. On peut se poser la question de pourquoi ne pas partitionner avec tous les éléments strictement inférieurs à gauche et supérieurs ou égaux à droite (ou vice versa), un algorithme beaucoup plus facile à programmer. Le problème est qu'il peut toujours se produire que l'élément pivot soit le plus petit ou le plus grand élément du vecteur. Dans ce cas, avec cette méthode, l'une de ces deux parties contiendrait tous les éléments de début et l'algorithme bouclerait. Il est donc important de garantir que la taille des deux parties soit strictement inférieure à la taille initiale du tableau.

Afin de garantir cela, nous allons exclure le pivot choisi à chaque étape, puis partager les autres éléments entre ceux qui sont inférieurs au pivot à gauche, ceux qui sont supérieurs à droite, ceux qui sont égaux soit à gauche soit à droite et le pivot choisi entre les deux. Afin d'exclure le pivot, nous allons d'abord l'échanger avec le dernier élément du tableau, puis partitionner les autres éléments et finalement échanger le dernier élément (le pivot) avec l'un des éléments supérieurs ou égaux au pivot. Cette idée est illustrée dans la figure 24.3.

**Figure 24.3:** Exclusion de l'élément pivot
$\begin{figure}\begin{center} \input exclusion.pstex_t \end{center} \end{figure}$

L'idée de la méthode de partition est la suivante : on maintient deux positions, l'une à gauche et l'autre à droite, telles que les éléments qui précèdent la position de gauche soient inférieurs ou égaux au pivot et ceux qui succèdent la position de droite soient supérieurs ou égaux au pivot. La position de gauche est avancée à droite et celle de droite avancée à gauche tant que la condition est respectée. Quand ce processus se termine, l'élément de la position gauche est strictement supérieur au pivot et celui de la position droite est strictement inférieur au pivot. Les deux sont alors échangés et le processus continue. Ce processus est illustré dans la figure 24.4 avec l'élément 28 comme pivot. Cette étape a clairement une complexité

**Figure 24.4:** Partitionnmenet du vecteur
$\begin{figure}\begin{center} \input partition.pstex_t \end{center} \end{figure}$

(loop while (<= left right) do (loop while (<= left right) until (< pivot (aref v left)) do (incf left)) (loop while (<= left right) until (< (aref v right) pivot) do (decf right)) (when (<= left right (rotatef (aref v left) (aref v right)) (incf left) (decf right)))

Ce code a clairement une complexité

. Lorsque ce morceau de code se termine, la différence entre right et left est

, les éléments se trouvant à une position strictement inférieure à left sont inférieurs ou égaux au pivot et les éléments à une position strictement supérieure à right sont supérieurs ou égaux au pivot. Les deux parties sont forcément d'une taille inférieure à la taille initiale du tableau, car un élément est exclu.

Il suffit maintenant d'échanger le pivot choisi avec le premier élément de la partie droite obtenue, puis de trier les deux parties.

L'algorithme de tri rapide est facile à adapter aux listes et le résultat est plus simple que pour les vecteurs. Après avoir choisi l'élément pivot, il suffit de parcourir la liste de la partitionner en trois parties, les éléments strictement inférieurs à l'élément pivot, les éléments égaux à l'élément pivot et les éléments strictement supérieurs à l'élément pivot. Puis, il faut trier récursivement la première et la dernière liste et finalement concaténer les trois listes obtenues.

Le seul problème avec le tri rapide sur les listes est le choix du pivot. Nous avons déjà mentionné le risque de choisir le premier ou le dernier élément. Ici, nous allons d'abord choisir le premier élément, malgré le risque, puis discuter de meilleures solutions.

Le problème du choix de l'élément pivot peut être résolu de plusieurs manières. On peut, bien sûr, systématiquement choisir un autre élément comme pivot, par exemple celui du milieu de la liste. Cela nécessite un parcours supplémentaire de la liste. En fait, si l'on ne fait pas attention, cela nécessite deux parcours supplémentaires. Un parcours pour déterminer la longueur de la liste, et un autre pour trouver l'élément du milieu. Mais on peut argumenter que cela prend très peu de temps pour la raison suivante : dans une application réelle, on ne trie pas d'objets simples comme des entiers. Il est donc probable que le test d'égalité sur deux objets du domaine, voir l'exécution de la fonction key, prenne la plus grande partie du temps. Parcourir la liste une ou deux fois de plus, en particulier si ces parcours sont effectués avec des fonctions primitives length et elt, ne représente donc qu'un temps négligeable par rapport à l'exécution de ces deux fonctions.

Voici donc une version de cet algorithme qui utilise l'élément du milieu comme pivot :

Nos deux versions de l'algorithme de tri rapide sur les listes sont destructives, à savoir que la liste initiale est modifiée. Ceci est conforme à la tradition Common Lisp, car la fonction sort prédéfinie est elle-même destructive. Il y a deux raisons de cela. D'abord, il est souvent plus efficace de recycler les cellules que de les jeter et d'en allouer d'autres. Puis, si l'utilisateur ne souhaite pas détruire sa liste, il est facile de précéder l'appel à la fonction de tri d'un appel à copy-list.