Pourquoi quicksort est-il meilleur que mergesort?

comme de nombreuses personnes l'ont fait remarquer, la performance moyenne de quicksort est plus rapide que celle de mergesort. mais ceci n'est vrai que si vous supposez un temps constant pour accéder à n'importe quelle pièce de mémoire à la demande.

dans RAM cette hypothèse n'est généralement pas trop mauvaise (ce n'est pas toujours vrai à cause des caches, mais ce n'est pas trop mal). Cependant si votre structure de données est assez grande pour vivre sur le disque, alors quicksort obtient tué par le le fait que votre disque Moyen fait quelque chose comme 200 recherches aléatoires par seconde. Mais ce même disque n'a aucun problème de lecture ou d'écriture de mégaoctets par seconde de données séquentiellement. C'est exactement ce que fait mergesort.

donc si les données doivent être triées sur le disque, vous voulez vraiment, vraiment utiliser une certaine variation sur mergesort. (Généralement, vous raccourcissez les listes secondaires, puis commencez à les fusionner au-dessus d'un certain seuil de taille.)

en outre, si vous devez faire n'importe quoi avec des ensembles de données de cette taille, réfléchissez bien à la façon d'éviter cherche à disque. Par exemple, c'est la raison pour laquelle il est recommandé de laisser tomber les index avant de faire de gros chargements de données dans les bases de données, puis de reconstruire l'index plus tard. Maintenir l'index pendant la charge signifie constamment chercher à disque. Par contre, si vous supprimez les index, alors la base de données peut reconstruire l'index en triant d'abord les informations à traiter (en utilisant un mergesort bien sûr!) et puis le chargement dans une structure de données BTREE pour l'index. (BTREEs sont naturellement maintenus dans l'ordre, de sorte que vous pouvez charger un à partir d'un ensemble de données triées avec peu de recherches sur le disque.)

il y a eu un certain nombre d'occasions où comprendre comment éviter les recherches de disques m'a permis de faire des travaux de traitement de données prennent des heures plutôt que des jours ou des semaines.

en fait, QuickSort est O(n ² ). Son cas moyen durée de fonctionnement est O(nlog(n)), mais son pire cas est O (n ² ), qui se produit lorsque vous l'exécutez sur une liste qui contient peu d'éléments uniques. La randomisation prend O (n). Bien sûr, cela ne change pas son pire cas, il empêche juste un utilisateur malveillant de faire votre sort prend beaucoup de temps.

QuickSort est plus populaire parce qu'il:

1. Est en place (MergeSort nécessite davantage de mémoire linéaires à nombre d'éléments à trier).
2. a une petite constante cachée.

Le Animé Algorithmes de Tri montre un certain nombre d'algorithmes sur 4 des conditions initiales différentes (aléatoire, presque triées, inversé, quelques unique) et pourrait aider.

" et pourtant la plupart des gens utilisent Quicksort au lieu de Mergesort. Pourquoi est-ce?"

une raison psychologique qui n'a pas été donnée est simplement que Quicksort est plus habilement nommé. ie bon marketing.

Oui, Quicksort avec triple partioning est probablement l'un des meilleurs algorithmes de tri à usage général, mais il n'y a pas passer outre le fait que le tri "rapide" sonne beaucoup plus puissant que le tri "Fusion".

comme d'autres l'ont noté, le pire cas de Quicksort est O(N^2), tandis que mergesort et heapsort restent à O(nlogn). En moyenne, cependant, les trois sont O(nlogn); ils sont donc pour la grande majorité des cas comparables.

ce qui rend Quicksort meilleur en moyenne est que la boucle interne implique de comparer plusieurs valeurs avec une seule, tandis que sur les deux autres termes sont différents pour chaque comparaison. En d'autres termes, Quicksort fait la moitié moins de deux autres algorithmes. Sur la performance des CPUs modernes est fortement dominé par les temps d'accès, de sorte Qu'en fin de Compte Quicksort finit par être un grand premier choix.

j'aimerais ajouter que des trois algorithmes mentionnés jusqu'à présent (mergesort, quicksort et heap sort), seul mergesort est stable. Qui est, l'ordre ne change pas pour les valeurs qui ont la même clé. Dans certains cas, cela est souhaitable.

mais, à vrai dire, dans les situations pratiques, la plupart des gens n'ont besoin que d'une bonne performance moyenne et quicksort est... quick =)

Tous les algorithmes de tri ont leurs hauts et leurs bas. Voir Wikipedia article pour les algorithmes de tri pour une bonne vue d'ensemble.

Mu! Quicksort est pas mieux, il est bien adapté pour un autre type d'application, de mergesort.

Mergesort vaut la peine de considérer si la vitesse est de l'essence, la mauvaise performance du pire cas ne peut pas être tolérée, et l'espace supplémentaire est disponible. 1

Vous avez déclaré qu'ils "sont tous les deux O(nlogn) [...]". Ce qui est faux. "Quicksort utilise environ n^2/2 comparaisons dans le pire des cas." 1 .

cependant la propriété la plus importante selon mon expérience est la facilité d'implémentation de l'accès séquentiel que vous pouvez utiliser lors du tri en utilisant des langages de programmation avec le paradigme impératif.

1 Sedgewick, Algorithmes

Quicksort est l'algorithme de tri le plus rapide dans la pratique mais a un certain nombre de cas pathologiques qui peuvent le faire fonctionner aussi mal que O(n2).

Heapsort est assuré de fonctionner en O (N*ln(n)) et ne nécessite qu'un stockage supplémentaire limité. Mais il y a beaucoup de citations de tests du monde réel qui montrent que l'aéroport d'heapsort est beaucoup plus lent que quicksort en moyenne.

à Partir de l'entrée de Wikipedia sur Quicksort :

Quicksort est également en concurrence avec mergesort, un autre type récursif algorithme, mais avec l'avantage de dans le pire des cas Θ(nlogn) durée de fonctionnement. Mergesort est un type stable, contrairement quicksort et heapsort, et peut être facilement adaptable pour fonctionner sur des listes et très grandes listes stockées sur les supports lents d'accès tels que les disques stockage ou stockage relié au réseau. Bien quicksort peut être écrit à fonctionner sur les listes liées, il sera souvent souffrent de mauvais choix de pivot sans l'accès aléatoire. Le principal inconvénient de mergesort est que, lors de l'exploitation sur les tableaux, il nécessite Θ(n) auxiliaire l'espace dans le meilleur des cas, alors que la variante de quicksort avec en place le partitionnement et la queue utilise la récursivité seulement Θ(logn) espace. (Notez que lorsque exploitation sur des listes liées, Fusion nécessite seulement une petite quantité constante de mémoire auxiliaire.)

L'explication de Wikipedia est:

en général, quicksort est beaucoup plus rapide dans la pratique que les autres algorithmes Θ(nlogn), parce que sa boucle interne peut être mise en œuvre efficacement sur la plupart des architectures, et dans la plupart des données du monde réel, il est possible de faire des choix de conception qui minimisent la probabilité d'exiger du temps quadratique.

Quicksort

Mergesort

je pense qu'il y a aussi des problèmes avec la quantité de stockage nécessaire pour les fusions (qui est Ω(n)) que les implémentations quicksort n'ont pas. Dans le pire des cas, il s'agit de la même quantité de temps algorithmique, mais mergesort nécessite plus de stockage.

Quicksort n'est pas mieux que mergesort. Avec O(N^2) (le pire cas qui se produit rarement), quicksort est potentiellement beaucoup plus lent que le O(nlogn) du type de fusion. Quicksort a moins de frais généraux, donc avec les petits n et les ordinateurs lents, c'est mieux. Mais les ordinateurs sont aujourd'hui si vite que la charge supplémentaire d'un mergesort est négligeable, et le risque d'un ralentissement du quicksort l'emporte de loin sur l'insignifiant surcharge de mergesort dans la plupart des cas.

en outre, un mergesort feuilles éléments avec des clés identiques dans leur ordre d'origine, un attribut utile.

je voudrais ajouter aux grandes réponses existantes quelques mathématiques sur la façon dont le QuickSort se comporte lorsqu'il s'écarte du meilleur cas et à quel point c'est probable, ce qui j'espère aidera les gens à comprendre un peu mieux pourquoi le cas O(N^2) n'est pas une réelle préoccupation dans les implémentations plus sophistiquées de QuickSort.

en dehors des questions d'accès aléatoire, il y a deux facteurs principaux qui peuvent avoir un impact sur la performance de QuickSort et ils sont tous deux liés à la façon dont le pivot se compare les données triées.

1) Un petit nombre de touches dans les données. Un ensemble de données de la même valeur va trier en n^2 temps sur un QuickSort 2-partition vanille parce que toutes les valeurs sauf l'emplacement de pivot sont placés sur un côté à chaque fois. Les implémentations modernes traitent cela par des méthodes telles que l'utilisation d'un tri de partition 3. Ces méthodes s'exécutent sur un ensemble de données de même valeur en O(n) time. Ainsi, l'utilisation d'une telle implémentation signifie qu'un input avec un petit nombre de les touches améliorent en fait le temps de performance et ne sont plus un problème.

