Pourquoi quicksort est-il meilleur que mergesort?

StackOverflow https://stackoverflow.com/questions/70402

Question

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

Était-ce utile?

La solution

Quicksort a O ( n 2 ) dans le pire des scénarios d’exécution et O ( n log n ) moyen cas d'exécution. Toutefois, il est préférable de fusionner le tri dans de nombreux scénarios, car de nombreux facteurs influencent le temps d’exécution d’un algorithme et, en les prenant tous ensemble, 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. C’est effectivement une bonne mesure de performance, d’autant plus qu’elle est indépendante de la conception matérielle sous-jacente. Cependant, d’autres éléments - tels que la localité de référence (lisons-nous beaucoup d’éléments qui sont probablement en 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 localisation en 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 le temps d’exécution de O ( n 2 dans le pire des cas de quicksort) en utilisant un choix approprié du pivot - tel que comme le choisir au hasard (c'est une excellente stratégie).

En pratique, de nombreuses implémentations modernes de quicksort (en particulier le std :: sort de libstdc ++ sont en réalité introsort , dont le pire cas théorique est O ( n journal n ), identique au tri par fusion. Pour ce faire, il limite la profondeur de récursivité et passe à un algorithme différent ( heapsort ) une fois dépassé. connectez-vous n .

Autres conseils

Comme beaucoup de personnes l’ont noté, les performances moyennes des cas de quicksort sont plus rapides que de mergesort. Mais , cela n’est vrai que si vous prenez le temps nécessaire pour accéder à n’importe quelle pièce 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 c’est pas trop mal). Toutefois, si votre structure de données est suffisamment volumineuse pour vivre sur un disque, le tri rapide est tué par le fait que votre disque moyen effectue environ 200 recherches aléatoires par seconde. Mais ce même disque n'a aucun problème à lire ou à écrire séquentiellement des mégaoctets de données par seconde. Ce qui est exactement ce que mergesort fait.

