1  Le tri quicksort

Le tri quicksort a été introduit par C.A.R. Hoare en 1960. C’est le prototype des méthodes diviser pour résoudre.

On suppose disposer :

• d’un tableau composé d’éléments à trier ;
• d’une fonction f de comparaison de deux éléments du tableau :
  • f retourne 0 si les deux éléments sont équivalents ;
  • f retourne une valeur positive si le premier élément est considéré plus grand que le second ;
  • f retourne une valeur négative sinon.

Principe du tri quicksort.

Le principe du tri quicksort est le suivant : pour trier un tableau, on considère x, le premier élément du tableau. Supposons qu’après manipulation, on réussi à réagencer le tableau en deux zones contiguës :

• la première zone constituée des élémentsy tels quef(y, x) < 0 ;
• la seconde zone constituée des éléments z tels que f(x, z) ≤ 0.

Il suffit de recommencer récursivement la manipulation sur les première et seconde zones du tableau pour trier notre tableau. La récursion prend fin lorsque une zone du tableau est réduite à un élément.

Attention. Aucune copie du tableau n’est faite lors du tri : ce tri est destructif, il altère le tableau à trier.

Une méthode de partitionnement.

Une implantation du tri quicksort réside sur un algorithme de partitionnement d’un tableau en deux zones. Pour partitionner un tableau, on peut opérer comme suit :

• on choisit comme valeur pivot x, la valeur du premier élément comme élément pivot x (on peut aussi choisir n’importe quel autre valeur, par exemple la valeur de l’élément médiant des 3 ou 5 premiers éléments du tableau) ;
• initialement, on considère que montant et descendant référencent respectivement le premier et dernier éléments du tableau ;
• tant que montant est inférieur à decendant, on itère les phases suivantes :
  • incrémenter montant tant que l’élément y référencé est tel que f(y, x)<0 ;
  • décrémenter descendant tant que l’élément z référencé est tel que f(x, z) ≤ 0 ;
  • si montant et descendant se rencontrent, quitter ;
  • échanger les éléments référencés par montant et descendant.
  Pour finir, on échange le pivot et descendant.