2) une très mauvaise sélection du pivot peut causer le pire cas de performance. Dans un cas idéal, le pivot sera toujours tel que 50% des données sont plus petites et 50% des données sont plus grandes, de sorte que l'entrée sera brisée en deux pendant chaque itération. Cela nous donne n comparaisons et swaps fois log-2(n) récursions pour O (N*logn) temps.

Combien la non-idéal de pivot de la sélection affecter le temps d'exécution?

considérons un cas où le pivot est systématiquement choisi de sorte que 75% des données se trouvent d'un côté du pivot. C'est toujours O(N*logn) mais maintenant la base du log a changé à 1/0.75 ou 1,33. La relation dans la performance lors du changement de base est toujours une constante représentée par log(2)/log(newBase). Dans ce cas, cette constante est de 2,4. Cette qualité de choix du pivot prend donc 2,4 fois plus de temps que l'idéal.

à quelle vitesse cela empire-t-il?

Pas très rapide jusqu'à ce que le pivot choix gets (systématiquement) très mauvais:

• de 50% sur un côté: (cas idéal)
• 75% sur un côté: 2,4 fois plus long
• 90% sur un côté: 6,6 fois plus long
• 95% sur un côté: de 13,5 fois plus longtemps
• 99% sur un côté: 69 fois plus longtemps

