Tri rapide

Description

L'algorithme du tri rapide est à la fois facile à comprendre et extrêmement difficile à implémenter correctement, en tous cas sur les tableau.

Voici une description générale de l'algorithme : étant donnée une suite S de N éléments, choisir un élément e arbitraire de la suite. On appelle cet élément élément pivot. Puis partager les éléments de S en trois sous suites T, U et V, telles que T contient tous les éléments de S qui sont strictement inférieurs à e, U contient tous les éléments de S qui sont égaux à e et V contient tous les éléments de S qui sont strictement supérieurs à e. Trier récursivement les suites T et V (obtenant disons T' et V'), puis concaténer T', U et V' pour obtenir le résultat final.

Exemple : nous souhaitons trier la suite d'entiers S = 5,4,7,5,8,l,4,5,4,6,7,8,7,4,6,1,6. On choisit arbitrairement e = 6. Les sous suites deviennent alors T = 5,4,5,l,4,5,4,4,1 (pas nécessairement dans cet ordre), U = 6,6,6 et V = 7,8,7,8,7 (encore une fois pas nécessairement dans cet ordre). Après un tri récursif de T, on obtient T'= 1,1,4,4,4,4,5,5,5 et V'= 7,7,7,8,8. Le résultat final est 1,1,4,4,4,4,5,5,5,6,6,6,7,7,7,8,8

Le cas de base de l'algorithme ci-dessus arrive lorsque S est vide ou contient un seul élément, auquel cas, il suffit de renvoyer S non traitée. La terminaison de l'algorithme est assurée, car U contient au moins un élément (e), ce qui implique que T et V sont strictement plus courtes que s. Ce ne serait pas le cas se l'on avait partagé S en deux suites, l'une avec les éléments inférieurs à e et l'autre avec les éléments supérieurs ou égaux à e. La raison est que rien n'empêche que e soit le plus petit élément de S ce qui fait que la seconde des deux suites contiendrait tous les éléments de S. Un raisonnement analogue est possible si l'on partage S en deux suites, l'une avec les éléments inférieurs ou égaux à e et l'autre avec les éléments supérieurs à e.

Une implémentation très directe en Lisp (utilisant des listes) de cette algorithme est relativement facile. Cette implémentation n'utilise pas de mémoire supplémentaire (autre que la liste passée en argument) ce qui est très souhaitable.

Les choses se compliquent lorsque nous souhaitons trier des tableaux. D'abord, il n'est pas pratique de créer des sous tableaux et de les concaténer à la fin, car cela utiliserait de la mémoire supplémentaire. Il faut donc faire avec le tableau passé en argument. Puis, il n'est pas pratique non plus de partager les éléments du tableau en trois parties. Nous allons donc voir comment on peut résoudre le problème créé par un partage en deux parties seulement.

Partitionner un tableau

Pour y arriver, nous allons définir une opération appelée partitionnement d'un tableau. Étant donné un objet o du domaine des éléments stockés dans le tableau, partitionner le tableau signifie réorganiser les éléments du tableau de telle manière à ce que la partie gauche contient les éléments du tableau qui sont inférieurs à o et la partie droite contient les éléments du tableau qui sont supérieurs à o. Concernant les éléments égaux à o certains peuvent se trouver dans la partie gauche et certains autres dans la partie droite. Mise à part l'effet de bord qui est la réorganisation du tableau, l'opération de partitionnement renvoie également une position p telle que les éléments avec une position inférieure à p constituent la partie gauche et les éléments avec une position supérieure ou égale à p constituent la partie droite du tableau.

Si l'on pouvait garantir que chacune des parties obtenues par le partitionnement du tableau contienne au moins un élément, on pourrait exprimer le tri rapide d'un tableau de la manière suivante : Choisir arbitrairement un élément pivot parmi les éléments du tableau. Partitionner le tableau par rapport cet élément. Trier récursivement la partie gauche et la partie droite.