Par conséquent, si les données doivent être triées sur le disque, vous souhaitez vraiment, vraiment, utiliser certaines variantes de mergesort. (Généralement, vous triez rapidement les sous-listes, puis commencez à les fusionner au-dessus d’un 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 manière d'éviter les recherches sur le disque. C'est pourquoi, par exemple, il est conseillé de supprimer les index avant d'effectuer des chargements de données volumineux dans des bases de données, puis de reconstruire l'index ultérieurement. Maintenir l'index pendant le chargement signifie chercher 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 (à l'aide d'un mergesort bien sûr!), Puis en les chargeant dans une structure 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 jeu de données trié avec peu de recherches sur le disque.)

À plusieurs reprises, comprendre comment éviter les recherches sur disque m'a permis de faire des tâches de traitement de données prendre des heures plutôt que des jours ou des semaines.

En fait, QuickSort est O (n 2 ). Son temps d'exécution moyen est O (nlog (n)), mais son pire cas est O (n 2 ), ce qui se produit lorsque vous l'exécutez sur une liste qui contient quelques é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 faire votre tri prendre 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 est-ce? "

Une des raisons psychologiques qui n’a pas été donnée est simplement que Quicksort porte un nom plus astucieux. c'est-à-dire un bon marketing.

Oui, Quicksort avec triple partitionnement est probablement l’un des meilleurs algorithmes de tri à usage général, mais il n’ya pas de doute que "Quick" trier semble beaucoup plus puissant que "Fusionner" trier.

Comme d’autres l’ont déjà noté, le pire cas de Quicksort est O (n ^ 2), tandis que mergesort et heapsort restent en O (nlogn). En moyenne, cependant, tous les trois sont O (nlogn); ils sont donc comparables dans la grande majorité des cas.

Ce qui rend Quicksort meilleur en moyenne, c’est que la boucle interne implique de comparer plusieurs valeurs avec une seule, alors que les deux autres termes sont différents pour chaque comparaison. En d'autres termes, Quicksort effectue la moitié moins de lectures que les deux autres algorithmes. Sur les processeurs modernes, les temps d’accès pèsent lourdement sur les performances, ce qui fait de Quicksort un excellent premier choix.

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

Mais, à vrai dire, dans la pratique, 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 article de Wikipedia sur le tri des algorithmes pour un bon aperçu.

De l'entrée 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, le temps d'exécution running (nlogn).   Mergesort est un type stable, contrairement à   quicksort et heapsort, et peut être   facilement adapté pour fonctionner sur lié   listes et très grandes listes stockées sur   média d'accès lent tel que le disque   stockage ou stockage connecté au réseau.   Bien que quicksort puisse être écrit pour   fonctionner sur des listes chaînées, il sera souvent   souffrir de mauvais choix de pivot sans   accès aléatoire. Le principal inconvénient   de mergesort est que, lors de l'exploitation   sur les tableaux, il faut T (n) auxiliaire   dans le meilleur des cas, alors que le   variante de tri rapide avec en place   utilisations de partitionnement et de récursion de queue   seulement space (logn) space. (Notez que lorsque   opérant sur des listes chaînées, mergesort   nécessite seulement une petite quantité constante   de stockage auxiliaire.)

Mu! Quicksort n’est pas meilleur, il est bien adapté à un type d’application différent de celui de mergesort.

  

Mergesort vaut la peine d’être envisagé si la rapidité est essentielle, si les performances dans le pire des cas ne sont pas médiocres, et si de l’espace supplémentaire est disponible. 1

Vous avez déclaré qu'ils «ils sont tous deux O (nlogn) […]». C'est faux. «Dans le pire des cas, Quicksort utilise environ n ^ 2/2 comparaisons.» 1 .

Toutefois, selon mon expérience, la propriété la plus importante est la mise en œuvre facile d’un accès séquentiel que vous pouvez utiliser lors du tri lorsque vous utilisez 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 présente un certain nombre de cas pathologiques qui peuvent le rendre aussi performant que O (n2).

Heapsort est garanti pour s'exécuter 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 la pile de tractions est beaucoup plus lente que la tri rapide en moyenne.

L’explication de Wikipedia est la suivante:

  

En règle générale, le tri rapide est beaucoup plus rapide dans la pratique que les autres algorithmes T (nlogn), car sa boucle interne peut être efficacement mise en œuvre sur la plupart des architectures et, dans la plupart des données réelles, il est possible de faire des choix de conception minimisant la probabilité de nécessitant un temps quadratique.

Quicksort

Mergesort

Je pense que la quantité de mémoire nécessaire pour Mergesort (qui est O (n)) pose également problème, contrairement aux implémentations de tri rapide. Dans le pire des cas, ils ont la même durée de temps algorithmique, mais mergesort nécessite plus de stockage.

Quicksort n'est PAS meilleur que mergesort. Avec O (n ^ 2) (dans le pire des cas, cela arrive rarement), le tri rapide 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 ordinateurs n et les ordinateurs lents, il est préférable. Mais les ordinateurs sont si rapides aujourd'hui que les frais généraux supplémentaires d'un fusionnement sont négligeables, et le risque d'un tri rapide très lent l'emporte largement sur les frais généraux insignifiants d'un test de fusion dans la plupart des cas.

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

Je voudrais ajouter aux bonnes réponses existantes quelques calculs sur le comportement de QuickSort par rapport au meilleur des cas et sur sa probabilité, ce qui, j'espère, aidera les gens à comprendre un peu mieux pourquoi le cas O (n ^ 2) est pas vraiment préoccupant dans les implémentations plus sophistiquées de QuickSort.

En dehors des problèmes d’accès aléatoire, deux facteurs principaux peuvent influer sur les performances de QuickSort. 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 ensemble de données de la même valeur sera trié en n ^ 2 fois sur un QuickSort à deux partitions vanilla car toutes les valeurs, à l'exception de l'emplacement du pivot, sont placées d'un côté à chaque fois. Les implémentations modernes traitent 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 la même valeur en O (n) time. L'utilisation d'une telle implémentation signifie donc qu'une entrée avec un petit nombre de clés améliore réellement les performances et ne pose plus de problème.

2) Une sélection de pivot extrêmement mauvaise peut entraîner des performances optimales. 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 divisée en deux à chaque itération. Cela nous donne n comparaisons et swaps fois les récurrences log-2 (n) pour O (n * logn).

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

Prenons le cas où le pivot est choisi de manière cohérente, de sorte que 75% des données se trouvent sur un côté du pivot. C'est toujours O (n * logn) mais maintenant la base du journal a été changée en 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 2.4. Donc, cette qualité de choix de pivot prend 2,4 fois plus longtemps que l’idéal.