comme nous approchons 100% d'un côté la partie logarithmique de l'exécution approche n et l'exécution entière approche asymptotiquement O(N^2).

dans une implémentation naïve de QuickSort, des cas tels qu'un tableau trié (pour le 1er élément pivot) ou un tableau trié à l'envers (pour le dernier élément pivot) produiront de manière fiable un temps D'exécution O(N^2) du pire cas. En outre, les implémentations avec une sélection de pivot prévisible peuvent être soumises à DoS attaque par des données conçues pour produire une exécution dans le pire des cas. Les implémentations modernes évitent cela par une variété de méthodes, telles que la randomisation des données avant le tri, le choix de la médiane de 3 index choisis au hasard, etc. Avec cette randomisation dans le mélange, nous avons 2 cas:

• petit ensemble de données. Le cas le plus défavorable est raisonnablement possible, mais O(N^2) n'est pas catastrophique car n est suffisamment petit pour que n^2 soit aussi petit.
• Grand ensemble de données. Le pire est possible en théorie, mais pas dans la pratique.

quelle probabilité avons-nous de voir une performance terrible?

chances extrêmement petite . Considérons une sorte de 5000 valeurs:

notre mise en œuvre hypothétique choisira un pivot en utilisant une médiane de 3 index choisis au hasard. Nous considérerons les pivots qui se situent entre 25% et 75% comme étant" bons " et les pivots qui se situent entre 0% et 25% ou entre 75% et 100% sont "mauvais". Si vous regardez la distribution de probabilité en utilisant la médiane de 3 indices aléatoires, chaque récursion a une chance de 11/16 de finir avec un bon pivot. Faisons deux hypothèses prudentes (et fausses) pour simplifier les calculs:

1. les bons pivots sont toujours à 25%/75% et fonctionnent à 2,4*cas idéal. Nous n'obtenons jamais une séparation idéale ou une séparation meilleure que 25/75.

2. les mauvais pivots sont toujours les pires et ne contribuent essentiellement rien à la solution.

