Pourquoi le tri rapide est-il meilleur que les autres algorithmes de tri en pratique?

308

Dans un cours sur les algorithmes standard, on nous apprend que quicksort est en moyenne et dans le pire des cas. Dans le même temps, d'autres algorithmes de tri sont étudiés, qui sont dans le pire des cas (comme mergesort et heapsort ) et même un temps linéaire dans le meilleur des cas (comme bubblesort ) mais avec quelques besoins supplémentaires en mémoire.O ( n 2 ) O ( n log n )O(nlogn)O(n2)O(nlogn)

Après un rapide coup d'œil sur quelques temps supplémentaires, il est naturel de dire que le tri rapide ne devrait pas être aussi efficace que d'autres.

En outre, considérez que les étudiants apprennent dans les cours de programmation de base que la récursivité n’est pas très bonne en général car elle pourrait utiliser trop de mémoire, etc. Par conséquent (même si ce n’est pas un argument réel), cela donne à penser vraiment bon parce que c'est un algorithme récursif.

Pourquoi, alors, quicksort surpasse-t-il les autres algorithmes de tri en pratique? Est-ce que cela a à voir avec la structure des données du monde réel ? Cela a-t-il à voir avec le fonctionnement de la mémoire dans les ordinateurs? Je sais que certains souvenirs sont bien plus rapides que d'autres, mais je ne sais pas si c'est la véritable raison de cette performance contre-intuitive (comparée aux estimations théoriques).


Mise à jour 1: une réponse canonique indique que les constantes impliquées dans du cas moyen sont plus petites que les constantes impliquées dans d’autres algorithmes . Cependant, je n'ai pas encore vu de justification valable à cela, avec des calculs précis au lieu d'idées intuitives.O ( n log n )O(nlogn)O(nlogn)

Quoi qu’il en soit, il semble que la vraie différence se produise, comme le suggèrent certaines réponses, au niveau de la mémoire, où les implémentations tirent parti de la structure interne des ordinateurs, en utilisant, par exemple, le fait que la mémoire cache est plus rapide que la RAM. La discussion est déjà intéressante, mais j'aimerais quand même voir plus de détails en ce qui concerne la gestion de la mémoire, car il semble que la réponse y soit.


Mise à jour 2: Il existe plusieurs pages Web offrant une comparaison des algorithmes de tri, certaines plus sophistiquées que d'autres (plus particulièrement, tri-algorithms.com ). À part la présentation d'un bel outil visuel, cette approche ne répond pas à ma question.

Janoma
la source
2
Dans le cas le plus défavorable, le tri par fusion est , et le tri d’un tableau d’entiers dans lequel il existe une limite connue à la taille des entiers peut être effectué en un temps avec un tri de comptage. O ( n )O(nlogn)O(n)
Carl Mummert
13
sorting-algorithms.com a une comparaison assez approfondie des algorithmes de tri.
Joe
2
Ad Update 1: Je suppose que vous pouvez avoir une analyse rigoureuse ou des hypothèses réalistes. Je n'ai pas vu les deux. Par exemple, la plupart des analyses formelles ne comptent que des comparaisons.
Raphaël
9
Cette question a remporté un concours récent sur programmers.SE !
Raphaël
3
Question interessante. Il y a quelque temps, j'ai effectué des tests avec des données aléatoires et une implémentation naïve de tri rapide et de fusion. Les deux algorithmes ont plutôt bien fonctionné pour de petits ensembles de données (jusqu'à 100 000 éléments), mais après ce tri par fusion, ils se sont avérés bien meilleurs. Cela semble aller à l’encontre de l’hypothèse générale selon laquelle le tri rapide est si bon et je n’ai toujours pas trouvé d’explication. La seule idée que je puisse imaginer est que, normalement, le terme tri rapide est utilisé pour des algorithmes plus complexes comme le tri intro, et que l'implémentation naïve du tri rapide à pivot aléatoire n'est pas très bonne.
Giorgio

Réponses:

215

Réponse courte

L'argument de l'efficacité du cache a déjà été expliqué en détail. De plus, il existe un argument intrinsèque, pourquoi Quicksort est rapide. Si elles sont implémentées comme avec deux "pointeurs de croisement", par exemple ici , les boucles internes ont un corps très petit. Comme c'est le code exécuté le plus souvent, cela en vaut la peine.

