Tri rapide - Quicksort

Tri rapide
	Visualisation animée de l'algorithme de tri rapide. Les lignes horizontales sont des valeurs de pivot.
Classer	Algorithme de tri
Performances dans le pire des cas
Le meilleur cas la performance	(partition simple) ; ou ( partition à trois voies et clés égales)
Performances moyennes
Complexité spatiale dans le pire des cas	auxiliaire (naïf) auxiliaire (Hoare 1962);

Quicksort est un algorithme de tri sur place . Développé par l'informaticien britannique Tony Hoare en 1959 et publié en 1961, il s'agit toujours d'un algorithme de tri couramment utilisé. Lorsqu'il est bien implémenté, il peut être un peu plus rapide que le tri par fusion et environ deux ou trois fois plus rapide que le tri par tas .

Quicksort est un algorithme diviser pour régner . Il fonctionne en sélectionnant un élément « pivot » dans le tableau et en partitionnant les autres éléments en deux sous-tableaux, selon qu'ils sont inférieurs ou supérieurs au pivot. Pour cette raison, il est parfois appelé tri d'échange de partition . Les sous-tableaux sont ensuite triés récursivement . Cela peut être fait sur place , ce qui nécessite de petites quantités de mémoire supplémentaires pour effectuer le tri.

Quicksort est un tri de comparaison , ce qui signifie qu'il peut trier des éléments de tout type pour lesquels une relation "inférieure à" (formellement, un ordre total ) est définie. Les implémentations efficaces de Quicksort ne sont pas un tri stable , ce qui signifie que l'ordre relatif des éléments de tri égaux n'est pas conservé.

L'analyse mathématique du tri rapide montre qu'en moyenne , l'algorithme prend O ( n log n ) comparaisons pour trier n éléments. Dans le pire des cas , il fait O( n ² ) comparaisons.

Histoire

L'algorithme de tri rapide a été développé en 1959 par Tony Hoare alors qu'il était étudiant invité à l'Université d'État de Moscou . À cette époque, Hoare travaillait sur un projet de traduction automatique pour le National Physical Laboratory . Dans le cadre du processus de traduction, il devait trier les mots dans des phrases russes avant de les rechercher dans un dictionnaire russe-anglais, classé par ordre alphabétique sur une bande magnétique . Après avoir reconnu que sa première idée, le tri par insertion , serait lente, il a proposé une nouvelle idée. Il a écrit la partie partition dans Mercury Autocode mais a eu du mal à gérer la liste des segments non triés. De retour en Angleterre, on lui a demandé d'écrire du code pour Shellsort . Hoare a mentionné à son patron qu'il connaissait un algorithme plus rapide et son patron a parié six pence qu'il n'en avait pas. Son patron a finalement accepté qu'il avait perdu le pari. Plus tard, Hoare a découvert ALGOL et sa capacité à faire de la récursivité, ce qui lui a permis de publier le code dans Communications of the Association for Computing Machinery , le premier journal d'informatique de l'époque.

Quicksort a été largement adopté, apparaissant, par exemple, dans Unix comme sous-programme de tri de bibliothèque par défaut. Par conséquent, il a prêté son nom au sous-programme de bibliothèque standard C qsort et à l'implémentation de référence de Java .

La thèse de doctorat de Robert Sedgewick en 1975 est considérée comme une étape importante dans l' étude de Quicksort où il a résolu de nombreux problèmes ouverts liés à l' analyse de divers schémas de sélection pivot , y compris Samplesort , le partitionnement adaptatif par Van Emden ainsi que la dérivation du nombre attendu de comparaisons et échanges. Jon Bentley et Doug McIlroy ont incorporé diverses améliorations à utiliser dans les bibliothèques de programmation, y compris une technique pour traiter des éléments égaux et un schéma pivot connu sous le nom de pseudomédiane de neuf, où un échantillon de neuf éléments est divisé en groupes de trois, puis la médiane du trois médianes de trois groupes sont choisies. Bentley a décrit un autre schéma de partitionnement plus simple et compact dans son livre Programming Pearls qu'il a attribué à Nico Lomuto. Plus tard, Bentley a écrit qu'il avait utilisé la version de Hoare pendant des années mais ne l'avait jamais vraiment comprise, mais la version de Lomuto était suffisamment simple pour être correcte. Bentley a décrit Quicksort comme le « plus beau code que j'aie jamais écrit » dans le même essai. Le schéma de partition de Lomuto a également été popularisé par le manuel Introduction to Algorithms bien qu'il soit inférieur au schéma de Hoare car il effectue trois fois plus d'échanges en moyenne et se dégrade en $O (n 2)$ lorsque tous les éléments sont égaux.

En 2009, Vladimir Yaroslavskiy a proposé une nouvelle implémentation Quicksort utilisant deux pivots au lieu d'un. Dans les listes de diffusion de la bibliothèque de base Java, il a lancé une discussion affirmant que son nouvel algorithme était supérieur à la méthode de tri de la bibliothèque d'exécution, qui était à l'époque basée sur la variante largement utilisée et soigneusement réglée du classique Quicksort par Bentley et McIlroy. Le Quicksort de Yaroslavskiy a été choisi comme nouvel algorithme de tri par défaut dans la bibliothèque d'exécution Java 7 d'Oracle après des tests de performances empiriques approfondis.

Algorithme

Exemple complet de tri rapide sur un ensemble aléatoire de nombres. L'élément ombré est le pivot. Il est toujours choisi comme dernier élément de la partition. Cependant, toujours choisir le dernier élément de la partition comme pivot de cette manière entraîne de mauvaises performances (

O (n 2)

) sur des tableaux déjà triés , ou des tableaux d'éléments identiques. Étant donné que les sous-tableaux d'éléments triés / identiques surgissent beaucoup vers la fin d'une procédure de tri sur un grand ensemble, les versions de l'algorithme de tri rapide qui choisissent le pivot comme élément central s'exécutent beaucoup plus rapidement que l'algorithme décrit dans ce diagramme sur grands ensembles de nombres.

Quicksort est un type d' algorithme de division pour régner pour trier un tableau, basé sur une routine de partitionnement ; les détails de ce partitionnement peuvent varier quelque peu, de sorte que quicksort est en réalité une famille d'algorithmes étroitement liés. Appliqué à une plage d'au moins deux éléments, le partitionnement produit une division en deux sous-plages consécutives non vides, de telle sorte qu'aucun élément de la première sous-plage n'est supérieur à un élément quelconque de la deuxième sous-plage. Après avoir appliqué cette partition, quicksort trie alors récursivement les sous-gammes, éventuellement après en avoir exclu un élément au point de division qui est à ce point connu pour être déjà dans son emplacement final. En raison de sa nature récursive, le tri rapide (comme la routine de partition) doit être formulé de manière à pouvoir être appelé pour une plage dans un tableau plus grand, même si le but ultime est de trier un tableau complet. Les étapes du tri rapide sur place sont les suivantes :