notre implémentation de QuickSort s'arrêtera à n=10 et passera à une sorte d'insertion, nous avons donc besoin de 22 partitions à pivot de 25%/75% pour casser l'entrée de 5.000 valeurs jusqu'ici. (10*1.333333^22 > 5000) ou, nous avons besoin de 4990 pivots du pire cas. Gardez à l'esprit que si nous accumulons 22 bons pivots à n'importe quel point alors le tri se terminera, donc le pire cas ou n'importe quoi près de lui nécessite extrêmement mauvaise chance. S'il nous a fallu 88 récursions pour réaliser effectivement les 22 bons pivots nécessaires pour trier vers le bas à n=10, ce serait 4*2,4*cas idéal ou environ 10 fois le temps d'exécution du cas idéal. Dans quelle mesure est-il probable que nous et non réalisions les 22 bons pivots requis après 88 récursions?

Binomial les distributions de probabilité peuvent répondre à cela, et la réponse est d'environ 10^-18. (n est 88, k est 21, P est 0,6875) votre utilisateur est environ mille fois plus susceptible d'être frappé par la foudre dans la 1 seconde qu'il faut pour cliquer [trier] qu'ils ne le sont pour voir que 5,000 article trier exécuter pire que 10*cas idéal. Cette chance s'amenuise au fur et à mesure que l'ensemble de données s'élargit. Voici quelques tailles de tableau et leurs chances correspondantes de courir plus de 10 * idéal:

• Matrice de 640 éléments: 10^-13 (nécessite 15 bons points de pivot de 60 essaie)
• Tableau de 5 000 articles: 10^-18 (nécessite 22 bonnes pivots de 88 essaie)
• Tableau de 40.000 postes:10^-23 (nécessite 29 bon pivots de 116)

rappelez-vous que c'est avec deux hypothèses prudentes qui sont pires que la réalité. Donc la performance réelle est encore meilleure, et le reste la probabilité est plus proche de l'idéal que non.

enfin, comme d'autres l'ont mentionné, même ces cas absurdement invraisemblables peuvent être éliminés en passant à un tri en tas si la pile de récursions va trop profond. Donc le TLDR est que, pour de bonnes implémentations de QuickSort, le pire cas n'existe pas vraiment parce qu'il a été conçu et l'exécution se termine dans le temps O(N*logn).

la réponse pencherait légèrement vers quicksort W. R. t to changes brought with DualPivotQuickSort for primitive values . Il est utilisé dans JAVA 7 pour trier dans java.util.Tableaux

It is proved that for the Dual-Pivot Quicksort the average number of
comparisons is 2*n*ln(n), the average number of swaps is 0.8*n*ln(n),
whereas classical Quicksort algorithm has 2*n*ln(n) and 1*n*ln(n)
respectively. Full mathematical proof see in attached proof.txt
and proof_add.txt files. Theoretical results are also confirmed
by experimental counting of the operations.

vous pouvez trouver L'implementation JAVA7 ici - http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/7-b147/java/util/Arrays.java

Plus Impressionnant Lecture sur DualPivotQuickSort - http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628

bien qu'ils soient tous les deux dans la même classe de complexité, cela ne signifie pas qu'ils ont tous les deux la même durée d'exécution. Quicksort est généralement plus rapide que mergesort, juste parce qu'il est plus facile de coder une implémentation serrée et les opérations qu'il fait peuvent aller plus vite. C'est parce que quicksort est généralement plus rapide que les gens l'utilisent à la place de mergesort.

cependant! Personnellement, je vais souvent utiliser mergesort ou une variante de quicksort qui se dégrade à mergesort lorsque quicksort ne mal. Rappeler. Quicksort est seulement O (N log N) sur moyenne . C'est pire des cas est O(n^2)! Mergesort est toujours O (N log n). Dans les cas où la performance en temps réel ou la réactivité est un must et vos données d'entrée pourraient provenir d'une source malveillante, vous ne devez pas utiliser quicksort simple.

Quicksort a une meilleure moyenne complexité de cas, mais dans certaines applications, il est le mauvais choix. Quicksort est vulnérable aux attaques par déni de service. Si un attaquant peut choisir l'entrée à trier, il peut facilement construire un ensemble qui prend le pire temps complexité de o(N^2).

