Tri rapide

Une manière simple de choisir le pivot est de prendre toujours le premier élément du sous-tableau courant (ou le dernier). Lorsque toutes les permutations possibles des entrées sont équiprobables, la complexité moyenne du tri rapide en sélectionnant le pivot de cette façon est Θ(n log n). Cependant, la complexité dans le cas le pire est Θ(n²), et celle-ci est atteinte lorsque l'entrée est déjà triée ou presque triée[4].

Si on prend comme pivot le milieu du tableau, le résultat est identique, bien que les entrées problématiques soient différentes.

Il est possible d'appliquer une permutation aléatoire au tableau pour éviter que l'algorithme soit systématiquement lent sur certaines entrées. Cependant, cette technique est généralement moins efficace que de choisir le pivot aléatoirement.

Si on utilise la méthode donnée dans la description de l'algorithme, c'est-à-dire choisir le pivot aléatoirement de manière uniforme parmi tous les éléments, alors la complexité moyenne du tri rapide est Θ(n log n) sur n'importe quelle entrée. Dans le pire des cas, la complexité est Θ(n²). Néanmoins, l'écart type de la complexité est seulement Θ(n), ce qui signifie que l'algorithme s'écarte peu du temps d'exécution moyen[5].

Dans le cas le meilleur, l'algorithme est en Θ(n log n).

On donne une preuve de la complexité temporelle moyenne du tri rapide d'un tableau de taille ${\displaystyle n}$[4].

On note ${\displaystyle z_{1},\dots ,z_{n}}$ les éléments du tableau donnés par ordre croissant. Pour ${\displaystyle i<j}$ on note ${\displaystyle Z_{ij}=\{z_{i},z_{i+1},\dots ,z_{j}\}}$. Initialement, le tableau à trier est ${\displaystyle z_{\sigma (1)},\dots ,z_{\sigma (n)}}$ où ${\displaystyle \sigma }$ est une permutation des entiers compris entre 1 et ${\displaystyle n}$.