Si la plage comporte moins de deux éléments, revenez immédiatement car il n'y a rien à faire. Peut-être pour d'autres longueurs très courtes, une méthode de tri spécifique est appliquée et le reste de ces étapes est ignoré.
Sinon, choisissez une valeur, appelée pivot , qui se produit dans la plage (la manière précise de choisir dépend de la routine de partition et peut impliquer un caractère aléatoire).
Partitionner la plage : réorganiser ses éléments, tout en déterminant un point de division, de sorte que tous les éléments avec des valeurs inférieures au pivot viennent avant la division, tandis que tous les éléments avec des valeurs supérieures au pivot viennent après ; les éléments qui sont égaux au pivot peuvent aller dans les deux sens. Puisqu'au moins une instance du pivot est présente, la plupart des routines de partition garantissent que la valeur qui se termine au point de division est égale au pivot, et est maintenant dans sa position finale (mais la fin du tri rapide n'en dépend pas, tant que des sous-gammes strictement inférieures à l'original sont produites).
Appliquer récursivement le tri rapide à la sous-plage jusqu'au point de division et à la sous-plage après, en excluant éventuellement des deux plages l'élément égal au pivot au point de division. (Si la partition produit une sous-plage éventuellement plus grande près de la limite où tous les éléments sont connus pour être égaux au pivot, ceux-ci peuvent également être exclus.)

Le choix de la routine de partition (y compris la sélection du pivot) et d'autres détails non entièrement spécifiés ci-dessus peuvent affecter les performances de l'algorithme, peut-être dans une large mesure pour des tableaux d'entrée spécifiques. En discutant de l'efficacité du tri rapide, il est donc nécessaire de spécifier ces choix en premier. Nous mentionnons ici deux méthodes de partition spécifiques.

Schéma de partition Lomuto

Ce schéma est attribué à Nico Lomuto et popularisé par Bentley dans son livre Programming Pearls et Cormen et al. dans leur livre Introduction aux algorithmes . Ce schéma choisit un pivot qui est généralement le dernier élément du tableau. L'algorithme maintient l'index i pendant qu'il parcourt le tableau en utilisant un autre index j tel que les éléments de lo à i-1 (inclus) sont inférieurs au pivot, et les éléments de i à j (inclus) sont égaux ou supérieurs au pivot. Comme ce schéma est plus compact et facile à comprendre, il est fréquemment utilisé dans le matériel d'introduction, bien qu'il soit moins efficace que le schéma original de Hoare, par exemple, lorsque tous les éléments sont égaux. Ce schéma se dégrade en $O (n 2)$ lorsque le tableau est déjà en ordre. Diverses variantes ont été proposées pour améliorer les performances, notamment différentes manières de sélectionner le pivot, de traiter des éléments égaux, d'utiliser d'autres algorithmes de tri tels que le tri par insertion pour les petits tableaux, etc. Dans le pseudocode , un quicksort qui trie les éléments de lo à hi (inclus) d'un tableau $A$ peut être exprimé sous la forme :

// Sorts a (portion of an) array, divides it into partitions, then sorts those
algorithm quicksort(A, lo, hi) is 
  // If indices are in correct order
  if lo >= 0 && hi >= 0 && lo < hi then 
    // Partition array and get pivot index
    p := partition(A, lo, hi) 
      
    // Sort the two partitions
    quicksort(A, lo, p - 1) // Left side of pivot
    quicksort(A, p + 1, hi) // Right side of pivot

// Divides array into two partitions
algorithm partition(A, lo, hi) is 
  pivot := A[hi] // The pivot must be the last element

  // Pivot index
  i := lo - 1

  for j := lo to hi do 
    // If the current element is less than or equal to the pivot
    if A[j] <= pivot then 
      // Move the pivot index forward
      i := i + 1

      // Swap the current element with the element at the pivot
      swap A[i] with A[j] 
  return i // the pivot index

Le tri de l'ensemble du tableau est effectué par quicksort(A, 0, length(A) - 1) .

Schéma de partition Hoare

Une démonstration animée de Quicksort utilisant le schéma de partition de Hoare. Les contours rouges montrent les positions des pointeurs gauche et droit ( iet jrespectivement), les contours noirs montrent les positions des éléments triés et le carré noir rempli montre la valeur comparée à ( pivot).

Le schéma de partition original décrit par Tony Hoare utilise deux pointeurs (indices dans la plage) qui commencent aux deux extrémités du tableau en cours de partition, puis se déplacent l'un vers l'autre, jusqu'à ce qu'ils détectent une inversion : une paire d'éléments, un plus grand que la limite (termes de Hoare pour la valeur pivot) au premier pointeur, et un de moins que la limite au deuxième pointeur ; si à ce stade le premier pointeur est encore avant le second, ces éléments sont dans le mauvais ordre les uns par rapport aux autres, et ils sont alors échangés. Après cela, les pointeurs sont déplacés vers l'intérieur et la recherche d'une inversion est répétée ; lorsque finalement les pointeurs se croisent (les premiers points après le second), aucun échange n'est effectué ; une partition valide est trouvée, avec le point de division entre les pointeurs croisés (toutes les entrées qui pourraient être strictement entre les pointeurs croisés sont égales au pivot et peuvent être exclues des deux sous-plages formées). Avec cette formulation, il est possible qu'une sous-gamme s'avère être toute la gamme d'origine, ce qui empêcherait l'algorithme d'avancer. Hoare stipule donc qu'à la fin, la sous-gamme contenant l'élément pivot (qui est toujours à sa position d'origine) peut être réduite en taille en excluant ce pivot, après l'avoir (si nécessaire) échangé avec l'élément de sous-gamme le plus proche de la séparation; ainsi, la fin du tri rapide est assurée.