la complexité moyenne des cas de Mergesort et la complexité du pire cas sont les mêmes, et en tant que tel ne souffre pas le même problème. Cette propriété de fusion-tri rend également le choix supérieur pour les systèmes en temps réel-précisément parce qu'il n'y a pas de cas pathologiques qui font qu'il tourne beaucoup, beaucoup plus lentement.

Je suis un plus grand fan de Mergesort que de Quicksort, pour ces raisons.

toutes choses étant égales par ailleurs, je m'attends à ce que la plupart des gens utilisent ce qui est le plus commodément disponible, et cela tend à être qsort(3). Autre que ce quicksort est connu pour être très rapide sur les tableaux, tout comme mergesort est le choix commun pour les listes.

ce que je me demande, c'est pourquoi il est si rare de voir radix ou une sorte de seau. Ils sont O( n), au moins sur les listes liées et tout ce qu'il faut c'est une méthode pour convertir la clé en un nombre ordinal. (les cordes et les flotteurs fonctionnent très bien.)

dans d'autres nouvelles, les flotteurs peuvent être triés comme entiers, mais vous devez tourner le les nombres négatifs autour de la suite.

Edit: En fait, voici une façon encore plus vicieuse de trier les flotteurs-comme-entiers: http://www.stereopsis.com/radix.html . Notez que le truc de retournement de bits peut être utilisé quel que soit l'algorithme de tri que vous utilisez réellement...

C'est difficile à dire.Le pire de MergeSort est n (log2n) - n+1,ce qui est exact si n égale 2^k(j'ai déjà prouvé cela).Et pour tout n,c'est entre (n lg n - n + 1) et (n lg n + n + O(lg n)).Mais pour quickSort, son meilleur est nlog2n (aussi n égale 2^k).Si vous divisez Mergesort par quickSort,il est égal à un quand n est infini.Donc, c'est comme si le pire des cas de fusion est meilleur que le meilleur des cas de QuickSort,pourquoi utilisons-nous quicksort?Mais rappelez-vous,MergeSort n'est pas en place,il faut 2N memeroy de l'espace.Et MergeSort a également besoin de faire de nombreuses copies de tableaux,que nous n'incluons pas dans l'analyse de l'algorithme.En un mot, MergeSort est vraiment plus rapide que quicksort dans theroy, mais en réalité vous devez considérer l'espace de mémoire,le coût de la copie de tableau, la fusion est plus lente que le tri rapide.Une fois j'ai fait une expérience où on m'a donné 1000000 chiffres en java par classe aléatoire,et il a fallu 2610ms par mergesort,1370ms par quicksort.

pourquoi Quicksort est-il bon?

• QuickSort prend N^2 dans le pire des cas et NlogN en moyenne. Le pire des cas se produit lorsque les données sont triées. Cela peut être atténué par un mélange aléatoire avant le début du tri.
• QuickSort ne prend pas de mémoire supplémentaire qui est prise par le tri de fusion.
• si l'ensemble de données est grand et il ya des éléments identiques, la complexité de Quicksort réduit en utilisant 3 voie partition. Plus le nombre d'articles identiques mieux la sorte. Si tous les articles sont identiques, il trie dans le temps linéaire. [C'est l'implémentation par défaut dans la plupart des bibliothèques]

Quicksort est-il toujours meilleur que Mergesort?

pas vraiment.

• Mergesort est stable, mais Quicksort ne l'est pas. Donc, si vous avez besoin de stabilité dans la sortie, vous utiliserez Mergesort. La stabilité est nécessaire dans de nombreuses applications pratiques.
• la mémoire est bon marché de nos jours. Ainsi, si la mémoire supplémentaire utilisée par Mergesort n'est pas critique pour votre application, il n'y a aucun mal à utiliser Mergesort.

Note: en java, tableaux.la fonction sort() utilise Quicksort pour les types de données primitifs et Mergesort pour les types de données objet. Parce que les objets consomment la mémoire au-dessus, donc ajouté un petit au-dessus pour Mergesort peut ne pas être un problème pour point de vue des performances.

référence : regardez les vidéos de QuickSort de semaine 3, cours D'algorithmes de Princeton à Coursera