À quelle vitesse cela empire-t-il?

Pas très vite jusqu'à ce que le choix du pivot devienne (toujours) 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 long
  • 95% d'un côté: 13,5 fois plus longtemps
  • 99% d'un côté: 69 fois plus longtemps

Alors que nous nous approchons de 100% d’un côté, la partie journal de l’exécution s’approche de n et l’ensemble de l’exécution approche de façon asymptotique O (n ^ 2).

Dans une implémentation naïve de QuickSort, des cas tels qu'un tableau trié (pour le pivot du premier élément) ou trié inversé (pour le pivot du dernier élément) génèrent de manière fiable un temps d'exécution O (n ^ 2) dans le pire des cas. De plus, 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 une exécution dans le pire des cas. Les implémentations modernes évitent cela par diverses méthodes, telles que la randomisation des données avant tri, le choix de la médiane de 3 index choisis aléatoirement, etc. Cette randomisation faisant partie du mixage, 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 le soit également.
  • Grand ensemble de données. Le pire des cas est possible en théorie mais pas en pratique.

Quelle est notre probabilité de voir des performances terribles?

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

Notre implémentation hypothétique choisira un pivot utilisant une médiane de 3 index choisis au hasard. Nous considérerons que les pivots compris entre 25% et 75% sont "bons". et des pivots qui sont dans la plage de 0% à 25% ou de 75% à 100% pour être "mauvais". Si vous regardez la distribution de probabilité en utilisant la médiane de 3 index aléatoires, chaque récurrence a 11 chances sur 16 de se retrouver avec un bon pivot. Faisons deux hypothèses conservatrices (et fausses) pour simplifier les calculs:

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

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

Notre implémentation QuickSort s'arrêtera à n = 10 et passera à un tri par insertion. Nous avons donc besoin de 22 partitions pivot 25% / 75% pour décomposer la valeur de 5 000 entrées jusqu'à présent. (10 * 1.333333 ^ 22 > 5000) Nous avons également besoin de 4990 pivots dans le cas le plus défavorable. Gardez à l'esprit que si nous accumulons 22 bons pivots à n'importe quel point , le tri s'achèvera. Le pire des cas, ou un résultat proche, nécessite donc extremement un manque de chance. Si nous avions besoin de 88 récursions pour atteindre les 22 pivots nécessaires pour trier n = 10, nous aurions alors 4 * 2.4 * cas idéal, soit environ 10 fois le temps d’exécution du cas idéal. Quelle est la probabilité que nous n'atteignions pas les 22 bons pivots nécessaires après 88 récursions?

Les

distributions de probabilité binomiales peuvent répondre à cette question. 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 au cours de la seconde qu'il faut pour cliquer sur [TRIER] qu'il ne le faut pour voir que le tri de 5 000 éléments est exécuté pire que 10 * cas idéal. Cette chance diminue à mesure que le jeu de données s'agrandit. Voici quelques tailles de tableaux et leurs chances correspondantes de fonctionner plus de 10 * idéal:

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

N'oubliez pas qu'il s'agit de 2 hypothèses conservatrices pires que la réalité. La performance réelle est donc encore meilleure et le solde de la probabilité restante est plus proche de l’idéal que possible.

Enfin, comme d’autres l'ont déjà mentionné, même ces cas absurdement improbables peuvent être éliminés en passant à un type de segment de mémoire si la pile de récursivité est trop profonde. Le TLDR indique donc que, pour de bonnes implémentations de QuickSort, le pire des cas n'existe pas vraiment car il a été conçu et son exécution terminée en temps O (n * logn).

La réponse inclinerait légèrement vers le tri rapide par rapport aux changements apportés avec DualPivotQuickSort pour les valeurs primitives. Il est utilisé dans JAVA 7 pour trier 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

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

Dans Merge-Sort, l'algorithme général est le suivant:

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

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

À un niveau inférieur, chaque itération de l’étape 3 implique de traiter avec N / 2 éléments, mais vous devez répéter ce processus deux fois. Donc, vous avez toujours affaire à 2 * N / 2 == N éléments.

