Pourquoi QuickSort est-il meilleur que Mergesort?

On m'a posé cette question lors d'une interview. Ils sont tous les deux O (nlogn) et pourtant la plupart des gens utilisent Quicksort au lieu de Mergesort. Pourquoi donc?

Quicksort a O ( n ² ) le pire cas d'exécution et O ( n log n ) le temps d'exécution moyen du cas. Cependant, il est préférable de fusionner le tri dans de nombreux scénarios, car de nombreux facteurs influencent l'exécution d'un algorithme et, en les rassemblant tous, le tri rapide l'emporte.

En particulier, le temps d'exécution souvent cité des algorithmes de tri fait référence au nombre de comparaisons ou au nombre de swaps nécessaires pour effectuer le tri des données. Il s'agit en effet d'une bonne mesure des performances, d'autant plus qu'elle est indépendante de la conception matérielle sous-jacente. Cependant, d'autres choses - comme la localité de référence (c'est-à-dire lisons-nous beaucoup d'éléments qui sont probablement dans le cache?) - jouent également un rôle important sur le matériel actuel. Quicksort en particulier nécessite peu d'espace supplémentaire et présente une bonne localité de cache, ce qui le rend plus rapide que le tri par fusion dans de nombreux cas.

De plus, il est très facile d'éviter presque entièrement le temps d'exécution O ( n ² ) de quicksort en utilisant un choix approprié du pivot - comme le choisir au hasard (c'est une excellente stratégie).

Dans la pratique, de nombreuses implémentations modernes de quicksort (en particulier celles de libstdc ++ std::sort) sont en fait introsort , dont le pire cas théorique est O ( n log n ), identique au tri par fusion. Il y parvient en limitant la profondeur de récursivité et en passant à un algorithme différent ( heapsort ) une fois qu'il dépasse log n .

Comme de nombreuses personnes l'ont noté, les performances moyennes des cas pour quicksort sont plus rapides que pour mergesort. Mais cela n'est vrai que si vous supposez un temps constant pour accéder à n'importe quel morceau de mémoire à la demande.

En 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 mauvais). Cependant, si votre structure de données est suffisamment grande pour vivre sur le disque, le tri rapide est tué par 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 à lire ou à écrire séquentiellement des mégaoctets par seconde de données. C'est exactement ce que fait mergesort.

