Tri rapide

Il existe cependant un meilleur algorithme de tri (Hoare, 1962) appelé tri rapide, en anglais quicksort, qui est utilisé également par l'API Java, pour le tri des tableaux dont les éléments sont de type primitif, par les fonctions Arrays.sort(int[] t), etc. ; 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.

 

  static void échangerÉléments(int[] t, int m, int n) {
    int temp = t[m];

    t[m] = t[n];
    t[n] = temp;
  }

  static int partition(int[] t, int m, int n) {
    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) {
        échangerÉléments(t, i, j);
      } else {
        return j;
      }
    }
  }

  static void triRapide(int[] t, int m, int n) {
    if (m<n) {
      int p = partition(t, m, n);
      triRapide(t, m, p);
      triRapide(t, p+1, n);
    }
  }

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².