Page d'accueil
encyclopedie-enligne.com en page d'accueil| Page d'accueil |
encyclopedie-enligne.com en page d'accueil |
|||||
| Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] | Liste Catégories | Une page au hasard | Pages liées | ||||||
Le tri rapide (en anglais quicksort) est une méthode de tri
inventée par C.A. Hoare en 1962 basée sur la méthode de conception diviser pour régner.
| Sommaire |
Elle consiste à placer le premier élément d'un tableau d'éléments à trier (appelé pivot) à sa place définitive en permutant tous les éléments de telle sorte que tous ceux qui lui sont inférieurs soient à sa gauche et que tous ceux qui lui sont supérieurs soient à sa droite. Cette opération s'appelle partitionnement. Pour chacun des sous-tableaux, on définit un nouveau pivot et on répète l'opération de partitionnement. Ce processus est répété récursivement, jusqu'à ce que l'ensemble des éléments soient triés.
tri_rapide(tableau t, entier premier, entier dernier) début si premier < dernier alors pivot <- choix_pivot(t,premier,dernier) pivot <- partitionner(t,premier,dernier,pivot) tri_rapide(t,premier,pivot-1) tri_rapide(t,pivot+1,dernier) finsi fin
Si le pivot est correctement choisi à chaque étape, c'est la méthode de tri la plus rapide connue avec une complexité en O(n ln(n)) dans le cas moyen, mais elle peut se dégrader en O(n²) dans le pire des cas, qui se trouve être le cas où les éléments sont déjà dans l'ordre. Dans la pratique, pour les partitions avec un faible nombre d'éléments (quelques dizaines), on a souvent recours à un tri par insertion qui se révèle plus efficace que le tri rapide.
Grâce à ses bonnes performances et à son implémentation facile (en première approche), quicksort est un des plus populaires algorithmes de tri.
C'est un tri instable car il ne préserve pas nécessairement l'ordre des éléments équivalents.
Le problème le plus important est le choix du pivot. Une implémentation du tri rapide qui n'optimise pas la recherche du pivot sera très inefficace pour certaines entrées. Par exemple, si le pivot est toujours le plus petit élément de la liste, QuickSort sera aussi efficace qu'un tri par sélection, c'est-à-dire de performance O(n²). Un problème lié est le niveau de récursion: dans le pire des cas il peut être linéaire: la pile requiert un espace supplémentaire de O(n).
Le pire cas du tri rapide n'est pas un problème théorique. Quand il est utilisé avec des services Web, par exemple, il est possible pour un attaquant d'utiliser volontairement des données conduisant au pire cas de performance et de provoquer un ralentissement de la machine attaqué voir un arrêt intempestif du programme par débordement de pile.
Des données triées ou partiellement triées sont relativement fréquente dans la pratique et l'implémentation naïve (comme ci-dessus) du tri rapide choisi le premier élément comme pivot ce qui conduit a une profondeur de récursivité linéaire. Pour résoudre ce problème, l'élément du milieu du tableau peut être utilisé. Cette façon de faire fonctionne bien en pratique mais facilite la mise au point d'attaque.
Une meilleur optimisation peut être de sélectionner le pivot aléatoirement entre 2 valeur au centre pour éviter que les hackers puissent prévoir la réaction de votre méthode de tri en fonction des données a trier.
Trouver la valeur médiane de la liste peut être fait si le nombre d'éléments est suffisamment grand pour le justifier mais cela en vaut rarement la peine en pratique.
Une autre optimisation est de changer d'algorithme quand le sous-ensemble de données non encore trié devient petit, 10 éléments ou moins. 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é.
Une implémentation répandue du quicksort, celui de la bibliothèque C de 1997 de Microsoft, passe au tri par insertion pour les listes de 8 éléments ou moins; Microsoft affirme que des essais ont montré que cela est un bon choix. Sur des machines dotées de processeurs modernes des valeurs entre 16 et 32 sont souvent utilisé de nos jours.
Sedgewick 1978 suggère une amélioration 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 1997 considèrent « 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 le taux de succès des caches à cause de la plus large dispersion des accès à la mémoire, ce qui fait que les performances du tri décroissent. 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. Ce travail est cité par Musser.
Étant donné que le tri rapide nécessite de la mémoire supplémentaire pour implémenter la récursion, des variantes non récursives du tri rapide ont été écrites. Elles ont l'avantage d'utiliser la mémoire de façon plus prévisible, indépendante des données a trier, au prix d'une très nette augmentation de la complexité du code. Les programmeurs voulant utiliser un tri itératif peuvent considérer introsort ou le tri par tas.
Une alternative simple pour réduire l'utilisation de la mémoire par un tri rapide utilise une récursion pour la plus petite des sous-listes a trier et une récursion finale (qui peut donc âtre transformé en une boucle) pour la plus grande. Ceci limite la quantité de mémoire utilisé a O(log n). Par exemple:
tri_rapide(a, gauche, droite) tant que droite-gauche+1 > 1 sélectionner une valeur de pivot a[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
Une variante du tri rapide devenu largement utilisé est introsort alias introspective sort Musser 1997. 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. Elle permet d'éviter la complexité du choix d'un bon pivot tout en garantissant une exécution en O(n log n).
Le concurrent le plus direct du tri rapide est le tri par tas. Le tri par tas est typiquement un peu plus lent que le tri rapide mais son plus mauvais comportement est en O(n log n), aussi il est préféré lorsque la complexité maximale doit être garantie ou lorsque l'on soupçonne que le comportement en O(n²) du tri rapide sera souvent atteint (dans le cas plus commun que l'on ne pourrait le penser ou les données à trier le sont déjà presque). Le tri par tas a aussi l'avantage de requérir un espace mémoire additionnel constant tandis que la meilleur variante du tri rapide utilise 0(log n) d'espace mémoire additionnel.
Un algorithme de sélection simple, qui choisit le plus petit des éléments d'une liste, fonctionne globalement de la même manière que le quicksort, la différence étant qu'au lieu de d'être appelé récursivement sur les deux sous-listes, il n'est appelé récursivement que sur la sous-liste contenant l'élément recherché. Cette petite différence fait passer la complexité moyenne à un niveau linéaire, en O(n). Une variante de cet algorithme trouve la valeur médiane à chaque étape, ce qui réduit également le temps d'exécution dans le pire des cas à O(n).
Une mise en œuvre simple de QuickSort sur un tableau d'entiers en C:
void quicksort(int * low, int * high)
{
/* On prend naïvement la première valeur du tableau
comme pivot. */
/* Ceci ne donne pas des performances optimales dans
un contexte d'utilisation réel. */
int * lowbound = low + 1; /* la limite haute du sous-tableau bas */
int * highbound = high - 1; /* la limite basse du sous-tableau haut */
int temp;
while(lowbound <= highbound) /* découpage du tableau */
{
if(*lowbound < *low) /* compare au pivot */
lowbound++; /* remonte lowbound vers le milieu */
else
{
temp = *lowbound; /* échange *lowbound et *highbound */
*lowbound = *highbound;
*highbound = temp;
highbound--; /* descend highbound vers le milieu */
}
}
highbound++; /* remet les limites à leurs positions correctes */
lowbound--;
temp = *low; /* met le pivot au milieu */
*low = *lowbound;
*lowbound = temp;
if(low != lowbound) /* appel récursif sur les sous-tabelaux */
quicksort(low, lowbound);
if(high != highbound)
quicksort(highbound, high);
}
Ici, nous avons une implementation en Python, qui utilise un meilleur partitionnement :
def partition(array, start, end, compare): while start < end: # au début de cette boucle, notre élément permettant la partition # est à la valeur 'start' while start < end: if compare(array[start], array[end]): (array[start], array[end]) = (array[end], array[start]) break end = end - 1 # au début de cette boucle, notre élément permettant la partition # est à la valeur 'end' while start < end: if compare(array[start], array[end]): (array[start], array[end]) = (array[end], array[start]) break start = start + 1 return start def quicksort(array, compare=lambda x, y: x > y, start=None, end=None): """Le plus rapide des tris par échanges pour la plupart des usages.""" if start is None: start = 0 if end is None: end = len(array) if start < end: i = partition(array, start, end-1, compare) quicksort(array, compare, start, i) quicksort(array, compare, i+1, end)
Ici, une version très courte écrite en langage fonctionnel (Haskell):
quicksort :: (Ord a) => [a] -> [a] quicksort [] = [] quicksort (pivot:rest) = (quicksort [y| y<-rest, y<pivot]) ++ [pivot] ++ (quicksort [y| y<-rest,y>=pivot])
La même chose en Python:
def qsort(L): if len(L) <= 1: return L return qsort( [ lt for lt in L[1:] if lt < L[0] ] ) + \ [ L[0] ] + \ qsort( [ ge for ge in L[1:] if ge >= L[0] ] )
Noter l'usage de liste par compréhension ainsi que l'utilisation du premier élément de la liste comme pivot ainsi le
tri n'est pas optimal si la liste est déjà triée où presque triée (on peut optimiser cette version en pré-sélectionnant le pivot
avant d'appeler la fonction de tri). Cette version est très facile à comprendre, elle effectue un tri récursif en filtrant les
éléments plus petits ou plus grands que le pivot et en insérant ce pivot entre les deux sous-listes ainsi formées. Pour les
implémentations existantes du compilateur Haskell cette procédure de tri est inefficace car elle nécessite la copie et la
concaténation de beaucoup de petites sous-listes et est donc de complexité O(n²). Une future implémentation de Haskell pourrait
implémenter de façon transparente des optimisations pour régler ces problèmes mais actuellement ce n'est pas requis par la
définition du langage.
complexité dans le meilleur des cas
|
|
|
à bulle · par sélection · par insertion · par tas · par base · rapide · fusion · comptage |
