Le tri rapide : QSort

Bon, alors cet algorithme a un principe un peu original si vous êtes habitués au tri à bulles ou au tri par sélection. En fait, l'idée, c'est de séparer votre tableau en deux. Pour cela, on choisit une valeur de notre tableau de base, qu'on appelle pivot. Le pivot est souvent la valeur de la première case du tableau. On construit alors deux « sous-tableaux » : l'un contient toutes les valeurs du premier tableaux qui sont inférieures ou égales au pivot, l'autre contient les valeurs supérieures au pivot.


Non, il ne l'est pas. Mais il est déja un peu plus « rangé ». Afin de terminer le tri, il vous suffira de retrier chacun des deux sous-tableaux avec qsort, puis de concaténer les deux tableaux (cela signifie les mettre bout à bout, comme strcat le fait avec les chaînes de caractères en C).

Comme vous pouvez le voir, l'algorithme du tri rapide s'utilise lui même. On dit que c'est un algorithme récursif (Bluestorm a écrit un tutoriel sur la récursivité pour ceux que ça intéresse). Le dernier problème est donc de savoir quand-est ce qu'on arrête d'appeller récursivement QSort... La réponse est très simple : quand il n'y a plus rien à trier (c'est à dire, quand les sous-tableaux restants sont soit des singletons, soit vides) !

Un petit exemple ?

Prenons cette liste :

Code : Console

Ici, je vais choisir comme pivot 37. En effet, il y a deux valeurs au dessus (38 et 42) et deux valeurs au dessous (5 et 21). C'est donc une valeur médiane, ce qui convient très bien pour un pivot (on verra que le principal problème de l'implémentation de quicksort est le choix du pivot). On prend donc la case 37 comme pivot et on fait passer de l'autre côté du pivot les valeurs qui ne sont pas à leur place :

Code : Console
Ici, on voit la liste initiale séparée en deux : au milieu, le pivot, 37. A gauche, les valeurs inférieures à 37 (<37) ont été insérées. De même à droite pour les valeurs supérieures à 37 (>37).

Bon, maintenant, on est sûrs que le 37 est à sa position définitive : il ne bougera plus. En effet, toutes les valeurs qui lui sont inférieures sont à sa gauche, et les autres sont à droite.