Par rapport à cette description originale, les implémentations font souvent des variations mineures mais importantes. Notamment, le schéma tel que présenté ci-dessous comprend des éléments égaux au pivot parmi les candidats à une inversion (donc les tests « supérieur ou égal » et « inférieur ou égal » sont utilisés au lieu de « supérieur à » respectivement « inférieur à » ; puisque la formulation utilise do ... while plutôt que repeat ... jusqu'à ce qui est en fait reflété par l'utilisation d'opérateurs de comparaison stricts). Bien qu'il n'y ait aucune raison d'échanger des éléments égaux à la limite, ce changement permet d'omettre les tests sur les pointeurs eux-mêmes, qui sont autrement nécessaires pour s'assurer qu'ils ne sont pas hors de portée. En effet, puisqu'au moins une instance de la valeur pivot est présente dans la plage, le premier avancement de l'un ou l'autre pointeur ne peut pas traverser cette instance si un test inclusif est utilisé ; une fois l'échange effectué, ces éléments échangés sont désormais tous les deux strictement en avance sur le pointeur qui les a trouvés, empêchant ce pointeur de s'échapper. (Ce dernier est vrai indépendamment du test utilisé, il serait donc possible d'utiliser le test inclusif uniquement lors de la recherche de la première inversion. Cependant, l'utilisation d'un test inclusif garantit également qu'une division proche du milieu est trouvée lorsque tous les éléments dans la plage est égale, ce qui donne un gain d'efficacité important pour le tri des tableaux avec de nombreux éléments égaux.) Le risque de produire une séparation non avançante est évité d'une manière différente de celle décrite par Hoare. Une telle séparation ne peut se produire que lorsqu'aucune inversion n'est trouvée, les deux pointeurs avançant vers l'élément pivot à la première itération (ils sont alors considérés comme croisés et aucun échange n'a lieu). La division renvoyée est après la position finale du deuxième pointeur, donc le cas à éviter est celui où le pivot est l'élément final de la plage et tous les autres sont plus petits que lui. Par conséquent, le choix du pivot doit éviter l'élément final (dans la description de Hoare, il pourrait s'agir de n'importe quel élément de la plage) ; cela se fait ici en arrondissant la position médiane à l' inférieur , à l'aide de la floorfonction . Cela illustre que l'argument en faveur de l'exactitude d'une implémentation du schéma de partition de Hoare peut être subtil, et il est facile de se tromper.

En pseudo - code ,

// Sorts a (portion of an) array, divides it into partitions, then sorts those
algorithm quicksort(A, lo, hi) is 
  if lo >= 0 && hi >= 0 && lo < hi then
    p := partition(A, lo, hi) 
    quicksort(A, lo, p) // Note: the pivot is now included
    quicksort(A, p + 1, hi) 

// Divides array into two partitions
algorithm partition(A, lo, hi) is 
  // Pivot value
  pivot := A[ floor((hi + lo) / 2) ] // The value in the middle of the array

  // Left index
  i := lo - 1 

  // Right index
  j := hi + 1

  loop forever 
    // Move the left index to the right at least once and while the element at 
    // the left index is less than the pivot 
    do i := i + 1 while A[i] < pivot 
    
    // Move the right index to the left at least once and while the element at
    // the right index is greater than the pivot 
    do j := j - 1 while A[j] > pivot 

    // If the indices crossed, return
    if i ≥ j then return j
    
    // Swap the elements at the left and right indices
    swap A[i] with A[j]

L'ensemble du tableau est trié par quicksort(A, 0, length(A) - 1) .

Le schéma de Hoare est plus efficace que le schéma de partition de Lomuto car il effectue en moyenne trois fois moins d'échanges. De plus, comme mentionné, l'implémentation donnée crée une partition équilibrée même lorsque toutes les valeurs sont égales, ce que le schéma de Lomuto ne fait pas. Comme le schéma de partition de Lomuto, le partitionnement de Hoare entraînerait également la dégradation de Quicksort en $O (n 2)$ pour les entrées déjà triées, si le pivot était choisi comme premier ou dernier élément. Avec l'élément du milieu comme pivot, cependant, les résultats de données triés avec (presque) aucun échange dans des partitions de taille égale conduisant au meilleur comportement de Quicksort, c'est-à-dire $O (n log(n))$ . Comme d'autres, le partitionnement de Hoare ne produit pas un tri stable. Dans ce schéma, l'emplacement final du pivot n'est pas nécessairement à l'index renvoyé, car le pivot et les éléments égaux au pivot peuvent se retrouver n'importe où dans la partition après une étape de partition et peuvent ne pas être triés avant le cas de base d'un la partition à un seul élément est atteinte par récursivité. Les deux segments suivants sur lesquels l'algorithme principal revient sont (lo..p) (éléments ≤ pivot) et (p+1..hi) (éléments ≥ pivot) par opposition à (lo..p-1) et (p +1..hi) comme dans le schéma de Lomuto.

Problèmes de mise en œuvre

Choix du pivot

Dans les toutes premières versions de quicksort, l'élément le plus à gauche de la partition était souvent choisi comme élément pivot. Malheureusement, cela provoque un comportement dans le pire des cas sur des tableaux déjà triés, ce qui est un cas d'utilisation assez courant. Le problème a été facilement résolu en choisissant soit un index aléatoire pour le pivot, en choisissant l'index du milieu de la partition ou (surtout pour les partitions plus longues) en choisissant la médiane du premier, du milieu et du dernier élément de la partition pour le pivot (comme recommandé par Sedgewick ). Cette règle de la "médiane sur trois" contrecarre le cas des entrées triées (ou triées à l'envers) et donne une meilleure estimation du pivot optimal (la vraie médiane) que la sélection d'un seul élément, lorsqu'aucune information sur l'ordre des l'entrée est connue.

Extrait de code médian sur trois pour la partition Lomuto :

mid := ⌊(lo + hi) / 2⌋
if A[mid] < A[lo]
    swap A[lo] with A[mid]
if A[hi] < A[lo]
    swap A[lo] with A[hi]
if A[mid] < A[hi]
    swap A[mid] with A[hi]
pivot := A[hi]

Il met d'abord une médiane A[hi], puis cette nouvelle valeur de A[hi]est utilisée pour un pivot, comme dans un algorithme de base présenté ci-dessus.

Plus précisément, le nombre attendu de comparaisons nécessaires pour trier $n$ éléments (voir § Analyse du tri rapide aléatoire ) avec une sélection pivot aléatoire est de $1,386 n log n$ . Le pivotement de la médiane sur trois le ramène à $C n, 2 1,188 n log n$ , au prix d'une augmentation de trois pour cent du nombre attendu d'échanges. Une règle de pivotement encore plus forte, pour les tableaux plus grands, consiste à choisir le neuvième , une médiane récursive sur trois (Mo3), définie comme