Longue réponse

Tout d'abord,

Le cas moyen n'existe pas!

Comme le meilleur et le pire des cas sont rarement des extrêmes dans la pratique, une analyse de cas moyenne est effectuée. Mais toute analyse de cas moyenne suppose une certaine distribution d’intrants ! Pour le tri, le choix typique est le modèle de permutation aléatoire (supposé tacitement sur Wikipedia).

Pourquoi -Notation?O

L'élimination des constantes dans l'analyse des algorithmes est effectuée pour une raison principale: si les temps d'exécution exacts m'intéressent , j'ai besoin des coûts (relatifs) de toutes les opérations de base impliquées (même en ignorant les problèmes de mise en cache, de traitement en pipeline dans les processeurs modernes ...). L'analyse mathématique peut compter la fréquence d'exécution de chaque instruction, mais les temps d'exécution d'instructions simples dépendent des détails du processeur, par exemple si une multiplication d'entier sur 32 bits prend autant de temps que nécessaire.

Il y a deux issues:

  1. Correction d'un modèle de machine.

    Ceci est fait dans la série de livres de Don Knuth "The Art of Computer Programming" pour un ordinateur artificiel "typique" inventé par l'auteur. Dans le volume 3, vous trouverez les résultats moyens exacts pour de nombreux algorithmes de tri, par exemple:

    • :11.667(n+1)ln(n)1.74n18.74
    • Fusion:12.5nln(n)
    • Essaim: 16nln(n)+0.01n
    • Insertionsort: [ source ]2.25n2+7.75n3ln(n) Temps d'exécution de plusieurs algorithmes de tri

    Ces résultats indiquent que Quicksort est le plus rapide. Mais, cela n’est prouvé que sur la machine artificielle de Knuth, cela n’implique pas nécessairement quoi que ce soit pour, disons, votre PC x86. Notez également que les algorithmes se rapportent différemment pour les petites entrées:
    Temps d'exécution de plusieurs algorithmes de tri pour les petites entrées
    [ source ]

  2. Analyser les opérations de base abstraites .

    Pour le tri basé sur la comparaison, il s'agit généralement de swaps et de comparaisons clés . Dans les livres de Robert Sedgewick, par exemple «Algorithms» , cette approche est poursuivie. Vous y trouvez

    • : comparaisons et swaps en moyenne12nln(n)13nln(n)
    • Mergesort: comparaisons, mais jusqu’à accède au tableau (mergesort n’est pas basé sur un swap, nous ne pouvons donc pas le compter).1.44nln(n)8.66nln(n)
    • Insertionsort: comparaisons et échanges en moyenne.14n214n2

    Comme vous le voyez, cela ne permet pas facilement de comparer des algorithmes en tant qu’analyse d’exécution exacte, mais les résultats sont indépendants des détails de la machine.

Autres distributions d'entrée

Comme indiqué ci-dessus, les cas moyens concernent toujours une distribution d'intrants donnée, de sorte que l'on peut en envisager d'autres que des permutations aléatoires. Par exemple, des recherches ont été effectuées pour Quicksort avec des éléments égaux et il existe un bel article sur la fonction de tri standard en Java.

