Calcul de la complexité

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

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))}$.

Traitement spécial des petits sous-problèmes

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^[8] : 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 »^[9], 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.

Introsort

Une variante du tri rapide devenue largement utilisée est introsort alias introspective sort^[10]. 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).