sort rapide est le pire des cas O (N^2), cependant, le cas moyen effectue systématiquement tri de fusion. Chaque algorithme est O (nlogn), mais vous devez vous rappeler que lorsque vous parlez de Big O, nous laissons de côté les facteurs de complexité inférieurs. Quick sort a des améliorations significatives par rapport à merge sort quand il s'agit de facteurs constants.

nécessite aussi de la mémoire O(2n), tandis que le tri rapide peut être fait en place (nécessitant seulement O(n)). C'est une autre raison que le tri rapide est généralement préféré au tri de fusion.

informations supplémentaires:

le pire cas de tri rapide se produit lorsque le pivot est mal choisi. Prenons l'exemple suivant:

[5, 4, 3, 2, 1]

si le pivot est choisi comme le plus petit ou le plus grand nombre dans le groupe alors le tri rapide s'exécute en O(N^2). La probabilité de choisir l'élément qui est le plus grand ou le plus petit de 25% de la liste est de 0,5. Que donne l'algorithme de 0,5 chance d'être un bon pivot. Si nous employons un algorithme de choix de pivot typique (par exemple choisir un élément aléatoire), nous avons 0,5 chance de choisir un bon pivot pour chaque choix d'un pivot. Pour les collections de grande taille, la probabilité de toujours choisir un pivot faible est de 0,5 * N. Basé sur cette probabilité, le tri rapide est efficace pour le cas moyen (et typique).

dans merge-sort, l'algorithme général est:

1. Triez le sous-tableau de gauche
2. trier le sous-tableau de droite
3. fusionner les 2 sous-tableaux triés

au niveau supérieur, la fusion des deux sous-tableaux triés implique de traiter des éléments N.

un niveau en dessous de cela, chaque itération de l'étape 3 implique de traiter avec les éléments n / 2, mais vous devez répéter ce processus à deux reprises. Donc vous avez toujours affaire à 2 * N/2 == N éléments.

un niveau en dessous de cela, vous fusionnez 4 * N/4 == N éléments, et ainsi de suite. Chaque profondeur dans la pile récursive implique la fusion du même nombre d'éléments, à travers tous les appels pour cette profondeur.

d'Envisager le tri rapide de l'algorithme de la place:

1. Choisissez un point de pivot
2. placer le point de pivot à la bonne place dans le tableau, avec tous des éléments plus petits à gauche, et des éléments plus grands à droite
3. trier la gauche-subarray
4. trier la droite-subarray

au niveau supérieur, vous avez affaire à un tableau de taille N. vous choisissez alors un point de pivot, mettez-le dans sa position correcte, et peut ensuite l'ignorer complètement pour le reste de l'algorithme.

un niveau en dessous de cela, vous avez affaire à 2 sous-tableaux qui ont une taille combinée de N-1 (c'est-à-dire soustraire le point de pivot antérieur). Vous choisissez un point de pivot pour chaque sous-tableau, qui vient jusqu'à 2 points de pivot supplémentaires.

un niveau en dessous de cela, vous avez affaire à 4 sous-tableaux avec la taille combinée N-3, pour les mêmes raisons que ci-dessus.

Puis N-7... Puis N-15... Puis N-32...

la profondeur de votre pile récursive reste approximativement la même (logN). Avec merge-sort, vous avez toujours affaire à une fusion de n-element, à travers chaque niveau de la pile récursive. Avec le tri rapide cependant, le nombre d'éléments que vous traitez diminue lorsque vous descendez la pile. Par exemple, si vous regardez la profondeur à mi - chemin à travers la pile récursive, le nombre d'éléments dont vous avez à traiter est N - 2^((logN)/2)) == N-sqrt(N).

Avertissement: Sur la fusion de tri, car vous divisez le tableau en 2 exactement égale morceaux à chaque fois, la profondeur de récursivité est exactement logN. Sur tri rapide, parce que votre pivot point est peu probable d'être exactement au milieu du tableau, la profondeur de votre pile récursive peut être légèrement plus grande que logN. Je n'ai pas fait le calcul pour voir à quel point ce facteur et le facteur décrit ci-dessus jouent un rôle important dans la complexité de l'algorithme.

quand j'ai expérimenté les deux algorithmes de tri, en comptant le nombre d'appels récursifs, quicksort a toujours moins d'appels récursifs que mergesort. C'est parce que quicksort a des pivots, et les pivots ne sont pas inclus dans les prochains appels récursifs. De cette façon, quicksort peut atteindre le scénario de base récursif plus rapidement que mergesort.