Sébastien
la source
8
Les résultats de type 2. peuvent être transformés en résultats de type 1. en insérant des constantes dépendantes de la machine. Par conséquent, je dirais que 2. est une approche supérieure.
Raphaël
2
@ Raphaël +1. Je suppose que vous supposez que la dépendance à la machine dépend également de la mise en œuvre, n'est-ce pas? Je veux dire, une machine rapide + une mauvaise mise en œuvre n'est probablement pas très efficace.
Janoma
2
@Janoma J'ai supposé que l'algorithme analysé était donné sous une forme très détaillée (comme l'analyse est détaillée) et que la mise en œuvre était aussi simple que possible. Mais oui, la mise en œuvre serait également prise en compte.
Raphaël
3
En réalité, l'analyse de type 2 est inférieure en pratique. Les machines du monde réel sont si compliquées que les résultats du type 2 ne peuvent pas être traduits de manière réaliste en type 1. Comparez cela au type 1: le traçage de durées de test expérimentales prend 5 minutes de travail.
Jules
4
@Jules: "le temps d'exécution expérimental" n'est pas du type 1; ce n'est pas une sorte d'analyse formelle et elle n'est pas transférable à d'autres machines. C'est pourquoi nous effectuons une analyse formelle, après tout.
Raphaël
78

Plusieurs points peuvent être soulevés à propos de cette question.

Quicksort est généralement rapide

Bien que Quicksort ait le comportement le plus défavorable avec , il est généralement rapide: en supposant une sélection de pivot aléatoire, il existe une très grande chance que nous choisissions un nombre qui sépare l'entrée en deux sous-ensembles de taille similaire, ce que nous voulons exactement. avoir.O(n2)

En particulier, même si nous choisissons un pivot qui crée une division de 10% à 90% toutes les 10 divisions (ce qui est une division meh), et une division 1 élément - élément sinon (qui est la pire division que vous puissiez obtenir) , notre temps d’exécution est toujours (notez que cela ferait exploser les constantes jusqu’à un point où le tri par fusion serait probablement plus rapide).n1O(nlogn)

Quicksort est généralement plus rapide que la plupart des tris

Quicksort est généralement plus rapide que les tris plus lents que (disons, le tri par insertion avec sa durée de fonctionnement ), tout simplement parce que, pour grand, leur durée de fonctionnement explose.O(nlogn)O(n2)n

Une bonne raison pour laquelle Quicksort est si rapide en pratique par rapport à la plupart des autres algorithmes tels que Heapsort, c’est parce qu’il est relativement efficace en cache. Son temps d'exécution est en fait , où est la taille du bloc. Heapsort, d’autre part, n’a pas une telle accélération: ce n’est pas du tout un moyen d’accéder efficacement à la mémoire cache.O(nlogn)O(nBlog(nB))B

La raison de cette efficacité du cache est qu’elle balaie linéairement l’entrée et la partitionne linéairement. Cela signifie que nous pouvons tirer le meilleur parti de chaque chargement de cache que nous faisons en lisant chaque numéro chargé dans le cache avant de l'échanger contre un autre. En particulier, l’algorithme ne tient pas compte de la cache, ce qui donne de bonnes performances de cache pour chaque niveau de cache, ce qui représente un autre gain.

L'efficacité du cache pourrait être encore améliorée en , où est la taille de notre mémoire principale. , si nous utilisons -way Quicksort. Notez que Mergesort a également la même efficacité de cache que Quicksort et que sa version k-way offre de meilleures performances (avec des facteurs constants inférieurs) si la mémoire est une contrainte sévère. Cela donne lieu au point suivant: nous devrons comparer Quicksort à Mergesort sur d’autres facteurs.MkO(nBlogMB(nB))Mk

Quicksort est généralement plus rapide que Mergesort

Cette comparaison concerne complètement des facteurs constants (si on considère le cas typique). En particulier, le choix est entre un choix sous-optimal du pivot pour Quicksort par rapport à la copie de la totalité de l'entrée pour Mergesort (ou la complexité de l'algorithme nécessaire pour éviter cette copie). Il s'avère que le premier est plus efficace: il n'y a pas de théorie derrière cela, il se trouve que c'est plus rapide.

Notez que Quicksort effectuera des appels plus récursifs, mais l’allocation d’espace de pile est peu coûteuse (presque gratuite en fait, tant que vous n’exploitez pas la pile) et vous le réutilisez. L'allocation d'un bloc géant sur le tas (ou sur votre disque dur, si est vraiment grand) coûte un peu plus cher, mais les deux sont des frais généraux pâles par rapport au travail mentionné ci-dessus.O ( log n ) O ( n )nO(logn)O(n)

Enfin, notez que Quicksort est légèrement sensible aux entrées qui se trouvent dans le bon ordre, auquel cas il peut ignorer certains échanges. Mergesort ne dispose pas de telles optimisations, ce qui rend Quicksort un peu plus rapide que Mergesort.

Utilisez le type qui convient à vos besoins

En conclusion: aucun algorithme de tri n'est toujours optimal. Choisissez celui qui convient à vos besoins. Si vous avez besoin d'un algorithme qui soit le plus rapide dans la plupart des cas, et cela ne vous dérange pas, il peut arriver que ce soit un peu lent, et si vous n'avez pas besoin d'un tri stable, utilisez Quicksort. Sinon, utilisez l'algorithme qui répond le mieux à vos besoins.