Par conséquent, si les données doivent être triées sur le disque, vous voulez vraiment, vraiment utiliser une variante du mergesort. (En général, vous triez rapidement les sous-listes, puis commencez à les fusionner au-dessus d'un certain seuil de taille.)

De plus, si vous devez faire quoi que ce soit avec des ensembles de données de cette taille, réfléchissez bien à la façon d'éviter de chercher sur le disque. Par exemple, c'est pourquoi il est conseillé de supprimer les index avant d'effectuer des chargements de données volumineux dans les bases de données, puis de reconstruire l'index ultérieurement. Maintenir l'index pendant le chargement signifie rechercher constamment sur le disque. En revanche, si vous supprimez les index, la base de données peut reconstruire l'index en triant d'abord les informations à traiter (en utilisant un mergesort bien sûr!), Puis en les chargeant dans une infrastructure de données BTREE pour l'index. (Les BTREE sont naturellement conservés dans l'ordre, vous pouvez donc en charger un à partir d'un ensemble de données trié avec peu de recherches sur le disque.)

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

En fait, QuickSort est O (n ² ). Son temps d'exécution moyen de cas 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 le pire des cas, cela empêche simplement un utilisateur malveillant de prendre votre tri longtemps.

QuickSort est plus populaire car il:

1. Est en place (MergeSort nécessite une mémoire supplémentaire linéaire par rapport au nombre d'éléments à trier).
2. A une petite constante cachée.

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

Une raison psychologique qui n'a pas été donnée est simplement que Quicksort est plus habilement nommé. c'est-à-dire un bon marketing.

Oui, Quicksort avec tripartitionnement est probablement l'un des meilleurs algorithmes de tri à usage général, mais il n'est pas possible de surmonter le fait que le tri "Rapide" semble beaucoup plus puissant que le tri "Fusionner".

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

Ce qui rend Quicksort meilleur en moyenne, c'est que la boucle interne implique de comparer plusieurs valeurs avec une seule, tandis que sur les deux autres, les deux termes sont différents pour chaque comparaison. En d'autres termes, Quicksort effectue deux fois moins de lectures que les deux autres algorithmes. Sur les processeurs modernes, les performances sont largement dominées par les temps d'accès, donc à la fin Quicksort finit par être un excellent premier choix.

Je voudrais ajouter que sur les trois algoritmes mentionnés jusqu'ici (mergesort, quicksort et heap sort), seul mergesort est stable. Autrement dit, l'ordre ne change pas pour les valeurs qui ont la même clé. Dans certains cas, cela est souhaitable.

Mais, à vrai dire, dans des situations pratiques, la plupart des gens n'ont besoin que de bonnes performances moyennes et le tri rapide est ... rapide =)

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

À partir de l'entrée Wikipedia sur Quicksort :

Quicksort est également en concurrence avec mergesort, un autre algorithme de tri récursif, mais avec l'avantage du temps d'exécution le plus défavorable Θ (nlogn). Mergesort est un type stable, contrairement au quicksort et au heapsort, et peut être facilement adapté pour fonctionner sur des listes liées et de très grandes listes stockées sur des supports à accès lent tels que le stockage sur disque ou le stockage en réseau. Bien que le tri rapide puisse être écrit pour fonctionner sur des listes chaînées, il souffrira souvent de mauvais choix de pivot sans accès aléatoire. Le principal inconvénient de mergesort est que, lorsqu'il fonctionne sur des baies, il nécessite dans le meilleur des cas un espace auxiliaire Θ (n), tandis que la variante de tri rapide avec partitionnement sur place et récursivité de queue utilise uniquement l'espace Θ (logn). (Notez que lorsque vous travaillez sur des listes liées, mergesort ne nécessite qu'une petite quantité constante de stockage auxiliaire.)

Mu! Quicksort n'est pas mieux, il est bien adapté à un autre type d'application que le mergesort.

Mergesort vaut la peine d'être considéré si la vitesse est essentielle, de mauvaises performances dans le pire des cas ne peuvent pas être tolérées et un espace supplémentaire est disponible. 1

Vous avez déclaré qu'ils «Ils sont tous les deux O (nlogn) […]». C'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 mise en œuvre facile d'accès séquentiel que vous pouvez utiliser lors du tri lors de l'utilisation de langages de programmation avec le paradigme impératif.

1 Sedgewick, algorithmes

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

Heapsort est garanti pour fonctionner en O (n * ln (n)) et ne nécessite qu'un stockage supplémentaire limité. Mais il existe de nombreuses citations de tests dans le monde réel qui montrent que le heapsort est beaucoup plus lent que le quicksort en moyenne.

L'explication de Wikipédia est:

En règle générale, quicksort est beaucoup plus rapide en pratique que les autres algorithmes Θ (nlogn), car sa boucle interne peut être efficacement mise en œuvre 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 un temps quadratique .

Tri rapide

Tri par fusion

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

Je voudrais ajouter aux excellentes réponses existantes quelques calculs sur la façon dont QuickSort fonctionne en s'écartant du meilleur cas et sur la probabilité, ce qui, j'espère, aidera les gens à comprendre un peu mieux pourquoi le cas O (n ^ 2) n'est pas réel dans les implémentations plus sophistiquées de QuickSort.

En dehors des problèmes d'accès aléatoire, deux facteurs principaux peuvent affecter les performances de QuickSort et ils sont tous deux liés à la façon dont le pivot se compare aux données en cours de tri.

1) Un petit nombre de clés dans les données. Un jeu de données de la même valeur sera trié en n ^ 2 fois sur un QuickSort vanilla à 2 partitions car toutes les valeurs, à l'exception de l'emplacement du pivot, sont placées d'un côté à chaque fois. Les implémentations modernes résolvent cela par des méthodes telles que l'utilisation d'un tri à 3 partitions. Ces méthodes s'exécutent sur un ensemble de données de même valeur en temps O (n). Ainsi, l'utilisation d'une telle implémentation signifie qu'une entrée avec un petit nombre de clés améliore réellement le temps de performance et n'est plus un problème.

2) Une sélection de pivot extrêmement mauvaise peut entraîner les pires performances. Dans un cas idéal, le pivot sera toujours tel que 50% les données sont plus petites et 50% les données sont plus grandes, de sorte que l'entrée sera divisée en deux à chaque itération. Cela nous donne n comparaisons et échange les temps log-2 (n) récursions pour le temps O (n * logn).

Dans quelle mesure la sélection de pivot non idéale affecte-t-elle le temps d'exécution?

Prenons un cas où le pivot est choisi de manière cohérente de telle 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 journal est passée à 1 / 0,75 ou 1,33. La relation dans les performances 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 de pivot prend donc 2,4 fois plus de temps que l'idéal.

À quelle vitesse cela empire-t-il?

Pas très vite jusqu'à ce que le choix du pivot soit (systématiquement) très mauvais:

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

Lorsque nous approchons de 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 pivot du 1er élément) ou un tableau trié inversement (pour le pivot du dernier élément) produiront de manière fiable un temps d'exécution O (n ^ 2) dans le pire des cas. En outre, les implémentations avec une sélection de pivot prévisible peuvent être soumises à une attaque DoS par des données conçues pour produire l'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 pire des cas est raisonnablement possible mais O (n ^ 2) n'est pas catastrophique car n est suffisamment petit pour que n ^ 2 soit également petit.
• Grand ensemble de données. Le pire des cas est possible en théorie mais pas en pratique.

