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
.
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
. 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.
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é .
Voici un morceau de code pour partitionner le vecteur :
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.
Voici le code :
trirapide.lisp
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.
Voici le code :
trirapide-liste.lisp
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 :
trirapide-liste2.lisp
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.
Irene DURAND