Alex ten Brink
la source
3
Votre dernière remarque est particulièrement précieuse. Un de mes collègues analyse actuellement les implémentations de Quicksort sous différentes distributions d’entrée. Certains d'entre eux se décomposent pour de nombreux doublons, par exemple.
Raphaël
4
O(n2)
8
"[T] il n'y a pas de théorie derrière cela, il arrive juste d'être plus rapide." Cette affirmation est très insatisfaisante du point de vue scientifique. Imaginez Newton en train de dire: "Les papillons volent, les pommes tombent: il n'y a pas de théorie derrière cela, les pommes tombent juste."
David Richerby
2
@ Alex ten Brink, que voulez-vous dire par «en particulier, l'algorithme est caché par la mémoire cache »?
Hibou57
4
@ David Richerby, «Cette déclaration est très insatisfaisante du point de vue scientifique»: il est peut-être simplement témoin d'un fait sans prétendre que nous devrions en être satisfaits. Certaines familles d'algorithmes souffrent d'un manque de formalisation complète; Les fonctions de hachage sont un exemple.
Hibou57
45

Dans l'un des didacticiels de programmation de mon université, nous avons demandé aux étudiants de comparer les performances de quicksort, mergesort, type d'insertion par rapport au list.sort intégré de Python (appelé Timsort ). Les résultats expérimentaux m'ont profondément surpris car le list.sort intégré fonctionnait tellement mieux que d'autres algorithmes de tri, même avec des instances qui effectuaient facilement le tri rapide, le crash de mergesort. Il est donc prématuré de conclure que la mise en œuvre habituelle du tri rapide est la meilleure dans la pratique. Mais je suis sûr que la mise en œuvre de quicksort, ou une version hybride de celle-ci, est bien meilleure.

C'est un bel article de blog de David R. MacIver expliquant Timsort comme une forme de fusion adaptative.

Dai
la source
17
@Raphael Pour résumer, Timsort est un type de fusion pour le type asymptotique plus un type d'insertion pour les entrées courtes plus quelques méthodes heuristiques pour gérer efficacement les données qui ont parfois une rafale déjà triée (ce qui se produit souvent dans la pratique). Dai: outre l'algorithme, list.sortbénéficie d'une fonction intégrée optimisée par les professionnels. Une comparaison plus juste aurait toutes les fonctions écrites dans la même langue avec le même niveau d'effort.
Gilles
1
@Dai: Vous pourriez au moins décrire avec quel type d'entrées (respectivement leur distribution) dans quelles circonstances (faible RAM, une mise en œuvre parallélisée, ...) vous avez obtenu vos résultats.
Raphaël
7
Nous avons testé sur une liste de nombres aléatoires et partiellement trié, complètement trié et inversement. C'était un cours d'introduction de 1ère année, donc ce n'était pas une étude empirique approfondie. Mais le fait qu’il soit maintenant officiellement utilisé pour trier les tableaux dans Java SE 7 et sur la plate-forme Android a un sens.
Dai
3
Cela a également été discuté ici: cstheory.stackexchange.com/a/927/74
Jukka Suomela
34

Je pense que l’une des principales raisons pour lesquelles QuickSort est si rapide par rapport à d’autres algorithmes de tri tient au fait qu’il est convivial au cache. Lorsque QS traite un segment d'un tableau, il accède aux éléments au début et à la fin du segment et se déplace vers le centre du segment.

Ainsi, lorsque vous démarrez, vous accédez au premier élément du tableau et une partie de la mémoire («emplacement») est chargée dans le cache. Et lorsque vous essayez d'accéder au deuxième élément, il est (probablement) déjà dans le cache, donc c'est très rapide.

D'autres algorithmes, comme Heapsort, ne fonctionnent pas comme cela, ils sautent souvent dans le tableau, ce qui les ralentit.

svick
la source
5
C'est une explication discutable: mergesort est également compatible avec le cache.
Dmytro Korduban
2
Je pense que cette réponse est fondamentalement juste, mais voici quelques détails youtube.com/watch?v=aMnn0Jq0J-E
rgrig
3
la constante multiplicative pour la complexité de la durée moyenne de la procédure de tri rapide est également meilleure (indépendamment du facteur de cache que vous avez mentionné).
Kaveh
1
Le point que vous avez mentionné n’est pas si important, comparé à d’autres bonnes propriétés de tri rapide.
MMS
1
@Kaveh: "la constante multiplicative pour la complexité de la durée moyenne du tri rapide est également meilleure" Avez-vous des données à ce sujet?
Giorgio
29