Quelle est la probabilité de voir de terribles performances?

Les chances sont extrêmement faibles . Considérons une sorte de 5000 valeurs:

Notre implémentation hypothétique choisira un pivot en utilisant une médiane de 3 index choisis au hasard. Nous considérerons les pivots dans la plage de 25% à 75% comme étant «bons» et les pivots dans la plage de 0% à 25% ou 75% à 100% comme «mauvais». Si vous regardez la distribution de probabilité en utilisant la médiane de 3 indices aléatoires, chaque récursivité a 11/16 de chances de se retrouver avec un bon pivot. Faisons 2 hypothèses conservatrices (et fausses) pour simplifier les calculs:

1. Les bons pivots sont toujours exactement à une répartition de 25% / 75% et fonctionnent à 2,4 * cas idéal. Nous n'obtenons jamais une répartition idéale ou une répartition meilleure que 25/75.

2. Les mauvais pivots sont toujours le pire des cas et ne contribuent essentiellement à rien à la solution.

Notre implémentation QuickSort s'arrêtera à n = 10 et basculera vers un tri par insertion, nous avons donc besoin de 22 partitions pivotantes à 25% / 75% pour décomposer la valeur de 5 000 entrées jusque-là. (10 * 1.333333 ^ 22> 5000) Ou, nous avons besoin de 4990 pivots dans le pire des cas. Gardez à l'esprit que si nous accumulons 22 bons pivots à tout moment, le tri se terminera, donc le pire des cas ou quoi que ce soit à proximité nécessite une très mauvaise chance. S'il nous a fallu 88 récursions pour atteindre réellement 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. Quelle est la probabilité que nous n'obtenions pas les 22 bons pivots requis après 88 récursions?

Les distributions de probabilités binomiales 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 a environ mille fois plus de chances d'être frappé par la foudre dans la seconde qu'il faut pour cliquer sur [TRIER] que pour voir que le tri de 5 000 éléments s'exécute plus mal de 10 * cas idéal. Cette chance diminue au fur et à mesure que l'ensemble de données augmente. Voici quelques tailles de tableau et leurs chances correspondantes de fonctionner plus longtemps que 10 * idéal:

• Tableau de 640 éléments: 10 ^ -13 (nécessite 15 bons points de pivot sur 60 essais)
• Tableau de 5000 éléments: 10 ^ -18 (nécessite 22 bons pivots sur 88 essais)
• Tableau de 40000 articles: 10 ^ -23 (nécessite 29 bons pivots sur 116)

N'oubliez pas que c'est avec 2 hypothèses conservatrices qui sont pires que la réalité. Les performances réelles sont donc encore meilleures, et le solde de la probabilité restante est plus proche que l'idéal.

Enfin, comme d'autres l'ont mentionné, même ces cas absurdement improbables peuvent être éliminés en passant à un tri par tas si la pile de récursivité va trop loin. Ainsi, le TLDR est que, pour de bonnes implémentations de QuickSort, le pire des cas n'existe pas vraiment car il a été conçu et l'exécution se termine en temps O (n * logn).

Pourquoi Quicksort est bon?

• QuickSort prend N ^ 2 dans le pire des cas et NlogN dans le cas moyen. 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 prise par tri par fusion.
• Si l'ensemble de données est volumineux et qu'il existe des éléments identiques, la complexité de Quicksort diminue en utilisant une partition à 3 voies. Plus le nombre d'articles identiques est meilleur, plus le tri est important. Si tous les éléments sont identiques, il trie en temps linéaire. [Il s'agit de 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é en sortie, vous utiliserez Mergesort. La stabilité est requise dans de nombreuses applications pratiques.
• La mémoire est bon marché de nos jours. Donc, 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.

Remarque: En java, la fonction Arrays.sort () utilise Quicksort pour les types de données primitifs et Mergesort pour les types de données d'objets. Étant donné que les objets consomment une surcharge de mémoire, l'ajout d'une petite surcharge pour Mergesort peut ne pas poser de problème pour les performances.

Référence : Regardez les vidéos QuickSort de la semaine 3, Princeton Algorithms Course at Coursera

Quicksort n'est PAS meilleur que mergesort. Avec O (n ^ 2) (le pire des cas qui arrive rarement), le tri rapide est potentiellement beaucoup plus lent que l'O (nlogn) du type de fusion. Quicksort a moins de frais généraux, donc avec de petits ordinateurs n et lents, c'est mieux. Mais les ordinateurs sont si rapides aujourd'hui que le surcoût supplémentaire d'un mergesort est négligeable, et le risque d'un tri rapide très lent l'emporte largement sur les frais généraux insignifiants d'un mergesort dans la plupart des cas.

De plus, un mergesort laisse les éléments avec des clés identiques dans leur ordre d'origine, un attribut utile.

La réponse inclinerait légèrement vers le tri rapide par rapport aux modifications apportées avec DualPivotQuickSort pour les valeurs primitives. Il est utilisé dans JAVA 7 pour trier dans java.util.Arrays

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'implémentation JAVA7 ici - http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/7-b147/java/util/Arrays.java

Autres lectures impressionnantes sur DualPivotQuickSort - http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628

En tri par fusion, l'algorithme général est:

1. Trier le sous-tableau de gauche
2. Trier le bon sous-tableau
3. Fusionner les 2 sous-tableaux triés

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

Un niveau en dessous, chaque itération de l'étape 3 implique de traiter N / 2 éléments, mais vous devez répéter ce processus deux fois. Vous avez donc toujours affaire à 2 * N / 2 == éléments N.

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

Considérez plutôt l'algorithme de tri rapide:

1. Choisissez un point de pivot
2. Placez le point de pivot au bon endroit dans le tableau, avec tous les petits éléments à gauche et les plus gros éléments à droite
3. Trier le sous-tableau de gauche
4. Trier le sous-tableau de droite

Au niveau supérieur, vous avez affaire à un tableau de taille N. Vous choisissez ensuite un point de pivot, le placez à sa position correcte, puis vous pouvez l'ignorer complètement pour le reste de l'algorithme.

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