Un niveau en dessous, vous êtes en train de fusionner 4 * N / 4 == N éléments, etc. Chaque profondeur de la pile récursive implique la fusion du même nombre d'éléments, pour tous les appels correspondant à cette profondeur.

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

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

Au niveau supérieur, vous avez affaire à un tableau de taille N. Vous devez ensuite sélectionner un point pivot, le placer à la bonne position et l’ignorer complètement pour le reste de l’algorithme.

À un niveau inférieur à celui-ci, vous avez deux sous-tableaux dont la taille combinée est N-1 (c’est-à-dire, soustrayez le point de pivot précédent). Vous choisissez un point pivot pour chaque sous-tableau, ce qui donne lieu à 2 points pivot supplémentaires.

Un niveau en dessous, vous avez 4 sous-tableaux de taille combinée N-3, pour les mêmes raisons que ci-dessus.

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

La profondeur de votre pile récursive reste approximativement la même (logN). Avec fusion-sort, vous avez toujours affaire à une fusion de N éléments, à chaque niveau de la pile récursive. Avec le tri rapide cependant, le nombre d’éléments que vous traitez diminue au fur et à mesure que vous progressez. Par exemple, si vous examinez la profondeur au milieu de la pile récursive, le nombre d’éléments traités est N - 2 ^ ((logN) / 2)) == N - sqrt (N).

Clause de non-responsabilité: lors de la fusion-triage, comme vous divisez le tableau en 2 fragments identiques à chaque fois, la profondeur récursive est exactement logN. Sur le tri rapide, comme il est improbable que votre point de pivotement se trouve exactement au milieu du tableau, la profondeur de votre pile récursive peut être légèrement supérieure à celle de logN. Je n'ai pas fait le calcul pour voir le rôle important que jouent ce facteur et le facteur décrit ci-dessus dans la complexité de l'algorithme.

Contrairement au tri par fusion, le tri rapide n’utilise pas d’espace auxiliaire. Tandis que le tri par fusion utilise un espace auxiliaire O (n). Mais le tri par fusion a la complexité temporelle dans le pire des cas de O (nlogn) alors que la complexité du tri rapide dans le pire des cas est O (n ^ 2), ce qui se produit lorsque le tableau est déjà trié.

Bien qu'ils appartiennent tous les deux à 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 compacte et que les opérations qu'elle 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 de fusionner.

Cependant! Personnellement, je vais souvent utiliser mergesort ou une variante de quicksort qui se dégrade en mergesort quand quicksort se comporte mal. Rappelles toi. Quicksort est seulement O (n log n) en moyenne . C'est le pire des cas, c'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 plain quicksort.

Quicksort a une complexité de cas moyenne supérieure, 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 prenant la pire complexité temporelle de o (n ^ 2).

La complexité moyenne des dossiers de Mergesort et la complexité des cas les plus défavorables 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 temps réel - précisément parce qu'il n'y a pas de cas pathologique qui le ralentit beaucoup.

Pour ces raisons, je suis un plus grand fan de Mergesort que de Quicksort.

Pourquoi le 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 brassage aléatoire avant le début du tri.
  • QuickSort ne prend pas de mémoire supplémentaire utilisée par le tri par fusion.
  • Si le jeu de données est volumineux et que les éléments sont identiques, la complexité de Quicksort est réduite en utilisant une partition à 3 voies. Plus le nombre d'éléments identiques est meilleur, mieux le tri. Si tous les éléments sont identiques, le tri est linéaire. [Ceci 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é en sortie, vous utiliserez Mergesort. La stabilité est nécessaire dans de nombreuses applications pratiques.
  • La mémoire n'est pas chère de nos jours. Si plus de mémoire utilisée par Mergesort n’est pas critique pour votre application, vous n’aurez 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'objet. Étant donné que les objets consomment de la mémoire, une légère surcharge pour Mergesort ne pose donc aucun problème en termes de performances.

Référence : Regardez les vidéos QuickSort de la semaine 3, à Princeton. Cours d'algorithmes à Coursera

Le tri rapide correspond au cas le plus défavorable O (n ^ 2). Toutefois, le cas moyen moyen effectue systématiquement le tri par fusion. Chaque algorithme est O (nlogn), mais vous devez vous rappeler que lorsque nous parlons de Big O, nous ne tenons pas compte des facteurs de complexité inférieure. 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 (ne nécessitant que O (n)). C'est une autre raison pour laquelle le tri rapide est généralement préféré au tri par fusion.