D'autres ont déjà indiqué que le temps d'exécution moyen asymptotique de Quicksort est supérieur (à la constante) à celui d'autres algorithmes de tri (dans certains contextes).

O(nlogn)

Notez qu'il existe de nombreuses variantes de Quicksort (voir par exemple la thèse de Sedgewick). Ils fonctionnent différemment sur différentes distributions d’entrée (uniformes, presque triées, presque inversement, de nombreux doublons, ...), et d’autres algorithmes pourraient être meilleurs pour certains.

k10

Raphaël
la source
20

O(nlgn)

ps: pour être précis, être meilleur que les autres algorithmes dépend de la tâche. Pour certaines tâches, il peut être préférable d’utiliser d’autres algorithmes de tri.

Voir également:

Kaveh
la source
3
@ Janoma, il s'agit du langage et du compilateur utilisés. Presque tous les langages fonctionnels (ML, Lisp, Haskell) peuvent faire des optimisations qui empêchent la pile de grandir, et des compilateurs plus intelligents pour les langages impératifs peuvent faire la même chose (GCC, G ++ et MSVC le font tous). L'exception notable est Java, qui n'effectuera jamais cette optimisation. Il est donc logique en Java de réécrire votre récurrence sous forme d'itération.
Rafe Kettler
4
@JD, vous ne pouvez pas utiliser l'optimisation d'appel final avec quicksort (du moins pas complètement), car elle s'appelle deux fois. Vous pouvez optimiser le second appel, mais pas le premier.
svick
1
@Janoma, vous n'avez pas vraiment besoin de l'implémentation récursive. Par exemple, si vous examinez l'implémentation de la fonction qsort en C, elle n'utilise pas d'appels récursifs. Par conséquent, l'implémentation devient beaucoup plus rapide.
Kaveh
1
Heapsort est également en place. Pourquoi QS est-il souvent plus rapide?
Kevin
6
23240
16

Θ(n2)Θ(nlogn)

La deuxième raison est qu'il effectue le in-placetri et fonctionne très bien avec les environnements de mémoire virtuelle.

UPDATE:: (après les commentaires de Janoma et de Svick)

Pour illustrer ceci mieux, laissez-moi vous donner un exemple en utilisant Merge Sort (car le tri par fusion est le prochain algorithme de tri largement adopté après le tri rapide, je pense) et vous indique d’où proviennent les constantes supplémentaires (à ma connaissance et pourquoi je pense Le tri rapide est préférable):

Considérons la séquence suivante:

12,30,21,8,6,9,1,7. The merge sort algorithm works as follows:

(a) 12,30,21,8    6,9,1,7  //divide stage
(b) 12,30   21,8   6,9   1,7   //divide stage
(c) 12   30   21   8   6   9   1   7   //Final divide stage
(d) 12,30   8,21   6,9   1,7   //Merge Stage
(e) 8,12,21,30   .....     // Analyze this stage

Si vous regardez bien comment se déroule la dernière étape, comparez les 12 premiers avec les 8 et les 8 plus petits. Maintenant 12 est ENCORE comparé à 21 et 12 passe ensuite et ainsi de suite. Si vous prenez la fusion finale, c'est-à-dire 4 éléments avec 4 autres éléments, cela entraîne de nombreuses comparaisons EXTRA en tant que constantes, ce qui n'est PAS le cas dans le tri rapide. C'est la raison pour laquelle le tri rapide est préféré.

0x0
la source
1
Mais qu'est-ce qui rend les constantes si petites?
svick
1
@svick Parce qu'ils sont triés in-placec'est-à-dire, aucune mémoire supplémentaire n'est requise.
0x0
Θ(nlgn)
15

D'après mon expérience de travail avec des données réelles, le tri rapide est un mauvais choix . Quicksort fonctionne bien avec des données aléatoires, mais les données du monde réel ne sont le plus souvent pas aléatoires.