Un niveau en dessous, vous avez affaire à 4 sous-tableaux de 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 le tri par fusion, vous avez toujours affaire à une fusion à N éléments, à chaque niveau de la pile récursive. Cependant, avec le tri rapide, le nombre d'éléments que vous traitez diminue à mesure que vous descendez la pile. Par exemple, si vous regardez la profondeur à mi-chemin à travers la pile récursive, le nombre d'éléments que vous traitez est N - 2 ^ ((logN) / 2)) == N - sqrt (N).

Avertissement: lors du tri par fusion, comme vous divisez le tableau en 2 morceaux exactement égaux à chaque fois, la profondeur récursive est exactement logN. Lors du tri rapide, car il est peu probable que votre point de pivot se trouve exactement au milieu du tableau, la profondeur de votre pile récursive peut être légèrement supérieure à 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.

Contrairement au tri par fusion, le tri rapide n'utilise pas d'espace auxiliaire. Alors que Merge Sort utilise un espace auxiliaire O (n). Mais Merge Sort a la pire complexité temporelle de O (nlogn) tandis que la pire complexité de Quick Sort est O (n ^ 2), ce qui se produit lorsque le tableau est déjà trié.

Quicksort a une meilleure complexité moyenne des cas, mais dans certaines applications, ce n'est pas le bon 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 la pire complexité temporelle de o (n ^ 2).

La complexité moyenne des cas et la pire des cas de Mergesort sont les mêmes et ne souffrent donc pas du même problème. Cette propriété de fusion-tri en fait é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 le font fonctionner beaucoup, beaucoup plus lentement.

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

C'est difficile à dire.Le pire de MergeSort est n (log2n) -n + 1, ce qui est précis si n est égal à 2 ^ k (je l'ai déjà prouvé) .Et pour tout n, il se situe entre (n lg n - n + 1) et (n lg n + n + O (lg n)). Mais pour quickSort, son meilleur est nlog2n (également n est égal à 2 ^ k). Si vous divisez Mergesort par quickSort, il est égal à un lorsque n est infini. c'est comme si le pire des cas de MergeSort était meilleur que le meilleur des cas de QuickSort, pourquoi utilisons-nous Quicksort? Mais rappelez-vous, MergeSort n'est pas en place, il nécessite 2 n d'espace de mémoire. ne pas inclure dans l'analyse de l'algorithme.En un mot, MergeSort est vraiment plus rapide que quicksort dans theroy, mais en réalité, vous devez prendre en compte l'espace mémoire, le coût de la copie du tableau, la fusion est plus lente que le tri rapide. expérience où j'ai reçu 1000000 chiffres en java par classe aléatoire,et il a fallu 2610 ms par mergesort, 1370 ms par quicksort.

Le tri rapide est le pire des cas O (n ^ 2), cependant, le cas moyen effectue systématiquement un tri par fusion. Chaque algorithme est O (nlogn), mais vous devez vous rappeler que lorsque nous parlons de Big O, nous laissons de côté les facteurs de complexité inférieurs. Le tri rapide présente des améliorations significatives par rapport au tri par fusion lorsqu'il s'agit de facteurs constants.

Le tri par fusion nécessite également de la mémoire O (2n), tandis qu'un tri rapide peut être effectué sur place (nécessitant uniquement O (n)). C'est une autre raison pour laquelle le tri rapide est généralement préféré au tri par fusion.

Informaitons 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 du groupe, le tri rapide s'exécutera en O (n ^ 2). La probabilité de choisir l'élément qui se trouve dans le plus grand ou le plus petit 25% de la liste est de 0,5. Cela donne à l'algorithme 0,5 chance d'être un bon pivot. Si nous utilisons 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 de pivot. Pour les collections de grande taille, la probabilité de toujours choisir un mauvais pivot est de 0,5 * n. Sur la base de cette probabilité, le tri rapide est efficace pour le cas moyen (et typique).

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