neuvième( a ) = médiane(Mo3(premier.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num,.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0 0.1em}.mw-parser-output .sfrac .den{border-top:1px solid}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px} 1/3d' un ), Mo3 (milieu1/3d' un ), Mo3 (final1/3d' un ))

La sélection d'un élément pivot est également compliquée par l'existence d' un débordement d'entier . Si les indices de limite du sous-tableau trié sont suffisamment grands, l'expression naïve pour l'indice du milieu, $(lo + hi)/2$ , provoquera un débordement et fournira un indice pivot invalide. Ceci peut être surmonté en utilisant, par exemple, $lo + (hi - lo)/2$ pour indexer l'élément du milieu, au prix d'une arithmétique plus complexe. Des problèmes similaires se posent dans d'autres méthodes de sélection de l'élément pivot.

Éléments répétés

Avec un algorithme de partitionnement tel que le schéma de partition Lomuto décrit ci-dessus (même celui qui choisit de bonnes valeurs de pivot), le tri rapide présente des performances médiocres pour les entrées contenant de nombreux éléments répétés. Le problème apparaît clairement lorsque tous les éléments d'entrée sont égaux : à chaque récursivité, la partition de gauche est vide (aucune valeur d'entrée n'est inférieure au pivot), et la partition de droite n'a diminué que d'un élément (le pivot est supprimé). Par conséquent, le schéma de partition Lomuto prend un temps quadratique pour trier un tableau de valeurs égales. Cependant, avec un algorithme de partitionnement tel que le schéma de partition de Hoare, les éléments répétés entraînent généralement un meilleur partitionnement, et bien que des échanges inutiles d'éléments égaux au pivot puissent se produire, le temps d'exécution diminue généralement à mesure que le nombre d'éléments répétés augmente (avec le cache mémoire réduisant les frais généraux d'échange). Dans le cas où tous les éléments sont égaux, le schéma de partition Hoare échange inutilement des éléments, mais le partitionnement lui-même est le meilleur des cas, comme indiqué dans la section partition Hoare ci-dessus.

Pour résoudre le problème du schéma de partition de Lomuto (parfois appelé le problème du drapeau national néerlandais ), une autre routine de partition en temps linéaire peut être utilisée qui sépare les valeurs en trois groupes : les valeurs inférieures au pivot, les valeurs égales au pivot et les valeurs supérieures que le pivot. (Bentley et McIlroy appellent cela une "grosse partition" et elle a déjà été implémentée dans le qsort de la version 7 Unix .) Les valeurs égales au pivot sont déjà triées, de sorte que seules les partitions inférieure et supérieure à doivent être récursivement trié. En pseudocode, l'algorithme de tri rapide devient

algorithm quicksort(A, lo, hi) is
    if lo < hi then
        p := pivot(A, lo, hi)
        left, right := partition(A, p, lo, hi)  // note: multiple return values
        quicksort(A, lo, left - 1)
        quicksort(A, right + 1, hi)

L' partitionalgorithme renvoie des indices au premier ('le plus à gauche') et au dernier ('le plus à droite') élément de la partition du milieu. Chaque élément de la partition est égal à pet est donc trié. Par conséquent, les éléments de la partition n'ont pas besoin d'être inclus dans les appels récursifs à quicksort.

Le meilleur cas pour l'algorithme se produit maintenant lorsque tous les éléments sont égaux (ou sont choisis parmi un petit ensemble de $k ≪ n$ éléments). Dans le cas de tous les éléments égaux, le tri rapide modifié n'effectuera que deux appels récursifs sur des sous-tableaux vides et se terminera donc en temps linéaire (en supposant que le partitionsous - programme ne prend pas plus de temps que le temps linéaire).

Optimisations

Deux autres optimisations importantes, également suggérées par Sedgewick et largement utilisées dans la pratique, sont :

Pour vous assurer qu'au plus l' espace $O (log n)$ est utilisé, revenez d' abord dans le plus petit côté de la partition, puis utilisez un appel de queue pour revenir dans l'autre, ou mettez à jour les paramètres pour ne plus inclure le plus petit côté maintenant trié, et itérer pour trier le plus grand côté.
Lorsque le nombre d'éléments est inférieur à un certain seuil (peut-être dix éléments), passez à un algorithme de tri non récursif tel que le tri par insertion qui effectue moins d'échanges, de comparaisons ou d'autres opérations sur de si petits tableaux. Le « seuil » idéal variera en fonction des détails de la mise en œuvre spécifique.
Une variante plus ancienne de l'optimisation précédente : lorsque le nombre d'éléments est inférieur au seuil $k$ , arrêtez simplement ; puis, une fois que l'ensemble du tableau a été traité, effectuez un tri par insertion dessus. L'arrêt précoce de la récursivité laisse le tableau trié en $k$ , ce qui signifie que chaque élément est à au plus $k$ positions de sa position triée finale. Dans ce cas, le tri par insertion prend $O (kn)$ pour terminer le tri, ce qui est linéaire si $k$ est une constante. Par rapport à l'optimisation "beaucoup de petites sortes", cette version peut exécuter moins d'instructions, mais elle fait une utilisation sous-optimale des mémoires cache dans les ordinateurs modernes.

Parallélisation

La formulation diviser pour régner de Quicksort permet la parallélisation à l' aide du parallélisme des tâches . L'étape de partitionnement est accomplie grâce à l'utilisation d'un algorithme de somme de préfixe parallèle pour calculer un indice pour chaque élément de tableau dans sa section du tableau partitionné. Étant donné un tableau de taille $n$ , l'étape de partitionnement effectue $O(n)$ travail en $O (log n)$ temps et nécessite $O(n)$ espace de travail supplémentaire. Une fois la baie partitionnée, les deux partitions peuvent être triées récursivement en parallèle. En supposant un choix idéal de pivots, le tri rapide parallèle trie un tableau de taille $n$ en $O(n log n)$ fonctionne en $O(log 2 n)$ temps en utilisant $O(n)$ espace supplémentaire.

Quicksort présente certains inconvénients par rapport aux algorithmes de tri alternatifs, comme merge sort , qui compliquent sa parallélisation efficace. La profondeur de l'arbre diviser pour régner de quicksort a un impact direct sur l'évolutivité de l'algorithme, et cette profondeur dépend fortement du choix du pivot de l'algorithme. De plus, il est difficile de paralléliser efficacement l'étape de partitionnement sur place. L'utilisation de l'espace de travail simplifie l'étape de partitionnement, mais augmente l'empreinte mémoire de l'algorithme et les frais généraux constants.

D'autres algorithmes de tri parallèle plus sophistiqués peuvent atteindre des limites de temps encore meilleures. Par exemple, en 1991, David Powers a décrit un tri rapide parallélisé (et un tri de base connexe ) qui peut fonctionner en temps $O (log n)$ sur une PRAM (machine à accès aléatoire parallèle ) CRCW (lecture et écriture simultanées ) avec $n$ processeurs en effectuer un partitionnement implicitement.

Analyse formelle

Analyse du pire des cas

La partition la plus déséquilibrée se produit lorsque l'une des sous-listes renvoyées par la routine de partitionnement est de taille $n - 1$ . Cela peut se produire si le pivot se trouve être le plus petit ou le plus grand élément de la liste, ou dans certaines implémentations (par exemple, le schéma de partition Lomuto tel que décrit ci-dessus) lorsque tous les éléments sont égaux.

Si cela se produit à plusieurs reprises dans chaque partition, alors chaque appel récursif traite une liste de taille un de moins que la liste précédente. Par conséquent, nous pouvons faire $n - 1$ appels imbriqués avant d'atteindre une liste de taille 1. Cela signifie que l' arbre des appels est une chaîne linéaire de $n - 1$ appels imbriqués. Le $i$ ème appel fait $O (n - i)$ pour effectuer la partition, et , donc dans ce cas le tri rapide prend $O$ $($ $n$ $2$ $)$ temps. $\textstyle \sum _{i=0}^{n}(ni)=O(n^{2})$

Analyse du meilleur cas

Dans le cas le plus équilibré, chaque fois que nous effectuons une partition, nous divisons la liste en deux parties presque égales. Cela signifie que chaque appel récursif traite une liste de la moitié de la taille. Par conséquent, nous ne pouvons faire que $log 2 n$ appels imbriqués avant d'atteindre une liste de taille 1. Cela signifie que la profondeur de l' arbre des appels est $log 2 n$ . Mais deux appels au même niveau de l'arbre d'appels ne traitent pas la même partie de la liste d'origine ; ainsi, chaque niveau d'appels n'a besoin que de $O (n)$ temps au total (chaque appel a un surcoût constant, mais puisqu'il n'y a que $O (n)$ appels à chaque niveau, cela est subsumé dans le facteur $O (n)$ ). Le résultat est que l'algorithme n'utilise que le temps $O (n log n)$ .

Analyse de cas moyen

Pour trier un tableau de $n$ éléments distincts, le tri rapide prend $O (n log n)$ temps d'attente, moyenné sur tous les $n!$ permutations de $n$ éléments avec une probabilité égale . Nous énumérons ici trois preuves communes à cette affirmation fournissant différentes informations sur le fonctionnement de quicksort.

Utilisation des centiles

Si chaque pivot a un rang quelque part au milieu des 50 %, c'est-à-dire entre le 25e centile et le 75e centile, alors il divise les éléments avec au moins 25 % et au plus 75 % de chaque côté. Si nous pouvions choisir de manière cohérente de tels pivots, nous n'aurions qu'à diviser la liste la plupart du temps avant d'atteindre des listes de taille 1, ce qui donnerait un algorithme $O$ $($ $n$ $log$ $n$ $)$ . $\log _{4/3}n$

Lorsque l'entrée est une permutation aléatoire, le pivot a un rang aléatoire et il n'est donc pas garanti qu'il se situe au milieu des 50 %. Cependant, lorsque nous partons d'une permutation aléatoire, dans chaque appel récursif, le pivot a un rang aléatoire dans sa liste, et il est donc au milieu de 50 pour cent environ la moitié du temps. C'est assez bien. Imaginez qu'une pièce est lancée : face signifie que le rang du pivot est au milieu de 50 pour cent, pile signifie qu'il ne l'est pas. Imaginez maintenant que la pièce est retournée encore et encore jusqu'à ce qu'elle obtienne $k face$ . Bien que cela puisse prendre beaucoup de temps, en moyenne, seulement $2 k$ flips sont nécessaires, et la probabilité que la pièce n'obtienne pas $k$ faces après $100 k$ flips est hautement improbable (cela peut être rendu rigoureux en utilisant les limites de Chernoff ). Par le même argument, la récursivité de Quicksort se terminera en moyenne à une profondeur d'appel de seulement . Mais si sa profondeur d'appel moyenne est $O$ $(log$ $n$ $)$ , et que chaque niveau de l'arbre d'appels traite au plus $n$ éléments, la quantité totale de travail effectué en moyenne est le produit, $O$ $($ $n$ $log$ $n$ $)$ . L'algorithme n'a pas à vérifier que le pivot est dans la moitié médiane - si nous l'atteignons une fraction constante des fois, cela suffit pour la complexité souhaitée. $2\log _{4/3}n$

Utilisation des récurrences

Une approche alternative consiste à établir une relation de récurrence pour le facteur $T (n)$ , le temps nécessaire pour trier une liste de taille $n$ . Dans le cas le plus déséquilibré, un seul appel de tri rapide implique $O (n)$ travail plus deux appels récursifs sur des listes de taille $0$ et $n -1$ , donc la relation de récurrence est

{\style d'affichage T(n)=O(n)+T(0)+T(n-1)=O(n)+T(n-1).}

C'est la même relation que pour le tri par insertion et le tri par sélection , et elle résout dans le pire des cas $T (n) = O (n 2)$ .

Dans le cas le plus équilibré, un seul appel de tri rapide implique $O (n)$ travail plus deux appels récursifs sur des listes de taille $n /2$ , donc la relation de récurrence est

T(n)=O(n)+2T\gauche({\frac {n}{2}}\droit).

Le théorème principal pour les récurrences diviser pour régner nous dit que $T (n) = O (n log n)$ .

Le schéma d'une preuve formelle de la complexité temporelle attendue $O (n log n)$ suit. Supposons qu'il n'y ait pas de doublons car les doublons pourraient être traités avec un pré-traitement et un post-traitement en temps linéaire, ou considérés comme des cas plus faciles que ceux analysés. Lorsque l'entrée est une permutation aléatoire, le rang du pivot est aléatoire uniforme de 0 à $n - 1$ . Alors les parties résultantes de la partition ont des tailles $i$ et $n - i - 1$ , et i est aléatoire uniforme de 0 à $n - 1$ . Ainsi, en faisant la moyenne sur toutes les divisions possibles et en notant que le nombre de comparaisons pour la partition est $n - 1$ , le nombre moyen de comparaisons sur toutes les permutations de la séquence d'entrée peut être estimé avec précision en résolvant la relation de récurrence :

C(n)=n-1+{\frac {1}{n}}\sum _{i=0}^{n-1}(C(i)+C(ni-1))= n-1+{\frac {2}{n}}\somme _{i=0}^{n-1}C(i)

nC(n)=n(n-1)+2\sum _{i=0}^{n-1}C(i)

{\style d'affichage nC(n)-(n-1)C(n-1)=n(n-1)-(n-1)(n-2)+2C(n-1)}

{\style d'affichage nC(n)=(n+1)C(n-1)+2n-2}

{\begin{aligned}{\frac {C(n)}{n+1}}&={\frac {C(n-1)}{n}}+{\frac {2}{n +1}}-{\frac {2}{n(n+1)}}\leq {\frac {C(n-1)}{n}}+{\frac {2}{n+1}} \\&={\frac {C(n-2)}{n-1}}+{\frac {2}{n}}-{\frac {2}{(n-1)n}}+{ \frac {2}{n+1}}\leq {\frac {C(n-2)}{n-1}}+{\frac {2}{n}}+{\frac {2}{n +1}}\\&\ \ \vdots \\&={\frac {C(1)}{2}}+\somme _{i=2}^{n}{\frac {2}{i+ 1}}\leq 2\sum _{i=1}^{n-1}{\frac {1}{i}}\approx 2\int _{1}^{n}{\frac {1}{ x}}\mathrm {d} x=2\ln n\end{aligned}}

La résolution de la récurrence donne $C (n) = 2 n ln n \approx 1,39 n log 2 n$ .

Cela signifie qu'en moyenne, le tri rapide ne fonctionne qu'environ 39 % moins bien que dans le meilleur des cas. En ce sens, il est plus proche du meilleur que du pire des cas. Un tri par comparaison ne peut pas utiliser moins de $log 2 (n!)$ comparaisons en moyenne pour trier $n$ éléments (comme expliqué dans l'article Comparison sort ) et en cas de grand $n$ , l'approximation de Stirling donne $log 2 (n!) \approx n (log 2 n - log 2 e)$ , donc le tri rapide n'est pas bien pire qu'un tri par comparaison idéal. Ce temps d'exécution moyen rapide est une autre raison de la domination pratique de quicksort sur les autres algorithmes de tri.

Utiliser un arbre de recherche binaire

L' arbre de recherche binaire (BST) suivant correspond à chaque exécution de tri rapide : le pivot initial est le nœud racine ; le pivot de la moitié gauche est la racine du sous-arbre gauche, le pivot de la moitié droite est la racine du sous-arbre droit, et ainsi de suite. Le nombre de comparaisons de l'exécution du tri rapide est égal au nombre de comparaisons lors de la construction du BST par une séquence d'insertions. Ainsi, le nombre moyen de comparaisons pour un tri rapide aléatoire est égal au coût moyen de construction d'un BST lorsque les valeurs insérées forment une permutation aléatoire. ${\style d'affichage (x_{1},x_{2},\ldots ,x_{n})}$

Considérons un BST créé par insertion d'une séquence de valeurs formant une permutation aléatoire. Soit $C$ le coût de création du BST. Nous avons , où est une variable aléatoire binaire exprimant si lors de l'insertion de il y avait une comparaison à . ${\style d'affichage (x_{1},x_{2},\ldots ,x_{n})}$ $C=\sum _{i}\sum _{j<i}c_{i,j}$ ${\style d'affichage c_{i,j}}$ ${\style d'affichage x_{i}}$ ${\style d'affichage x_{j}}$

Par linéarité de l'espérance , la valeur attendue de $C$ est . $\operatorname {E} [C]$ $\operatorname {E} [C]=\sum _{i}\sum _{j<i}\Pr(c_{i,j})$

Fixer $i$ et $j < i$ . Les valeurs , une fois triées, définissent $j$ $+1$ intervalles. L'observation structurelle de base est celle qui est comparée à dans l'algorithme si et seulement si tombe à l'intérieur de l'un des deux intervalles adjacents à . ${x_{1},x_{2},\ldots ,x_{j}}$ ${\style d'affichage x_{i}}$ ${\style d'affichage x_{j}}$ ${\style d'affichage x_{i}}$ ${\style d'affichage x_{j}}$

Observez que puisque est une permutation aléatoire, est également une permutation aléatoire, donc la probabilité adjacente à est exactement . ${\style d'affichage (x_{1},x_{2},\ldots ,x_{n})}$ ${\style d'affichage (x_{1},x_{2},\ldots ,x_{j},x_{i})}$ ${\style d'affichage x_{i}}$ ${\style d'affichage x_{j}}$ ${\frac {2}{j+1}}$

On termine par un petit calcul :

\operatorname {E} [C]=\sum _{i}\sum _{j<i}{\frac {2}{j+1}}=O\left(\sum _{i}\ log i\right)=O(n\log n).

Complexité spatiale

L'espace utilisé par quicksort dépend de la version utilisée.

La version sur place de quicksort a une complexité spatiale de $O (log n)$ , même dans le pire des cas, lorsqu'elle est soigneusement implémentée à l'aide des stratégies suivantes.

Le partitionnement sur place est utilisé. Cette partition instable nécessite $O (1)$ espace.
Après le partitionnement, la partition avec le moins d'éléments est (récursivement) triée en premier, nécessitant au plus $O (log n)$ espace. Ensuite, l'autre partition est triée à l'aide de la récursivité ou de l'itération de queue , ce qui n'ajoute rien à la pile d'appels. Cette idée, comme discuté ci-dessus, a été décrite par R. Sedgewick , et maintient la profondeur de la pile limitée par $O (log n)$ .

Quicksort avec partitionnement en place et instable n'utilise qu'un espace supplémentaire constant avant d'effectuer un appel récursif. Quicksort doit stocker une quantité constante d'informations pour chaque appel récursif imbriqué. Puisque le meilleur des cas fait au plus $O (log n)$ appels récursifs imbriqués, il utilise l' espace $O (log n)$ . Cependant, sans l'astuce de Sedgewick pour limiter les appels récursifs, dans le pire des cas, quicksort pourrait effectuer $O (n)$ appels récursifs imbriqués et nécessiter $O (n)$ espace auxiliaire.

D'un point de vue peu complexe, les variables telles que lo et hi n'utilisent pas d'espace constant ; il faut $O (log n)$ bits pour indexer dans une liste de $n$ éléments. Comme il existe de telles variables dans chaque cadre de pile, le tri rapide utilisant l'astuce de Sedgewick nécessite $O ((log n) 2)$ bits d'espace. Cette exigence d'espace n'est pas trop terrible, cependant, car si la liste contenait des éléments distincts, elle aurait besoin d'au moins $O (n log n)$ bits d'espace.

Une autre version, moins courante et non en place, du tri rapide utilise un espace $O (n)$ pour le stockage de travail et peut implémenter un tri stable. Le stockage de travail permet au tableau d'entrée d'être facilement partitionné de manière stable, puis de le recopier dans le tableau d'entrée pour des appels récursifs successifs. L'optimisation de Sedgewick est toujours appropriée.

Relation avec d'autres algorithmes

Quicksort est une version optimisée pour l'espace du tri par arbre binaire . Au lieu d'insérer des éléments de manière séquentielle dans une arborescence explicite, quicksort les organise simultanément dans une arborescence qui est impliquée par les appels récursifs. Les algorithmes font exactement les mêmes comparaisons, mais dans un ordre différent. Une propriété souvent souhaitable d'un algorithme de tri est la stabilité - c'est-à-dire que l'ordre des éléments comparables n'est pas modifié, ce qui permet de contrôler l'ordre des tables multi-clés (par exemple, les listes de répertoires ou de dossiers) de manière naturelle. Cette propriété est difficile à maintenir pour le tri rapide in situ (ou en place) (qui utilise uniquement un espace supplémentaire constant pour les pointeurs et les tampons, et un espace supplémentaire $O (log n)$ pour la gestion de la récursion explicite ou implicite). Pour les variantes de tris rapides impliquant de la mémoire supplémentaire en raison de représentations utilisant des pointeurs (par exemple des listes ou des arbres) ou des fichiers (en fait des listes), il est trivial de maintenir la stabilité. Les structures de données plus complexes, ou liées au disque, ont tendance à augmenter le coût en temps, en utilisant en général de plus en plus la mémoire virtuelle ou le disque.

Le concurrent le plus direct du quicksort est le heapsort . Le temps d'exécution de heapsort est $O (n log n)$ , mais le temps d'exécution moyen de heapsort est généralement considéré comme plus lent que le tri rapide sur place. Ce résultat est discutable ; certaines publications indiquent le contraire. Introsort est une variante de quicksort qui passe en heapsort lorsqu'un mauvais cas est détecté pour éviter le pire temps d'exécution de quicksort.

Quicksort est également en concurrence avec merge sort , un autre algorithme de tri $O (n log n)$ . Mergesort est un tri stable , contrairement au tri rapide et au tas sur place standard, et présente d'excellentes performances dans le pire des cas. Le principal inconvénient de mergesort est que, lorsqu'elles fonctionnent sur des tableaux, les implémentations efficaces nécessitent un espace auxiliaire $O (n)$ , alors que la variante de quicksort avec partitionnement sur place et récursivité de la queue n'utilise que l' espace $O (log n)$ .

Mergesort fonctionne très bien sur les listes chaînées , ne nécessitant qu'une petite quantité constante de stockage auxiliaire. Bien que le tri rapide puisse être implémenté en tant que tri stable à l'aide de listes chaînées, il souffrira souvent de mauvais choix de pivot sans accès aléatoire. Mergesort est également l'algorithme de choix pour le tri externe d'ensembles de données très volumineux stockés sur des supports à accès lent tels que le stockage sur disque ou le stockage en réseau .

Le tri par seaux avec deux seaux est très similaire au tri rapide ; le pivot dans ce cas est effectivement la valeur au milieu de la plage de valeurs, qui fonctionne bien en moyenne pour des entrées uniformément réparties.

Pivotement basé sur la sélection

Un algorithme de sélection choisit le $k$ ième plus petit d'une liste de nombres ; c'est un problème plus facile en général que le tri. Un algorithme de sélection simple mais efficace fonctionne presque de la même manière que quicksort et est donc connu sous le nom de quickselect . La différence est qu'au lieu de faire des appels récursifs sur les deux sous-listes, il ne fait qu'un seul appel récursif de queue sur la sous-liste qui contient l'élément souhaité. Ce changement abaisse la complexité moyenne au temps linéaire ou $O (n)$ , ce qui est optimal pour la sélection, mais l'algorithme de sélection est toujours $O (n 2)$ dans le pire des cas.

Une variante de quickselect, l' algorithme de la médiane des médianes , choisit les pivots avec plus de soin, garantissant que les pivots sont proches du milieu des données (entre le 30e et le 70e centiles), et a donc un temps linéaire garanti - $O (n)$ . Cette même stratégie de pivot peut être utilisée pour construire une variante de quicksort (median of medians quicksort) avec un temps $O (n log n)$ . Cependant, le surcoût lié au choix du pivot est important, de sorte qu'il n'est généralement pas utilisé dans la pratique.

De manière plus abstraite, étant donné un algorithme de sélection $O (n)$ , on peut l'utiliser pour trouver le pivot idéal (la médiane) à chaque étape du tri rapide et ainsi produire un algorithme de tri avec un temps d'exécution $O (n log n)$ . Les implémentations pratiques de cette variante sont considérablement plus lentes en moyenne, mais elles présentent un intérêt théorique car elles montrent qu'un algorithme de sélection optimal peut produire un algorithme de tri optimal.

Variantes

Tri rapide multi-pivot

Au lieu de diviser en deux sous - réseaux en utilisant un seul pivot, quicksort multi-pivot (également multiquicksort) partitionne son entrée dans certains $s$ nombre de sous - réseaux en utilisant $s - 1$ pivots. Alors que le cas à double pivot ( $s = 3$ ) était déjà considéré par Sedgewick et d'autres au milieu des années 1970, les algorithmes résultants n'étaient pas plus rapides en pratique que le tri rapide « classique ». Une évaluation de 1999 d'un tri rapide avec un nombre variable de pivots, réglé pour utiliser efficacement les caches du processeur, a révélé qu'il augmentait le nombre d'instructions d'environ 20 %, mais les résultats de la simulation ont suggéré qu'il serait plus efficace sur de très grandes entrées. Une version de tri rapide à double pivot développée par Yaroslavskiy en 2009 s'est avérée suffisamment rapide pour justifier une implémentation dans Java 7 , en tant qu'algorithme standard pour trier des tableaux de primitives (le tri des tableaux d' objets est effectué à l'aide de Timsort ). L'avantage en termes de performances de cet algorithme s'est par la suite avéré principalement lié aux performances du cache, et les résultats expérimentaux indiquent que la variante à trois pivots peut fonctionner encore mieux sur les machines modernes.

Tri rapide externe

Pour les fichiers disque, un tri externe basé sur un partitionnement similaire au tri rapide est possible. Il est plus lent que le tri par fusion externe, mais ne nécessite pas d'espace disque supplémentaire. 4 buffers sont utilisés, 2 pour l'entrée, 2 pour la sortie. Soit N = nombre d'enregistrements dans le fichier, B = le nombre d'enregistrements par tampon et M = N/B = le nombre de segments de tampon dans le fichier. Les données sont lues (et écrites) des deux extrémités du fichier vers l'intérieur. Soit X les segments qui commencent au début du fichier et Y les segments qui commencent à la fin du fichier. Les données sont lues dans les tampons de lecture X et Y. Un enregistrement pivot est choisi et les enregistrements des tampons X et Y autres que l'enregistrement pivot sont copiés dans le tampon d'écriture X dans l'ordre croissant et le tampon d'écriture Y dans l'ordre décroissant basé sur la comparaison avec l'enregistrement pivot. Une fois que le tampon X ou Y est rempli, il est écrit dans le fichier et le tampon X ou Y suivant est lu à partir du fichier. Le processus se poursuit jusqu'à ce que tous les segments soient lus et qu'il reste un tampon d'écriture. Si ce tampon est un tampon d'écriture X, l'enregistrement pivot lui est ajouté et le tampon X est écrit. Si ce tampon est un tampon d'écriture Y, l'enregistrement pivot est ajouté au tampon Y et le tampon Y écrit. Cela constitue une étape de partition du fichier, et le fichier est maintenant composé de deux sous-fichiers. Les positions de début et de fin de chaque sous-fichier sont poussées/sautées vers une pile autonome ou la pile principale par récursivité. Pour limiter l'espace de pile à O(log2(n)), le plus petit sous-fichier est traité en premier. Pour une pile autonome, poussez les paramètres de sous-fichier les plus grands sur la pile, itérez sur le sous-fichier plus petit. Pour la récursivité, récursez d'abord sur le plus petit sous-fichier, puis itérez pour gérer le plus grand sous-fichier. Une fois qu'un sous-fichier est inférieur ou égal à 4 B enregistrements, le sous-fichier est trié sur place via un tri rapide et écrit. Ce sous-fichier est maintenant trié et en place dans le fichier. Le processus se poursuit jusqu'à ce que tous les sous-dossiers soient triés et mis en place. Le nombre moyen de passes sur le fichier est d'environ 1 + ln(N+1)/(4 B), mais le pire des cas est N passes (équivalent à O(n^2) pour le pire cas de tri interne).

Tri rapide radix à trois voies

Cet algorithme est une combinaison de tri par base et de tri rapide. Choisissez un élément du tableau (le pivot) et considérez le premier caractère (clé) de la chaîne (multiclé). Divisez les éléments restants en trois ensembles : ceux dont le caractère correspondant est inférieur, égal et supérieur au caractère du pivot. Trier récursivement les partitions "inférieur à" et "supérieur à" sur le même caractère. Trier récursivement la partition "égale à" par le caractère suivant (clé). Étant donné que nous trions en utilisant des octets ou des mots de longueur $W$ bits, le meilleur cas est $O (KN)$ et le pire des cas $O (2 K N)$ ou au moins $O (N 2)$ comme pour le tri rapide standard, donné pour les clés uniques $N <2 K$ , et $K$ est une constante cachée dans tous les algorithmes de tri par comparaison standard , y compris le tri rapide. Il s'agit d'une sorte de tri rapide à trois voies dans lequel la partition du milieu représente un sous-tableau trié (trivialement) d'éléments exactement égaux au pivot.

Tri rapide par base

Également développé par Powers en tant qu'algorithme PRAM parallèle $O (K)$ . Il s'agit à nouveau d'une combinaison de tri par base et de tri rapide, mais la décision de partition gauche/droite de tri rapide est prise sur les bits successifs de la clé, et est donc $O$ $($ $KN$ $)$ pour les clés $N$ $K$ bits. Tous les tri de comparaison des algorithmes impliclty supposent le modèle transdichotomous avec $K$ dans $Θ$ $(log$ $N$ $)$ , comme si $K$ est plus petit que nous pouvons trier dans $O$ $($ $N$ $)$ heure à l' aide d' une table de hachage ou entier tri . Si $K$ $log$ $N$ mais que les éléments sont uniques dans $O$ $(log$ $N$ $)$ bits, les bits restants ne seront pas examinés par le tri rapide ou le tri par base rapide. A défaut, tous les algorithmes de tri par comparaison auront également le même surcoût de recherche à travers $O$ $($ $K$ $)$ bits relativement inutiles, mais le tri par base rapide évitera les pires comportements $O$ $($ $N$ $2$ $)$ du tri rapide standard et du tri rapide par base , et sera même plus rapide dans le meilleur des cas de ces algorithmes de comparaison dans ces conditions de $préfixe unique($ $K$ $) log$ $N$ . Voir Powers pour une discussion plus approfondie des frais généraux cachés en comparaison, en base et en tri parallèle.

Bloquer le tri rapide

Dans tout algorithme de tri basé sur des comparaisons, minimiser le nombre de comparaisons nécessite de maximiser la quantité d'informations obtenues à partir de chaque comparaison, ce qui signifie que les résultats de la comparaison sont imprévisibles. Cela provoque de fréquentes erreurs de prédiction de branche , limitant les performances. BlockQuicksort réorganise les calculs de quicksort pour convertir les branches imprévisibles en dépendances de données . Lors du partitionnement, l'entrée est divisée en blocs de taille modérée (qui s'insèrent facilement dans le cache de données ), et deux tableaux sont remplis avec les positions des éléments à échanger. (Pour éviter les branchements conditionnels, la position est stockée inconditionnellement à la fin du tableau, et l'index de la fin est incrémenté si un swap est nécessaire.) Une seconde passe échange les éléments aux positions indiquées dans les tableaux. Les deux boucles n'ont qu'un seul branchement conditionnel, un test de terminaison, qui est généralement effectué.

Tri rapide partiel et incrémentiel

Il existe plusieurs variantes de tri rapide qui séparent les $k$ éléments les plus petits ou les plus grands du reste de l'entrée.

Généralisation

Richard Cole et David C. Kandathil, en 2004, ont découvert une famille d'algorithmes de tri à un paramètre, appelés tris de partition, qui en moyenne (avec tous les ordres d'entrée également probables) effectuent la plupart des comparaisons (proche de la limite inférieure de la théorie de l'information) et opérations; au pire ils effectuent des comparaisons (et aussi des opérations) ; ceux-ci sont en place, ne nécessitant que de l' espace supplémentaire . L'efficacité pratique et la plus petite variation des performances ont été démontrées par rapport aux tris rapides optimisés (de Sedgewick et Bentley - McIlroy ). ${\style d'affichage n\log n+{O}(n)}$ ${\Thêta }(n\log n)$ ${\Thêta }(n\log ^{2}n)$ ${O}(\log n)$

Voir également

Introsort – Algorithme de tri hybride

Remarques

Les références

Sedgewick, R. (1978). "Mise en œuvre des programmes Quicksort". Comm. ACM . 21 (10) : 847-857. doi : 10.1145/359619.359631 . S2CID 10020756 .
Dean, C.-B. (2006). « Une simple analyse du temps d'exécution prévu pour les algorithmes aléatoires « diviser pour régner » ». Mathématiques discrètes appliquées . 154 : 1–5. doi : 10.1016/j.dam.2005.07.005 .
Hoare, RCA (1961). "Algorithme 63: Partition". Comm. ACM . 4 (7) : 321. doi : 10.1145/366622.366642 . S2CID 52800011 .
Hoare, RCA (1961). "Algorithme 65 : Trouver". Comm. ACM . 4 (7) : 321-322. doi : 10.1145/366622.366647 .
Hoare, RCA (1962). "Tri rapide" . Calcul. J. 5 (1) : 10-16. doi : 10.1093/comjnl/5.1.10 .(Réimprimé dans Hoare and Jones: Essays in computing science , 1989.)
Musser, David R. (1997). "Algorithmes de tri et de sélection introspectifs" . Logiciel : pratique et expérience . 27 (8) : 983–993. doi : 10.1002/(SICI)1097-024X(199708)27:8<983::AID-SPE117>3.0.CO;2-# .
Donald Knuth . L'art de la programmation informatique , volume 3 : tri et recherche , troisième édition. Addison-Wesley, 1997. ISBN 0-201-89685-0 . Pages 113-122 de la section 5.2.2 : Tri par échange.
Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest et Clifford Stein . Introduction aux algorithmes , deuxième édition. MIT Press et McGraw-Hill , 2001. ISBN 0-262-03293-7 . Chapitre 7 : Quicksort, pp. 145-164.
Faron Moller . Analyse de Quicksort . CS 332 : Conception d'algorithmes. Département d'informatique, Université de Swansea .
Martínez, C.; Roura, S. (2001). "Stratégies d'échantillonnage optimales dans Quicksort et Quickselect". SIAM J. Comput. 31 (3) : 683-705. CiteSeerX 10.1.1.17.4954 . doi : 10.1137/S0097539700382108 .
Bentley, JL; McIlroy, MD (1993). "Ingénierie d'une fonction de tri". Logiciel : pratique et expérience . 23 (11) : 1249-1265. CiteSeerX 10.1.1.14.8162 . doi : 10.1002/spe.4380231105 .

Liens externes

« Algorithmes de tri animés : tri rapide » . Archivé de l'original le 2 mars 2015 . Récupéré le 25 novembre 2008 . – démonstration graphique
"Algorithmes de tri animés : tri rapide (partition à 3 voies)" . Archivé de l'original le 6 mars 2015 . Récupéré le 25 novembre 2008 .
Structures de données ouvertes – Section 11.1.2 – Tri rapide , Pat Morin
Illustration interactive de Quicksort , avec procédure pas à pas du code

Languages

In other projects