Infos 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 se fera dans O (n ^ 2). La probabilité de choisir l'élément qui se trouve dans le plus grand ou le plus petit des 25% de la liste est de 0,5. Cela donne à l’algorithme une chance de devenir un 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 pivot médiocre 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 depuis que j'ai traité les deux récemment voici mon 2c:

Le tri par fusion nécessite 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 "à gauche". une partie 1/2 N de fois puis copiez simplement les 1/2 N éléments de droite. De plus, je peux supposer que les entrées déjà triées font briller le prédicteur de branche du processeur, mais en devinant presque toutes les branches correctement, évitant ainsi les blocages de pipeline.

Le tri rapide nécessite en moyenne environ 1,38 N log N comparaisons. Il ne tire pas grand profit des tableaux déjà triés en termes de comparaisons (cependant, il en fait de même pour les échanges et probablement pour les prédictions de branche dans la CPU).

Mes points de repère sur un processeur assez moderne montrent ce qui suit:

Lorsque la fonction de comparaison est une fonction de rappel (comme dans l’implémentation de qsort () libc), quicksort est plus lent que mergesort de 15% pour une entrée aléatoire et de 30% pour un tableau déjà trié pour des entiers 64 bits.

D’autre part, si la comparaison n’est pas un rappel, mon expérience est que le tri rapide produit un rendement supérieur à celui de la fusion par fusion jusqu’à 25%.

Cependant, si votre (grand) tableau a très peu de valeurs uniques, le tri par fusion commence à gagner 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 aboutissant principalement à un deuxième tiers sur "si" pour faire la différence) - il y a de fortes chances que vous serez mieux avec le genre de 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 affirme qu’une bonne mise en œuvre randomisée a plus de chances qu’un ordinateur effectuant ce tri soit frappé par la foudre plutôt que de passer à N ^ 2 - Mergesort nécessite de l'espace supplémentaire

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. Ainsi, quicksort peut atteindre le cas de base récursif plus rapidement que mergesort.

Toutes choses étant égales par ailleurs, je m'attendrais à ce que la plupart des gens utilisent ce qui est le plus commodément disponible, et cela a tendance à être qsort (3). En dehors de cela, quicksort est connu pour être très rapide sur les tableaux, tout comme mergesort est le choix courant pour les listes.

Ce que je me demande, c'est pourquoi il est si rare de voir radical ou un type de seau. Ils sont O (n), au moins sur des listes chaînées et tout ce qu’il faut, c’est une méthode de conversion de la clé en un nombre ordinal. (les chaînes et les flotteurs fonctionnent très bien.)

Je pense que la raison est liée à la manière dont l’informatique est enseignée. J'ai même dû démontrer à mon conférencier en analyse algorithmique qu'il était effectivement possible de trier plus rapidement que O (n log (n)). (Il avait la preuve que vous ne pouvez pas comparer trier 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.

Modifier: En fait, voici un moyen encore plus vicieux de trier les flottants en tant qu'entiers: http: //www.stereopsis. com / radix.html . Notez que cette astuce peut être utilisée 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 est égal à 2 ^ k (je l'ai déjà prouvé). Et pour tout n, il est compris entre (n lg n - n + 1) et (n lg n + n + O (lg n)). Mais pour quickSort, son meilleur est nlog2n (n est également égal à 2 ^ k) .Si vous divisez Mergesort par quickSort, il est égal à un lorsque n est Donc, c'est comme si le pire cas de MergeSort était meilleur que le meilleur cas de QuickSort, pourquoi utilisons-nous quicksort? Mais rappelez-vous, MergeSort n'est pas en place, il nécessite 2n meme space space.Et MergeSort doit également 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 le tri rapide, mais en réalité, vous devez tenir compte de l'espace mémoire, le coût de la copie d'un tableau, la fusion est plus lente que le tri rapide. Une fois, j’ai fait une expérience où j’avais reçu 1000000 chiffres en java par classe aléatoire, et cela a pris 2610ms par mergesort, 1370ms par quicksort.

Petits ajouts aux tris rapides ou fusionnés.

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 de plans, 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 un serveur distant.