Fusionner les besoins de tri en moyenne ~ N log N comparaisons. Pour les tableaux triés déjà (presque) triés, cela revient à 1/2 N log N, car lors de la fusion, nous sélectionnons (presque) toujours la partie "gauche" 1/2 N de fois, puis copions juste 1/2 N éléments à droite. De plus, je peux supposer qu'une entrée déjà triée fait briller le prédicteur de branche du processeur, mais devine presque toutes les branches correctement, empêchant ainsi les blocages de pipeline.

Le tri rapide nécessite en moyenne ~ 1,38 N log N comparaisons. Il ne bénéficie pas grandement d'un tableau déjà trié en termes de comparaisons (mais il le fait en termes de swaps et probablement en termes de prédictions de branche à l'intérieur du CPU).

Mes repères sur un processeur assez moderne montrent ce qui suit:

Lorsque la fonction de comparaison est une fonction de rappel (comme dans l'implémentation libs de qsort ()), la tri rapide est plus lente que la fusion par 15% sur une entrée aléatoire et 30% pour un tableau déjà trié pour des entiers 64 bits.

D'un autre côté, si la comparaison n'est pas un rappel, mon expérience est que le tri rapide surpasse le tri par fusion jusqu'à 25%.

Cependant, si votre (grand) tableau a très peu de valeurs uniques, le tri par fusion commence à gagner le tri rapide dans tous les cas.

Donc, peut-être que le résultat est le suivant: si la comparaison est coûteuse (par exemple, fonction de rappel, comparaison de chaînes, comparaison de nombreuses parties d'une structure atteignant principalement un deuxième-troisième "si" pour faire la différence) - les chances sont que vous serez meilleur avec tri par fusion. Pour des tâches plus simples, le tri rapide sera plus rapide.

Cela dit, tout ce qui a été dit précédemment est vrai: - Quicksort peut être N ^ 2, mais Sedgewick prétend qu'une bonne mise en œuvre aléatoire a plus de chances qu'un ordinateur effectuant un tri soit frappé par un éclair que d'aller N ^ 2 - Mergesort nécessite un espace supplémentaire

Lorsque j'ai expérimenté les deux algorithmes de tri, en comptant le nombre d'appels récursifs, quicksort a systématiquement 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 cas de base récursif plus rapidement que mergesort.

Il s'agit d'une question courante posée dans les entretiens: malgré de meilleures performances dans le pire des cas du tri par fusion, le tri rapide est considéré comme meilleur que le tri par fusion, en particulier pour une entrée importante. Il y a certaines raisons pour lesquelles le tri rapide est meilleur:

1- Espace auxiliaire: le tri rapide est un algorithme de tri sur place. Le tri sur place signifie qu'aucun espace de stockage supplémentaire n'est nécessaire pour effectuer le tri. Le tri par fusion nécessite en revanche un tableau temporaire pour fusionner les tableaux triés et il n'est donc pas en place.

2- Pire cas: le pire des cas de tri rapide O(n^2)peut être évité en utilisant un tri rapide aléatoire. Il peut être facilement évité avec une forte probabilité en choisissant le bon pivot. L'obtention d'un comportement de cas moyen en choisissant l'élément pivot droit permet d'improviser les performances et de devenir aussi efficace que le tri par fusion.

3- Localité de référence: Quicksort en particulier présente une bonne localité de cache, ce qui le rend plus rapide que le tri par fusion dans de nombreux cas comme dans un environnement de mémoire virtuelle.

4- Récursivité de la queue: QuickSort est récursif de la queue tandis que le tri par fusion ne l'est pas. Une fonction récursive de queue est une fonction où l'appel récursif est la dernière chose exécutée par la fonction. Les fonctions récursives de queue sont considérées comme meilleures que les fonctions non récursives de queue car la récursivité de queue peut être optimisée par le compilateur.

Bien qu'ils soient tous deux dans la même classe de complexité, cela ne signifie pas qu'ils ont tous les deux le même temps d'exécution. Quicksort est généralement plus rapide que mergesort, simplement parce qu'il est plus facile de coder une implémentation serrée et que les opérations qu'il effectue peuvent aller plus vite. C'est parce que ce tri rapide est généralement plus rapide que les gens l'utilisent au lieu du fusionnement.

Toutefois! Personnellement, j'utilise souvent mergesort ou une variante quicksort qui se dégrade en mergesort lorsque quicksort fonctionne mal. Rappelles toi. Quicksort n'est que O (n log n) en moyenne . Le pire des cas est O (n ^ 2)! Mergesort est toujours O (n log n). Dans les cas où les performances ou la réactivité en temps réel sont indispensables et que vos données d'entrée peuvent provenir d'une source malveillante, vous ne devez pas utiliser le tri rapide simple.

Toutes choses étant égales par ailleurs, je m'attendrais à ce que la plupart des gens utilisent ce qui est le plus facilement disponible, et cela a tendance à être qsort (3). À part cela, 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 des radix ou des seaux. Ils sont O (n), au moins sur les listes chaînées et il suffit d'une méthode de conversion de la clé en nombre ordinal. (les cordes et les flotteurs fonctionnent très bien.)

Je pense que la raison est liée à l'enseignement de l'informatique. J'ai même dû démontrer à mon professeur en analyse algorithmique qu'il était en effet possible de trier plus vite que O (n log (n)). (Il avait la preuve que la comparaison ne peut pas être triée plus rapidement que O (n log (n)), ce qui est vrai.)

Dans d'autres nouvelles, les flottants peuvent être triés sous forme d'entiers, mais vous devez inverser les nombres négatifs par la suite.

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

Petits ajouts aux tris rapides et de fusion.

Cela peut également dépendre du type d'éléments de tri. Si l'accès aux éléments, l'échange et les comparaisons ne sont pas des opérations simples, comme la comparaison d'entiers dans la mémoire plane, le tri par fusion peut être un algorithme préférable.

Par exemple, nous trions les éléments à l'aide du protocole réseau sur le serveur distant.

De plus, dans les conteneurs personnalisés comme la "liste chaînée", le tri rapide ne présente aucun avantage.
1. Fusionner le tri sur la liste liée, ne nécessite pas de mémoire supplémentaire. 2. L'accès aux éléments en tri rapide n'est pas séquentiel (en mémoire)

Le tri rapide est un algorithme de tri sur place, il est donc mieux adapté aux tableaux. Le tri par fusion nécessite en revanche un stockage supplémentaire de O (N) et convient mieux aux listes liées.

Contrairement aux tableaux, dans la liste aimée, nous pouvons insérer des éléments au milieu avec un espace O (1) et un temps O (1), par conséquent, l'opération de fusion dans le tri par fusion peut être implémentée sans espace supplémentaire. Cependant, l'allocation et la désallocation d'espace supplémentaire pour les tableaux ont un effet négatif sur le temps d'exécution du tri par fusion. Le tri par fusion favorise également la liste liée car les données sont accessibles séquentiellement, sans beaucoup d'accès aléatoire à la mémoire.

Le tri rapide, d'autre part, nécessite beaucoup d'accès aléatoire à la mémoire et avec un tableau, nous pouvons accéder directement à la mémoire sans aucune traversée comme l'exigent les listes liées. De même, le tri rapide lorsqu'il est utilisé pour les tableaux a une bonne localité de référence car les tableaux sont stockés de manière contiguë en mémoire.

Même si la complexité moyenne des deux algorithmes de tri est O (NlogN), généralement les personnes pour les tâches ordinaires utilisent 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 tri de fusion pire / meilleur / cas moyen est toujours nlogn, mais le tri rapide peut varier de n2 (pire cas lorsque les éléments sont déjà triés) à nlogn (moyen / meilleur cas lorsque pivot divise toujours le tableau en deux moitiés).

Considérez à la fois la complexité du temps et de l'espace. Pour le tri par fusion: Complexité temporelle: O (nlogn), Complexité spatiale: O (nlogn)

Pour Tri rapide: Complexité temporelle: O (n ^ 2), Complexité spatiale: O (n)

Maintenant, ils gagnent tous les deux dans un seul scénario. Mais, en utilisant un pivot aléatoire, vous pouvez presque toujours réduire la complexité temporelle du tri rapide à O (nlogn).

Ainsi, le tri rapide est préféré dans de nombreuses applications au lieu du tri par fusion.

En terre c / c ++, lorsque je n'utilise pas de conteneurs stl, j'ai tendance à utiliser quicksort, car il est intégré à l'exécution, tandis que mergesort ne l'est pas.

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

De plus, les performances peuvent être beaucoup plus élevées avec un tri rapide, dans les cas où l'ensemble de données entier ne rentre pas dans le jeu de travail.

L'une des raisons est plus philosophique. Quicksort est la philosophie Top-> Down. Avec n éléments à trier, il y en a n! possibilités. Avec 2 partitions de m & nm qui s'excluent mutuellement, le nombre de possibilités diminue de plusieurs ordres de grandeur. m! * (nm)! 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 de 2 et 3 chacune. et extrapoler à 1 million factoriel vs 900K! * 100K! Par conséquent, au lieu de vous soucier d'établir un ordre dans une plage ou une partition, il vous suffit d'établir un ordre à un niveau plus large dans les partitions et de réduire les possibilités au sein d'une partition. Tout ordre établi plus tôt dans une plage sera perturbé plus tard si les partitions elles-mêmes ne s'excluent pas mutuellement.

Toute approche d'ordre ascendant, comme le tri par fusion ou le tri par tas, est comme l'approche des travailleurs ou des employés où l'on commence à comparer au niveau microscopique tôt. Mais cet ordre est voué à être perdu dès qu'un élément intermédiaire se trouvera plus tard. Ces approches sont très stables et extrêmement prévisibles mais font un certain travail supplémentaire.

Le tri rapide est comme une approche managériale où l'on ne se préoccupe initialement d'aucune commande, mais seulement de répondre à un critère général sans égard à l'ordre. Ensuite, les partitions sont rétrécies jusqu'à ce que vous obteniez un ensemble trié. Le vrai défi dans Quicksort est de trouver une partition ou un critère dans le noir lorsque vous ne savez rien sur les éléments à trier. C'est pourquoi nous devons soit consacrer des efforts à trouver une valeur médiane, soit choisir 1 au hasard ou une approche "managériale" arbitraire. Trouver une médiane parfaite peut demander beaucoup d'efforts et conduit à nouveau à une stupide approche ascendante. Donc Quicksort dit juste de choisir un pivot aléatoire et espérons qu'il sera quelque part au milieu ou fera un travail pour trouver une médiane de 3, 5 ou quelque chose de plus pour trouver une meilleure médiane mais ne prévoit pas d'être parfait et de ne pas le faire ' ne perdez pas de temps lors de la commande initiale. Cela semble bien fonctionner si vous êtes chanceux ou parfois dégrade à n ^ 2 lorsque vous n'obtenez pas de médiane, mais prenez simplement une chance. Dans tous les cas, les données sont aléatoires. droite. Je suis donc plus d'accord avec l'approche logique top -> down de quicksort et il se trouve que la chance qu'il prend sur la sélection des pivots et les comparaisons qu'il enregistre plus tôt semble mieux fonctionner plus de fois que n'importe quel fond stable méticuleux et approfondi -> approche up comme tri par fusion. Mais les comparaisons qu'il enregistre plus tôt semblent mieux fonctionner plus de fois que toute approche ascendante méticuleuse et approfondie, comme le tri par fusion. Mais Les comparaisons qu'il enregistre plus tôt semblent mieux fonctionner plus de fois que toute approche ascendante méticuleuse et approfondie, comme le tri par fusion. Mais