Tri rapide

École de technologie supérieure

INF155 Introduction à la programmation
Sylvie Ratté et Hugues Saulnier

#define TAILLE_CRITIQUE_QUICK 10

void quick(double T[],int left,int right)
{ int i = left; int k = right;
  if((k-i)< TAILLE_CRITIQUE_QUICK) {
     triInsertion(T,i,k+1);
     return;
} 

Lorsque la taille restante est inférieure ou égale à 10, on utilise un tri plus simple: le tri par insertion. Cependant, dans l'animation ci-dessous, j'ai poursuivi le tri rapide jusqu'à la taille 2.

  double x = T[(left+right)/2];

Par cette instruction, on va chercher une valeur qui sera utilisée comme pivot.

  do { 
     while (T[i] < x ) i++;
     while ( x < tablo[k]) k--;
     if (i <= k) {
        permute(&T[i],&T[k]);
        i++; k--;
  } while (i < k); 

Voilà le coeur du tri rapide. On fait remonter l'indice de gauche "i" jusqu'à ce que le contenu du tableau soit supérieur ou égal à la valeur pivot. On fait ensuite descendre l'indice de droite "j" jusqu'à ce que le contenu du tableau soit inférieur ou égal à la valeur pivot. On échange ensuite les deux valeurs avec "permute" afin de retrouver la situation suivante: la valeur plus petite que le pivot se retrouve à gauche tandis que la valeur plus grande que le pivot se retrouve à droite. On répète ce processus jusqu'à ce que les deux indices se croisent.

  if (left < k) quick(T,left, k);
  if (i < right) quick(T,i, right);
}

Que doit-on faire des deux morceaux qui restent? Les trier bien sûr. On appelle à nouveau le tri rapide sur la partie gauche puis, sur la partie droite.