contrairement à Merge Sort Quick Sort n'utilise pas un espace auxiliaire. Tandis que le Sort de fusion utilise un espace auxiliaire O (n). Mais le Sort de Fusion a la complexité de temps la plus mauvaise du O(nlogn) tandis que la complexité de cas la plus mauvaise du Sort rapide est O (N^2) qui se produit lorsque le tableau est déjà trié.

Petits ajouts rapide vs fusion de toutes sortes.

aussi, il peut dépendre du type d'articles de tri. Si l'accès aux articles, le swap et les comparaisons ne sont pas des opérations simples, comme comparer des entiers dans la mémoire plane, alors le tri de fusion peut être l'algorithme préférable.

par exemple , nous trions les articles en utilisant le protocole réseau sur le serveur distant.

aussi, dans les conteneurs personnalisés comme" liste liée", LES ne sont pas un avantage de tri rapide.

1. Fusionner trier sur la liste liée, n'ont pas besoin de mémoire supplémentaire. 2. L'accès aux éléments dans quick sort n'est pas séquentiel (en mémoire)

quelque Chose à considérer est la mémoire. Mergesort nécessite un tableau supplémentaire, disons un "tableau espace de travail". Si votre mémoire est à peine assez grande pour stocker votre tableau original, alors mergesort ne fonctionnera pas.

Quick sort est un algorithme de tri en place, donc il convient mieux pour les tableaux. Le tri de fusion d'autre part nécessite un stockage supplémentaire de O(N), et est plus approprié pour les listes liées.

Contrairement aux tableaux, dans liked list nous pouvons insérer des éléments au milieu avec l'espace O(1) et le temps O(1), donc l'opération de fusion dans merge sort peut être implémentée sans espace supplémentaire. Cependant, l'allocation et la dé-allocation de l'espace supplémentaire pour les tableaux ont un effet négatif sur la course le temps de fusion de tri. Merge sort favorise également la liste liée car les données sont accessibles de façon séquentielle, sans beaucoup d'accès de mémoire aléatoire.

tri Rapide d'autre part nécessite beaucoup de mémoire vive accès et avec un tableau, nous pouvons accéder directement à la mémoire, sans traversant tel que requis par les listes chaînées. Aussi le tri rapide lorsqu'il est utilisé pour les tableaux ont une bonne localité de référence que les tableaux sont stockés contiguement dans la mémoire.

même si les deux tri la complexité moyenne des algorithmes est O (NlogN), généralement les gens pour les tâches ordinaires utilise un tableau pour le stockage, et pour cette raison le tri rapide devrait être l'algorithme de choix.

EDIT: je viens de découvrir que le sort de fusion worst/best/avg case est toujours nlogn, mais le sort rapide peut varier de n2(le pire cas quand les éléments sont déjà triés) à nlogn(avg/best case quand le pivot divise toujours le tableau en deux moitiés).

c'est une question assez ancienne, mais puisque j'ai traité les deux récemment voici mon 2c:

Merge sort a besoin en moyenne ~ n log n comparaisons. Pour les tableaux déjà (presque) triés cela se réduit à 1/2 N log N, puisque pendant la Fusion nous (presque) toujours sélectionner la partie "gauche" 1/2 N de fois et puis juste copier la droite 1/2 N éléments. En outre, je peux spéculer que l'entrée déjà triée fait briller le prédicteur de branche du processeur mais deviner presque toutes les branches correctement, empêchant ainsi les décrochages de pipeline.

