Quicksort

En appliquant la méthode << diviser pour régner >> au problème du tri d'une table, on obtient facilement le tri par fusion : on divise une table de longueur $n$ en deux tables de longueur $n/2$, on trie, récursivement, ces deux tables, puis on fusionne les tables triées. Comme la fusion de deux tables ordonnées de longueur $n/2$ se fait en $\Theta(n)$, l'équation de complexité est $T(n) = 2T(n/2) + \Theta(n)$, dont la solution est en $\Theta(n\log n)$.

Il existe cependant un meilleur algorithme de tri, dû à C.A.R. Hoare (1962) et appelé tri rapide, en anglais quicksort; il diffère du tri par fusion en ce que la décomposition en deux tables est calculée, la recomposition des tables triées étant immédiate. Cette décomposition se fait par une fonction partition, qui choisit un élément de la table, appelé pivot, réorganise la table en déplaçant tous les éléments plus petits que le pivot à la gauche du pivot et tous les éléments plus grands à sa droite, et retourne l'indice de l'élément pivot après réorganisation.

namespace {
  void array_swap(int t[], int m, int n) {
    int temp = t[m];
  
    t[m] = t[n];
    t[n] = temp;
  }
  
  int partition(int m, int n, int t[]) {
    int v = t[m];                 // valeur pivot 
    int i = m-1;
    int j = n+1;         // indice final du pivot 
  
    while (true) {
      do {
        j--;
      } while (t[j] > v);
      do {
        i++;
      } while (t[i] < v);
      if (i<j) {
        array_swap(t, i, j);
      } else {
        return j;
      }
    }
  }
}

void quicksort(int m, int n, int t[]) {
  if (m<n) {
    int p = partition(m,n,t);

    quicksort(m,p,t);
    quicksort(p+1,n,t);
  }
}

Les fonctions auxiliaires array_swap et partition sont rendues privées en les regroupant dans un namespace anonyme (en C, on les aurait dû les déclarer static) pour qu'elles ne soient pas connues hors de ce fichier ; par contre, quicksort est publique.

La fonction partition, qui est pourtant itérative, est la partie difficile à écrire : celle-ci choisit comme pivot le premier élément de chaque tableau. Sa complexité est en $\Theta(n)$.

Testé sur trois tableaux de taille 1000 dont les éléments sont respectivement, générés aléatoirement, générés par ordre croissant, générés par ordre décroissant, le nombre d'échanges d'éléments observé est respectivement : 5477, 999, et 250 999.

On montre en effet, sous des hypothèses d'uniformité, que la complexité moyenne du tri rapide est en $\Theta(n\log n)$ ; en pratique, son comportement est même meilleur que celui du tri par fusion (car la constante devant $n\log n$ est plus petite). Mais comme il n'y aucune raison pour que la partition décompose une table de longueur $n$ en deux tables de longueur $n/2$, la complexité dans le pire des cas est très mauvaise, puisqu'elle est en $n^2$. Cependant, ces cas extrêmes sont rares, sous des conditions d'uniformité des données.