Malheureusement, il est possible que l'une des deux parties soit vide, auquel cas, l'algorithme ne se termine pas (car il sera appelé récursivement sur autant d'objets). Nous allons voir comment régler ce problème après la description de l'algorithme de partitionnement.

Pour partitionner un tableau, nous allons maintenir deux indices du tableau g (pour gauche) et d (pour droite). L'invariant est que tous les éléments avec un indice strictement inférieur à g sont dans la partie gauche, et tous les éléments avec un indice strictement supérieur à d sont dans la partie droite. Initialement g = 0 et d = N-1N est le nombre d'éléments du tableau. À chaque itération, on incrémente la valeur de g jusqu'à ce que l'élément de la position g soit strictement supérieur à l'élément pivot, et on décrémente la valeur de d jusqu'à ce que l'élément de la position d soit strictement inférieur à l'élément pivot. L'invariant est alors maintenu. Puis on échange les deux éléments aux positions g et d et on incrément g de 1 et on décrémente d de 1. Encore une fois l'invariant est maintenu. Il est possible qu'aucun élément du tableau soit inférieur à l'élément pivot et il est possible qu'aucun élément du tableau soit supérieur à l'élément pivot (et les deux peuvent être vrai simultanément si le tableau ne contient que des éléments égaux à l'élément pivot. Pour cette raison, on arrête également l'itération si jamais g est strictement supérieur à d. Exercice : montrer que lorsque le processus se termine, g = d+1.

Lorsque le processus se termine, la partie gauche se trouve entre les indices 0 et g-1 = d inclus, et la partie droite se trouve entre les indices d+1 = g inclus.

L'algorithme de partitionnement se généralise de manière triviale à une partie d'un tableau, à savoir les indices entre deux valeurs min et max.

Voici une implémentation en Lisp de l'algorithme de partitionnement.

Trier un tableau grâce au partitionnement

Comme cela a été indiqué ci-dessus, l'algorithme évident qui consiste à partitionner le tableau en deux, puis de trier les deux parties risque de ne pas marcher, car il est possible que l'une des deux parties soit vide, ce qui implique que l'un des appels récursifs serait fait avec un tableau du même taille, avec le risque de non terminaison du programme.

Une façon de régler ce problème pourrait être de vérifier si l'une des parties est en fait vide, et dans ce cas choisir un élément pivot différent. Cela risque de devenir assez complexe (il se peut que tous les éléments du tableau soit égaux, par exemple). Ici, nous allons employer une autre méthode.

La méthode consiste à exclure un l'élément pivot choisi (mais d'inclure les autres éventuels éléments égaux à ce pivot) des deux appels récursifs, ce qui force les deux parties d'avoir au moins un élément de moins par rapport au tableau d'origine.

Pour cela, on peut par exemple choisir le premier élément comme élément pivot, puis partitionner le reste du tableau, puis trier les parties. Le problème est que dans ce cas là, le pivot (qui devrait se trouver entre les deux parties) est au début du tableau après les appels récursifs. Il aurait alors fallu réorganiser les éléments a posteriori ce qui n'est pas souhaitable (mais pas une catastrophe pour la performance non plus). Nous allons le faire différemment.

Nous choisissons donc le premier élément (élément numéro 0) comme élément pivot, puis nous partageons le reste du tableau (éléments numéro 1 .. N-1) ce qui nous donne un indice p tel que les éléments 1 .. p-1 sont inférieurs ou égaux à l'élément pivot et les éléments p .. N-1 sont supérieurs ou égaux à l'élément pivot. Attention, l'une des parties peut être vide, ce qui se traduit soit par p = 1 soit par p = N. Si la partie gauche est vide, alors (car tous les éléments de la partie droite sont supérieurs ou égaux au pivot par définition) il suffit de trier récursivement la partie droite et notre travail est terminé. Si la partie gauche n'est pas vide, alors on échange l'élément numéro 0 (notre pivot) et l'élément numéro p-1 (le dernier élément de la partie gauche). Après cet échange, les éléments 0 .. p-2 sont inférieurs ou égaux à l'élément pivot, l'élément numéro p-1 est égal à l'élément pivot, et les éléments p .. N-1 sont supérieurs ou égaux à l'élément pivot (il est possible que p = N. Maintenant, il suffit de trier récursivement les éléments 0 .. p-2 et les éléments p .. N-1 pour que le tableau entier soit trié.

En fait, même si l'on ne teste pas si la partie gauche est vide, les choses se passent bien. Dans ce cas, on échange élément numéro 0 avec lui même (car p = 1 et on trie récursivement les éléments 0 .. -1 à savoir un intervalle contenant aucun élément.

Choix de l'élément pivot

Dans la version du tri rapide sur les listes ainsi que la version sur les tableaux indiqué ci-dessus, c'est le premier élément qui est choisi comme élément pivot. C'est souvent un très mauvais choix, par exemple si la suite est déjà trié, ou trié en sens inverse. On préfère alors choisir un élément pivot autre que le premier.

En fait, on peut toujours utiliser l'algorithme ci-dessus, même si un autre élément pivot est choisi. Il suffit pour cela de commencer par échanger cet élément par le premier, et on a l'élément pivot au début du tableau, puis d'appliquer l'algorithme ci-dessus.

Un choix typique est l'élément du milieu du tableau, en espérant que sa valeur soit près de la valeur médiane. Ça marche relativement bien en pratique. Un meilleur choix pourrait être de choisir un élément aléatoire du tableau, mais le programme qui en résulte sera toujours plus difficile à mettre au point.

Exemples de code