tri rapide en moyenne nécessite ~ 1.38 n Log n comparaisons. Il ne bénéficie pas beaucoup du tableau déjà trié en termes de comparaisons (cependant il le fait en termes de swaps et probablement en termes de prédictions de branche à L'intérieur de CPU).

mes points de repère sur le processeur assez moderne montre ce qui suit:

quand la fonction de comparaison est une fonction de rappel (comme dans qsort () libc implémentation) quicksort est plus lent que mergesort de 15% sur les entrées aléatoires et de 30% pour les tableaux déjà triés pour les entiers 64 bits.

d'autre part, si comparaison n'est pas un rappel, mon expérience est que quicksort surpasse mergesort jusqu'à 25%.

cependant si votre tableau (Grand) a très peu de valeurs uniques, le tri de fusion commence à gagner sur quicksort dans tous les cas.

Alors peut-être la ligne de fond est: si la comparaison est cher (par exemple, fonction de rappel, comparaison des chaînes, comparaison de nombreuses parties d'une structure obtenant le plus souvent un deuxième-troisième-quatrième "si" pour faire la différence) - les chances sont que vous serez mieux avec la fusion de sorte. Pour des tâches plus simples quicksort sera plus rapide.

Qui dit tout dit précédemment est vrai: - Quicksort peut être n ^ 2, mais Sedgewick affirme qu'une bonne mise en Œuvre aléatoire a plus de chances d'un ordinateur exécutant une sorte d'être frappé par la foudre que d'aller n^2 - Mergesort nécessite un espace supplémentaire

En c/c++ terre, lorsque vous n'utilisez pas des conteneurs stl, j'ai tendance à utiliser quicksort, car il est construit dans le temps d'exécution, tandis que mergesort ne l'est pas.

donc je crois que dans de nombreux cas, c'est simplement la voie de la moindre résistance.

en outre, les performances peuvent être beaucoup plus élevées avec le tri rapide, pour les cas où l'ensemble des données ne rentre pas dans l'ensemble de travail.

L'une des raisons est plus philosophique. Quicksort est une philosophie Top - >Down. Avec n éléments à trier, il y a n! possibilité. Avec 2 partitions de m & n-m qui s'excluent mutuellement, le nombre de possibilités diminue de plusieurs ordres de grandeur. m! * (n-m)! est plus petit de plusieurs ordres que n! seul. imaginez 5! vs 3! *2!. 5! a 10 fois plus de possibilités que 2 partitions 2 & 3 chaque . et extrapolez à 1 million factoriel vs 900K!*100K! vs Donc, au lieu de s'inquiéter sur l'établissement de n'importe quel ordre dans une gamme ou une partition,il suffit d'établir l'ordre à un niveau plus large dans les partitions et de réduire les possibilités dans une partition. Tout ordre établi plus tôt dans une gamme sera perturbé plus tard si les cloisons elles-mêmes ne sont pas mutuellement exclusives.

toute approche ascendante telle que le tri par fusion ou le tri par tas est comme l'approche d'un travailleur ou d'un employé où l'on commence à comparer à un niveau microscopique tôt. Mais cet ordre est lié à être perdu dès qu'un élément entre eux est trouvé plus tard. Ces approches sont très stables et extrêmement prévisibles, mais font un certain travail supplémentaire.

Quick Sort est comme L'approche de gestion où l'on n'est pas d'abord préoccupé par n'importe quel ordre , seulement de répondre à un critère large sans égard pour l'ordre. Puis les partitions sont rétrécies jusqu'à ce que vous obtenez un ensemble trié. Le vrai défi à Quicksort est de trouver une partition ou un critère dans l'obscurité quand vous ne savez rien des éléments à trier. C'est la raison pour laquelle nous devons soit nous efforcer de trouver une valeur médiane, soit choisir 1 au hasard ou une méthode de "gestion" arbitraire . Pour trouver une médiane parfaite peut prendre beaucoup d'effort et conduit à une approche stupide bottom up à nouveau. Donc Quicksort dit juste un choix un pivot aléatoire et espérer qu'il sera quelque part dans le milieu ou faire un peu de travail pour trouver la médiane de 3, 5 ou quelque chose de plus pour trouver une meilleure médiane, mais ne prévoyez pas d'être parfait & ne perdez pas de temps dans la commande initiale. Cela semble faire bien si vous êtes chanceux ou se dégrade parfois à n^2 quand vous ne recevez pas une médiane mais juste prendre une chance. De toute façon les données sont aléatoires. droit. Je suis donc plus d'accord avec l'approche logique descendante de quicksort & il s'avère que la chance qu'il prend sur la sélection de pivot et des comparaisons qu'il sauve plus tôt semble fonctionner mieux plus de fois que n'importe quelle méticuleuse et approfondie stable bas ->vers le haut comme le tri de fusion. Mais