Tri rapide - Définition

Variantes et optimisations

Algorithme de partitionnement alternatif

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 O(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      

Combinaison avec d'autres algorithmes de tri

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 : 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 », 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 entraine 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. 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 pire cas est O(n log n).

Espace mémoire

Une implémentation naïve du tri rapide utilise un espace mémoire proportionnel à la taille du tableau dans le pire cas. Il est possible de limiter la quantité de mémoire à O(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(a, gauche, droit, pivotIndex)              si pivotNewIndex-1 - gauche < droit - (pivotNewIndex+1)                  tri_rapide(a, gauche, pivotNewIndex-1)                  gauche:= pivotNewIndex+1              sinon                  tri_rapide(a, pivotNewIndex+1, droit)                  droit:= pivotNewIndex-1              fin_si         fin_tant_que      

Variante pour la sélection d'élément

Une variante du tri rapide, 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 modifié 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.