En 2008, j'ai suivi un bug logiciel suspendu jusqu'à l'utilisation de quicksort. Un peu plus tard, j'ai écrit des implémentations simples de tri par insertion, tri rapide, tri par tas et par fusion et les ai testées. Mon type de fusion a surperformé tous les autres tout en travaillant sur de grands ensembles de données.

Depuis lors, le tri par fusion est mon algorithme de tri de choix. C'est élégant. C'est simple à mettre en œuvre. C'est un genre stable. Il ne dégénère pas en comportement quadratique comme le fait QuickSort. Je passe au tri par insertion pour trier les petits tableaux.

À de nombreuses occasions, je me suis retrouvé à penser qu'une mise en œuvre donnée fonctionnait étonnamment bien pour un tri rapide, mais seulement pour découvrir qu'elle n'était pas réellement un tri rapide. Parfois, la mise en œuvre bascule entre quicksort et un autre algorithme et parfois elle n'utilise pas du tout le tri rapide. À titre d'exemple, les fonctions qsort () de GLibc utilisent en réalité le tri par fusion. Ce n'est que si l'allocation de l'espace de travail échoue qu'elle se réduit à un tri rapide sur place qu'un commentaire de code appelle "l'algorithme le plus lent" .

Edit: les langages de programmation tels que Java, Python et Perl utilisent également le tri par fusion, ou plus précisément un dérivé, comme le tri Timsort ou le tri par fusion pour les grands ensembles et le tri par insertion pour les petits. (Java utilise également le tri rapide à double pivot, ce qui est plus rapide que le tri rapide.)

Erwan Legrand
la source
J'avais vu quelque chose de similaire à cela parce que nous ajoutions / utilisions en permanence pour insérer dans un lot de données déjà triées. Vous pouvez contourner ce problème en moyenne en utilisant un tri rapide aléatoire (et vous laisser surprendre par un type rare et extrêmement lent), ou vous pouvez tolérer un type toujours plus lent qui ne prend jamais un temps surprenant. Parfois, vous avez également besoin de stabilité de tri. Java est passé d’utiliser le tri par fusion à une variante de tri rapide.
Rob
@Rob Ceci n'est pas exact. Java utilise encore une variante de mergesort (Timsort) à ce jour. Il utilise également une variante de quicksort (quicksort à double pivot).
Erwan Legrand
14

1 - Le tri rapide est en place (ne nécessite pas de mémoire supplémentaire, sauf un montant constant.)

2 - Le tri rapide est plus facile à mettre en œuvre que d’autres algorithmes de tri efficaces.

3 - Le tri rapide a des facteurs constants de durée d'exécution plus petits que les autres algorithmes de tri efficaces.

Mise à jour: pour le tri par fusion, vous devez effectuer une "fusion", qui nécessite un ou plusieurs tableaux supplémentaires pour stocker les données avant la fusion. mais en quelque sorte, vous ne le faites pas. C'est pourquoi le tri rapide est en place. Il existe également des comparaisons supplémentaires pour la fusion qui augmentent les facteurs constants dans le type de fusion.

MMS
la source
3
Avez-vous déjà vu des implémentations avancées Quicksort sur place et en place? Ce sont beaucoup de choses mais pas "faciles".
Raphaël
2
Le numéro 2 ne répond pas du tout à ma question et les numéros 1 et 3 nécessitent une justification appropriée, à mon avis.
Janoma
@ Raphaël: Ils sont faciles. Il est beaucoup plus facile d'implémenter un tri rapide sur place en utilisant un tableau plutôt que des pointeurs. Et il n'est pas nécessaire d'être itératif pour être en place.
MMS
Les tableaux pour la fusion ne sont pas si mauvais. Une fois que vous avez déplacé un élément d'une pile source vers la pile de destination, il n'a plus besoin de s'y trouver. Si vous utilisez des tableaux dynamiques, la surcharge de mémoire est constante lors de la fusion.
Oskar Skog
@ 1 Mergesort peut aussi être en place. @ 2 Qu'est-ce qui définit l'efficacité? J'aime les fusions parce que c'est très simple et pourtant efficace à mon avis. @ 3 Non pertinent lorsque vous triez de grandes quantités de données et nécessite que l'algorithme soit implémenté efficacement.
Oskar Skog
11

Dans quelles conditions un algorithme de tri spécifique est-il réellement le plus rapide?

Θ(log(n)2)Θ(nlog(n)2)