Les opérations à effectuer sont les choix de pivot et les comparaisons qui ont lieu lors des partitions autour de chaque pivot. Dès lors qu'un pivot est choisi il n'est plus impliqué dans les partitions qui suivent et donc une exécution de l'algorithme fait intervenir au plus ${\displaystyle n}$ choix de pivot, et chaque choix se fait en temps constant. De plus tout élément est comparé à un élément au plus une fois, car tout élément n'est comparé qu'à un pivot, et une fois effectuée la partition autour d'un pivot donné, celui-ci n'intervient plus dans l'exécution de l'algorithme une fois la partition finie. En notant ${\displaystyle X}$ le nombre total de comparaison on obtient que la complexité d'une exécution est donc ${\displaystyle O(X+n)}$. De plus si l'on note ${\displaystyle X_{ij}}$ la variable aléatoire qui vaut 1 si ${\displaystyle z_{i}}$ est comparé à ${\displaystyle z_{j}}$ et 0 sinon, on déduit que l'on a pour une exécution donnée ${\displaystyle X=\sum _{i=1}^{n-1}\sum _{j=i+1}^{n}X_{ij}}$. On cherche à calculer ${\displaystyle {\mathtt {E}}[X]}$ l'espérance de ${\displaystyle X}$. C'est-à-dire ${\displaystyle {\mathtt {E}}[X]=\sum _{i=1}^{n-1}\sum _{j=i+1}^{n}\mathbb {P} \{{\text{L'algorithme compare }}z_{i}{\text{et }}z_{j}\}}$.

Or ${\displaystyle z_{i}}$ est comparé à ${\displaystyle z_{j}}$ si et seulement si le premier élément de ${\displaystyle Z_{ij}}$ à être choisi comme pivot est soit ${\displaystyle z_{i}}$ soit ${\displaystyle z_{j}}$. En effet si c'est un autre élément qui est choisi en premier comme pivot, alors ${\displaystyle z_{i}}$ et ${\displaystyle z_{j}}$ sont envoyés dans deux sous-tableaux différents de la partition, et les comparaisons sont effectuées exclusivement entre éléments d'un même sous-tableau. De plus la probabilité que le premier élément de ${\displaystyle Z_{ij}}$ à être choisi comme pivot soit ${\displaystyle z_{i}}$ ou ${\displaystyle z_{j}}$ vaut ${\displaystyle {\frac {2}{j-i+1}}}$ car les choix de pivot sont équiprobables et mutuellement exclusifs, et car ${\displaystyle Z_{ij}}$ contient ${\displaystyle j-i+1}$ éléments.

On a donc ${\displaystyle {\mathtt {E}}[X]=\sum _{i=1}^{n-1}\sum _{j=i+1}^{n}{\frac {2}{j-i+1}}=\sum _{i=1}^{n-1}\sum _{k=1}^{n-i}{\frac {2}{k+1}}}$.

Or ${\displaystyle \sum _{k=1}^{n-i}{\frac {2}{k+1}}\leq \sum _{k=1}^{n}{\frac {2}{k}}=O(\log(n))}$ (c'est une propriété de la série harmonique).

Par conséquent ${\displaystyle {\mathtt {E}}[X]=\sum _{i=1}^{n-1}O(\log(n))=O(n\log(n))}$.

La complexité moyenne du tri rapide lorsque le pivot est choisi aléatoirement est donc ${\displaystyle O(n\log(n))}$.

En théorie, on pourrait faire en sorte que la complexité de l'algorithme soit Θ(n log n) dans le pire cas en prenant comme pivot la valeur médiane du sous-tableau. En effet, dans ce cas l'arbre des appels récursifs de l'algorithme a une hauteur égale à ${\displaystyle {\mathtt {log}}_{2}(n)}$ et chacun de ses étages a la complexité ${\displaystyle \theta (n)}$. L'algorithme BFPRT ou médiane des médianes permet en effet de calculer cette médiane de façon déterministe en temps linéaire[6].

Mais l'algorithme n'est pas suffisamment efficace dans la pratique, et cette variante est peu utilisée.

Il existe un algorithme de partitionnement plus complexe, qui réduit le nombre d'échanges effectués lors du partitionnement. De plus, les éléments égaux au pivot sont mieux répartis des deux côtés de celui-ci qu'avec l'algorithme précédent. Ainsi, l'algorithme reste en Θ(n log n) même sur un tableau dont tous les éléments sont identiques.

Le principe de l'algorithme est le suivant :

• Trouver le plus petit i tel que T[i] soit supérieur ou égal au pivot.
• Trouver le plus grand j tel que T[j] soit inférieur ou égal au pivot.
• Si i<j, échanger T[i] et T[j] puis recommencer.

Il est possible de formaliser cet algorithme de sorte qu'il soit linéaire :

partitionner(tableau T, premier, dernier, pivot)
    échanger T[pivot] et T[premier]
    i = premier + 1, j = dernier
    tant que i < j
        tant que i < j et T[i] < T[premier], faire i := i + 1
        tant que i < j et T[j] > T[premier], faire j := j - 1
        échanger T[i] et T[j]
        i := i + 1, j := j - 1
    fin tant que
    ''// le tableau est à présent en 3 parties consécutives : pivot, partie gauche, partie droite''
    ''// dans partie gauche, tous les éléments sont <= pivot''
    ''// dans partie droite, tous les éléments sont >= pivot''
    ''// mais les deux parties peuvent se chevaucher : i-j peut être 0, 1 ou 2''
    ''// il faut replacer le pivot entre les 2 parties et retourner l'indice du pivot : c'est assez compliqué...''
    ''// il vaut mieux laisser le pivot à sa place au départ et le déplacer en cas de chevauchement :''

Une optimisation utile consiste à changer d'algorithme lorsque le sous-ensemble de données non encore trié devient petit. La taille optimale des sous-listes dépend du matériel et des logiciels utilisés, mais est de l'ordre de 15 éléments. On peut alors utiliser le tri par sélection ou le tri par insertion. Le tri par sélection ne sera sûrement pas efficace pour un grand nombre de données, mais il est souvent plus rapide que le tri rapide sur des listes courtes, du fait de sa plus grande simplicité.

Robert Sedgewick suggère une amélioration (appelée Sedgesort) lorsqu'on utilise un tri simplifié pour les petites sous-listes[7] : on peut diminuer le nombre d'opérations nécessaires en différant le tri des petites sous-listes après la fin du tri rapide, après quoi on exécute un tri par insertion sur le tableau entier.

LaMarca et Ladner ont étudié « l'influence des caches sur les performances des tris »[8], un problème prépondérant sur les architectures récentes dotées de hiérarchies de caches avec des temps de latence élevés lors des échecs de recherche de données dans les caches. Ils concluent que, bien que l'optimisation de Sedgewick diminue le nombre d'instructions exécutées, elle diminue aussi le taux de succès des caches à cause de la plus large dispersion des accès à la mémoire (lorsque l'on fait le tri par insertion à la fin sur tout le tableau et non au fur et à mesure), ce qui entraîne une dégradation des performances du tri. Toutefois l'effet n'est pas dramatique et ne devient significatif qu'avec des tableaux de plus de 4 millions d'éléments de 64 bits. Cette étude est citée par Musser.

Une variante du tri rapide devenue largement utilisée^{[réf. nécessaire]} est introsort alias introspective sort[9]. Elle démarre avec un tri rapide puis utilise un tri par tas lorsque la profondeur de récursivité dépasse une certaine limite prédéfinie. Ainsi, sa complexité dans le cas le pire est Θ(n log n).

Une mise en œuvre naïve du tri rapide utilise un espace mémoire proportionnel à la taille du tableau dans le pire des cas. Il est possible de limiter la quantité de mémoire à Θ(log n) dans tous les cas en faisant le premier appel récursif sur la liste la plus petite. Le second appel récursif, situé à la fin de la procédure, est récursif terminal. Il peut donc être transformé en itération de la manière suivante :

tri_rapide(T, gauche, droite)
    tant que droite-gauche+1 > 1
        sélectionner un pivot T[pivotIndex]
        pivotNewIndex := partition(T, gauche, droit, pivotIndex)
        si pivotNewIndex-1 - gauche < droit - (pivotNewIndex+1)
            tri_rapide(T, gauche, pivotNewIndex-1)
            gauche := pivotNewIndex+1
        sinon
            tri_rapide(T, pivotNewIndex+1, droit)
            droit := pivotNewIndex-1
        fin_si
   fin_tant_que

Un algorithme inspiré du tri rapide appelé Quickselect, fonctionnant en temps linéaire en moyenne, permet de déterminer le k-ème plus petit élément dans un tableau. Un cas particulier notable est k=n/2, qui correspond à la recherche de la médiane.

Le principe de l'algorithme Quickselect est le suivant : à chaque étape, on réalise une partition selon un pivot choisi aléatoirement. Une fois la partition effectuée, il est possible de savoir de quel côté de la partition se trouve le k-ème élément (ou bien si c'est le pivot lui-même). Dans le cas où le pivot n'est pas le k-ème élément, on appelle récursivement l'algorithme, mais seulement du côté où se trouve l'élément. À la fin de l'algorithme, le k-ème élément du tableau est alors le k-ème plus petit élément du tableau.

• Loi de Bernoulli, en particulier la section « Coût moyen de l'algorithme de tri rapide ».
• Quickselect, l'algorithme de sélection associé à Quicksort.

• (en) Simulation en Java
• (fr) QuickSort « pour les nuls »
• (en) Illustration dynamique du tri rapide
• (en) Quick-sort, HeapSort et autres algorithmes avec lecteur de visualisation du tri

• Portail de l’informatique
• Portail de l'informatique théorique