De même, dans les conteneurs personnalisés tels que "liste chaînée", il n’ya aucun avantage à un tri rapide.
1. Fusionner le tri sur la liste chaînée, pas besoin de mémoire supplémentaire. 2. L’accès aux éléments du tri rapide n’est pas séquentiel (en mémoire)

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

Contrairement aux tableaux, dans la liste des éléments préférés, 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 mise en œuvre 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 chaînée lors de l’accès séquentiel aux données, sans grand accès à la mémoire aléatoire.

Par contre, le tri rapide nécessite beaucoup d’accès aléatoire à la mémoire et avec un tableau, on peut accéder directement à la mémoire sans la traversée requise par les listes chaînées. De plus, 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ë dans la mémoire.

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

EDIT: Je viens de découvrir que la fusion du pire / meilleur / moyen cas est toujours nlogn, mais le tri rapide peut varier de n2 (pire cas où les éléments sont déjà triés) à nlogn (moyen / meilleur cas lorsque pivot divise toujours le tableau en deux moitiés).

Prenez en compte la complexité du temps et de l’espace. Pour le tri par fusion: Complexité temporelle: O (nlogn), Complexité de l'espace: O (nlogn)

Pour le tri rapide: Complexité temporelle: O (n ^ 2), Complexité de l'espace: O (n)

Maintenant, ils gagnent tous les deux dans un scénario chacun. 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.

Dans les pays c / c ++, lorsque je n’utilise pas de conteneurs stl, j’ai tendance à utiliser quicksort, car il est construit dans le temps d'exécution, tandis que mergesort ne l'est pas.

Je pense donc que dans de nombreux cas, il s’agit simplement de 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 l'ensemble de travail.

Une des raisons est plus philosophique. Quicksort est la philosophie Top- & Down. Avec n éléments à trier, il y a n! possibilités. Avec 2 partitions de m & amp; 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 de 2 & amp; 3 chacun. et extrapoler à 1 million de factoriels vs 900K! * 100K! Alors, au lieu de vous préoccuper d’établir un ordre dans une plage ou une partition, établissez un ordre à un niveau plus large dans les partitions et réduisez les possibilités au sein d’une partition. Tout ordre établi précédemment dans une plage sera perturbé ultérieurement si les partitions elles-mêmes ne sont pas mutuellement exclusives.

Toute approche ascendante, telle que le tri par fusion ou par tas, est semblable à une approche d’employé ou d’employé dans laquelle on commence tôt à comparer au niveau microscopique. Mais cet ordre est voué à être perdu dès qu'un élément intermédiaire se trouve plus tard. Ces approches sont très stables & amp; extrêmement prévisible, mais fait un certain travail supplémentaire.

Quick Sort est comme une approche managériale dans laquelle on ne s’intéresse au départ à aucun ordre, mais seulement à la satisfaction d’un critère général sans égard pour l’ordre. Ensuite, les partitions sont réduites jusqu'à ce que vous obteniez un ensemble trié. Le véritable défi de Quicksort est de trouver une partition ou un critère dans le noir alors que vous ne connaissez rien des éléments à trier. C’est la raison pour laquelle nous devons soit nous efforcer de trouver une valeur médiane, soit en choisir 1 au hasard, ou une valeur "arbitraire" de gestion. approche. Trouver une médiane parfaite peut demander beaucoup d’efforts et déboucher à nouveau sur une approche ascendante stupide. Donc, Quicksort dit juste de choisir un pivot aléatoire et espère que ce sera quelque part au milieu ou que vous ferez du 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 être parfait & amp; ne perdez pas de temps dans la commande initiale. Cela semble bien fonctionner si vous êtes chanceux ou si vous vous abaissez parfois jusqu'à n ^ 2 lorsque vous n'obtenez pas de médiane, mais tentez votre chance. De toute façon, les données sont aléatoires. droite.  Je suis donc plutôt d’accord avec l’approche logique haut / bas de quicksort & amp; il s’avère que l’opportunité de choisir le pivot & amp; les comparaisons qu'il enregistre plus tôt semblent fonctionner mieux plus de fois que tout traitement méticuleux & amp; une approche approfondie et stable du bas - > up comme le tri par fusion. Mais

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top