Θ(nk)Θ(nm)k=2#number_of_Possible_valuesm=#maximum_length_of_keys

3) La structure de données sous-jacente est-elle composée d'éléments liés? Oui -> toujours utiliser le tri par fusion sur place. Il existe à la fois des solutions faciles à mettre en œuvre de taille fixe ou des systèmes de fusion ascendante en place adaptatifs (c'est-à-dire naturels) pour les structures de données liées. plus rapide que tout autre type de classement général basé sur la comparaison, même plus rapide que le tri rapide.

Θ(n)

5) La taille des données sous-jacentes peut-elle être liée à une taille petite à moyenne? Par exemple, n <10 000 ... 100 000 000 (en fonction de l'architecture sous-jacente et de la structure de données)? Oui -> utilisez le tri bitonique ou Batcher impair-pair mergesort. Goto 1)

Θ(n)Θ(n2)Θ(nlog(n)2)Dans le pire des cas, le temps d'exécution est connu, ou essayez peut-être de trier les peignes. Je ne suis pas sûr que les types de coquilles ou de peignes fonctionnent assez bien dans la pratique.

Θ(log(n))Θ(n)Θ(n)Θ(log(n))Θ(n2)Θ(n)Θ(n)Θ(log(n))Θ(nlog(n))

Θ(nlog(n))

Conseils d'implémentation pour le tri rapide:

Θ(n)Θ(log(n))Θ(nlogk(k1))

2) Il existe des variantes itératives de tri rapide ascendantes, mais, autant que je sache, elles ont les mêmes limites d'espace et de temps asymptotiques que les bornes descendantes, avec les inconvénients d'être difficiles à mettre en œuvre (par exemple, gérer explicitement une file d'attente). Mon expérience est que pour des raisons pratiques, celles-ci ne valent jamais la peine d'être considérées.

Conseils d'implémentation pour mergesort:

1) Bottom-Up mergesort est toujours plus rapide que Top-Down Fusion, car il ne nécessite aucun appel récursif.

2) le très naïf mergesort peut être accéléré en utilisant un double tampon et commute le tampon au lieu de copier les données du tableau temporel après chaque étape.

3) Pour de nombreuses données du monde réel, le mergesort adaptatif est beaucoup plus rapide que le mergesort de taille fixe.

Θ(k)Θ(log(k))Θ(1)Θ(n)

D'après ce que j'ai écrit, il est clair que le tri rapide n'est souvent pas l'algorithme le plus rapide, sauf lorsque les conditions suivantes sont toutes réunies:

1) il y a plus que "quelques" valeurs possibles

2) la structure de données sous-jacente n'est pas liée

3) nous n'avons pas besoin d'un ordre stable

4) les données sont suffisamment volumineuses pour que le temps d'exécution asymptotique légèrement sous-optimal d'une trieuse bitonique ou d'un Batcher impair-pair mergesort entre en jeu

5) les données ne sont pas presque triées et ne se composent pas de plus grosses pièces déjà triées

6) nous pouvons accéder à la séquence de données simultanément à partir de plusieurs endroits

Θ(log(n))Θ(n)

ps: Quelqu'un doit m'aider à mettre en forme le texte.

Franki
la source
(5): L'implémentation de tri d'Apple vérifie une exécution en ordre croissant ou décroissant au début et à la fin de la baie. Ceci est très rapide s’il n’ya pas beaucoup d’éléments de ce type et peut être traité de manière très efficace s’il en existe plus de n / ln n. Concaténer deux tableaux triés et trier le résultat, et vous obtenez une fusion
gnasher729
8

La plupart des méthodes de tri doivent déplacer les données par petites étapes (par exemple, le tri par fusion effectue les modifications localement, puis fusionne ce petit fichier, puis un plus grand. ..). En conséquence, vous avez besoin de nombreux mouvements de données si les données sont éloignées de leur destination.

ab

fernand0
la source
5
Votre argumentation concernant le tri rapide ou le tri par fusion ne tient pas. Quicksort commence par un grand mouvement, puis effectue des mouvements de plus en plus petits (environ la moitié de la taille de chaque étape). Le tri par fusion commence par un petit mouvement, puis effectue des mouvements de plus en plus grands (environ deux fois plus gros à chaque étape). Cela ne signifie pas que l'un soit plus efficace que l'autre.
Gilles