Vous pouvez donc recommencer à appliquer le tri rapide pour les deux sous-listes restantes : (21, 5) et (42, 38). Cependant, dites vous bien que dans un certain nombre de cas, quand on arrive à des sous-listes de cette taille, elles sont déjà « naturellement » triées (ceci dépend de l'implementation). Pour tout vous dire, j'en ai bavé pour trouver un exemple de liste qui ne soit pas trié immédiatement .

Code : Console
Ce schéma montre les deux quickSorts appliqués chacun à une des sous-listes. On voit ici ces deux quickSorts effectués simultanément, juste après le choix du pivot, et avant le déplacement des valeurs de part et d'autres de ceux-ci.

Comme vous le voyez, on trie les deux listes complètement indépendamment. Bon, ici je me force à choisir un pivot et tout, mais il existe des variantes de QSort qui, à un certain stade, changent d'algorithme pour trier les sous-listes qui restent.
Une fois qu'on a fini le tri des deux sous-listes restantes, on obtient donc ceci :

Code : Console
Les deux quickSorts précédents, après l'étape de déplacement des valeurs. On remarque que les groupes de nombres entre les pivots sont soit des singletons, soit vides. QuickSort est donc terminé.

Nous sommes sûrs que les nombres 21, 37 et 38 sont à leur place définitive. En l'occurrence, il se trouve que la liste est triée. En effet, les sous-listes qui restent ne font qu'un nombre de long. On arrête donc de trier récursivement...

Voilà, vous avez saisi l'astuce ?



Il existe une implémentation du tri rapide qui est en place (c'est à dire qu'elle n'utilise aucune mémoire supplémentaire, en dehors de celle du tableau initial). Elle élimine donc pas mal de problèmes d'utilisation de mémoire et de puissance de calcul.

Cependant, nous verrons d'abord comment implémenter une version « simple » de Qsort. Tout ça se passe dans la sous-partie suivante... En avant !

Bon allez, implémentons tout ça.

QSort simple en OCaml

En premier lieu, nous allons implémenter un QSort qui obéit à la lettre à la définition de la sous-partie 1. Comme on l'a vu, cette implémentation risque d'être assez lourde à gérer à cause de tous les sous-tableaux. Pourtant, il est possible d'exprimer quicksort de façon très simple dans certains langages. Observons par exemple cette implémentation en OCaml par Bluestorm (si vous ne conaissez rien au OCaml, voyez par là, là, et sur google).

Code : OCaml

Ce code commence par déclarer la fonction qsort, récursive, qui prend un paramètre (liste), et qui regarde quelle est la structure de la liste (c'est le match liste with). Il y a alors plusieurs cas possibles :

• Si c'est une liste vide ou à un seul élément, alors on retourne la liste elle même
• Sinon, on appelle pivot le 1er élément de la liste, et reste le reste ;
  puis on partitionne le reste en deux listes, début et fin, en utilisant l'expression a < pivot pour décider dans quelle liste placer chaque élément a ;
  et enfin, on met bout à bout (c'est l'opérateur @) debut, le pivot, et fin, en appelant qsort sur debut et fin avant.

On voit donc que l'algorithme du tri rapide s'exprime de manière très simple et concise en OCaml. Ce code est sans doute « traduisible » en C, mais la partie « partition de la liste » risque d'être bien lourde à écrire. Il doit bien exister une autre solution pour les langages impératifs...

Une autre implémentation, en C

L'idée est extrêmement simple. Plutôt que de créer un nouveau tableau à chaque fois pour appeller récursivement qsort dessus, nous allons travailler sur un seul et unique tableau : celui qu'on nous fournit au départ.



Voici l'astuce : nous allons faire une fonction quickSort() qui prend trois paramètres, comme ceci :

Code : C

Le premier est bien évidemment le tableau à trier. Quant au second et au troisième, ce sont des indices (c'est à dire des numéros de cases). La fonction quickSort se chargera donc de trier le tableau entre la case numéro debut et la case numéro fin ! Pour appeler récursivement quickSort par la suite, il suffira de la rappeller avec le même tableau et les debut/fin qui vont bien. Plus besoin de créer des sous-tableaux !

Le seul obstacle qu'il nous reste : comment se débrouiller pour faire passer toutes les valeurs inférieures au pivot à sa gauche, et toutes les valeurs supérieures à sa droite ? Déjà, mettons nous d'accord tout de suite : dans un but de simplification, nous prendrons comme pivot la première case du tableau.

Ensuite, nous allons faire deux for. L'un d'entre eux parcourra le tableau de gauche à droite à la recherche d'un élément supérieur au pivot dans la partie gauche du tableau (qui n'est donc pas à sa place) ; l'autre parcourra le tableau de droite à gauche à la recherche d'un élément inférieur au pivot dans la partie droite du tableau.

Dès que les deux for ont chacun trouvé un élément, on permute ces deux éléments. Puis on recommence, jusqu'à ce que les for se « croisent » (l'indice du premier for est supérieur à celui du second). À ce moment, le tableau est prêt : on peut mettre le pivot à sa place définitive, puis appeller récursivement quickSort (en se servant des indices des for pour trouver les nouveaux débuts/fin).

Compliqué ? Je vous l'accorde. Voici l'implémentation. Je vous recommande de la faire tourner avec différents tableaux, en y rajoutant des printf un peu partout pour comprendre ce qui se passe.

Code : C

Que vous pouvez appeller comme ceci :

Code : C

Bonne lecture et bonne prise de tête !



Dans la dernière partie, nous verrons les performances et optimisations possibles de quickSort...

Cet algorithme s'appelle le « tri rapide ». Alors rapide, rapide, c'est vite dit. Dans quelle mesure est-il rapide ?

Une faible complexité

Nous allons ici regarder la complexité de l'algorithme. Pour ceux qui ne connaissent pas, je m'auto-cite :

Citation : GuilOooo

Provient de la sous partie III du tuto sur le tri à paniers.

La complexité de cet algorithme est plus difficile à évaluer que celle du tri à paniers, cependant. Il faut faire un peu de maths, et fournir des explications accessibles n'est pas toujours facile. Alors, de peur de vous dire une bêtise, je ne vais pas rentrer ici dans le détail.

On sait que, dans la plupart des cas, nous allons avoir environ 1.38*N*log(N) opérations à réaliser pour N cases à trier. Ce qui nous donne, si on simplifie en enlevant les constantes, une complexité de O(N*log(N)). (On note O( nombre ) la complexité d'un algorithme). Cette complexité est très compétitive.

Cependant, dans certains cas, la complexité peut tomber à O(N²), qui est déjà bien plus mauvaise. Simplement, ce cas de figure ne survient pas souvent : il faudrait donner une liste presque déjà triée à QSort pour qu'il galère ainsi et nous donne ce mauvais score. Ainsi, si vous avez souvent des listes quasiment déjà triées à manipuler, vous pouvez vous rabattre sur le tri par insertion ou par paniers. Dans les autres cas, notre cher tri rapide fera l'affaire.

Comment optimiser le tri rapide ?

On a donc vu que ce tri était rapide en théorie. En pratique, ça dépendra avant tout de l'implémentation que vous allez utiliser. Voici quelques optimisations possibles, en vrac, sans explications sur le pourquoi du comment (certaines sont triviales, d'autres moins).

• Mélanger le tableau aléatoirement avant de le trier. Ça paraît débile, mais QSort adore les tableaux bien mélangés et a horreur de ceux déjà presque triés. En utilisant un mélange avant QSort, on augmente les chances d'avoir une liste très désordonnée.
• Lors des appels récursifs, trier d'abord le sous-tableau le plus long et ensuite le sous-tableau le moins long. C'est juste un test de plus, et ça peut accélerer le tri (ne me demandez pas pourquoi...)
• Utiliser un autre algorithme de tri sur les sous-tableaux quand ils deviennent trop petits. Certains algorithmes sont plus efficaces que QuickSort sur de petits tableaux.
• Choisir un bon pivot, idéalement la médiane du tableau. Ce n'est cependant pas possible si on trie autre chose que des nombres, et ça peut être complexe à gérer.
• Vous pouvez essayer de mettre chacun des deux appels récursifs à quickSort dans un thread séparé, afin de faire les deux tris simultanément. Ceci n'est profitable qu'avec un double core ou deux processeurs.

Chacune de ces optimisations a des avantages et des inconvéniants (elles accélèrent le tri au prix d'opérations préalables qui peuvent être lentes) et sont donc à utiliser seulement si le besoin s'en fait ressentir.