Pourquoi le sorting rapide est-il meilleur que la fusion?

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 2 ) runtime le plus défavorable et O ( n log n ) runtime de cas moyen. Cependant, il est préférable de fusionner le sorting dans de nombreux scénarios, car de nombreux facteurs influencent le temps d’exécution d’un algorithme et, lorsqu’ils sont rassemblés, le sorting rapide gagne.

En particulier, l’exécution souvent citée des algorithmes de sorting fait référence au nombre de comparaisons ou au nombre de swaps à effectuer pour sortinger les données. C’est en effet 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.-à-d. 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 de cache, ce qui le rend plus rapide que le sorting par fusion dans de nombreux cas.

De plus, il est très facile d’éviter presque complètement le temps d’exécution le plus défavorable de O ( n 2 ) en utilisant un choix approprié de pivot – tel que le choisir au hasard (il s’agit d’une excellente stratégie).

En pratique, de nombreuses implémentations modernes de quicksort (en particulier std::sort libstdc ++) sont en réalité introsort , dont le pire cas théorique est O ( n log n ), identique au sorting par fusion. Cela se fait en limitant la profondeur de récursivité et en basculant vers un algorithme différent ( heapsort ) une fois qu’il dépasse log n .

Comme de nombreuses personnes l’ont noté, les performances moyennes des tests rapides sont plus rapides que celles de la fusion. Mais cela n’est vrai que si vous prenez un temps constant pour accéder à n’importe quelle 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 grave). Cependant, si votre structure de données est suffisamment grande pour vivre sur disque, le sorting rapide est éliminé par le fait que votre disque moyen fait quelque 200 recherches aléatoires par seconde. Mais ce même disque n’a aucun problème pour lire ou écrire des mégaoctets par seconde de données de manière séquentielle. C’est ce que fait exactement mergesort.

Par conséquent, si les données doivent être sortingées sur le disque, vous voulez vraiment utiliser certaines variantes de fusionsort. (En général, vous effectuez un sorting rapide des sous-listes, puis commencez à les fusionner au-dessus d’un certain seuil de taille.)

De plus, si vous devez faire quelque chose avec des ensembles de données de cette taille, réfléchissez bien à la manière d’éviter les recherches sur le disque. Par exemple, c’est la raison pour laquelle il est conseillé de supprimer les index avant de charger de grandes quantités de données dans des 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 firebase database peut reconstruire l’index en sortingant d’abord les informations à traiter (en utilisant une fusion 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 depuis un jeu de données sortingé avec peu de recherches sur le disque.)

Il y a eu un certain nombre d’occasions où comprendre comment éviter les recherches sur disque m’a permis de faire en sorte que les tâches de traitement des données prennent 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 le pire est O (n 2 ), ce qui se produit lorsque vous l’exécutez sur une liste contenant peu d’éléments uniques. La randomisation prend O (n). Bien sûr, cela ne change pas le pire des cas, il empêche simplement un utilisateur malveillant de faire votre sorting prend beaucoup de temps.

QuickSort est plus populaire car il:

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

Les algorithmes de sorting animé montrent un certain nombre d’algorithmes sur 4 conditions initiales différentes (aléatoires, presque sortingées, inversées, rares et uniques) et peuvent aider.

“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 intelligemment nommé. c’est à dire un bon marketing.

Oui, Quicksort avec sortingple partitionnement est probablement l’un des meilleurs algorithmes de sorting d’usage général, mais il n’y a pas de problème avec le fait que le sorting “rapide” semble beaucoup plus puissant que le sorting “Fusion”.

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

Ce qui rend Quicksort mieux en moyenne est que la boucle interne implique de comparer plusieurs valeurs avec une seule, tandis que les deux autres termes sont différents pour chaque comparaison. En d’autres termes, Quicksort fait deux fois moins de lectures que les deux autres algorithmes. Sur les processeurs modernes, les performances sont largement dominées par les temps d’access, de sorte que Quicksort finit par être un excellent premier choix.

J’aimerais append que sur les trois algorithmes mentionnés jusqu’ici (mergesort, quicksort et heap sort), seule la fusion est stable. En d’autres termes, 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 sorting rapide est … rapide =)

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

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

Mergesort est à prendre en compte si la rapidité est essentielle, les performances les plus défavorables ne peuvent être tolérées et un espace supplémentaire est disponible. 1

Vous avez déclaré qu’ils «sont tous 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 l’implémentation facile de l’access séquentiel que vous pouvez utiliser lors du sorting lors de l’utilisation de langages de programmation avec le paradigme impératif.

1 Sedgewick, Algorithmes

Quicksort est l’algorithme de sorting le plus rapide dans la pratique, mais il comporte 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 du monde réel qui montrent que le taux de retard est significativement plus lent que le court-métrage en moyenne.

De l’entrée Wikipedia sur Quicksort :

Quicksort est également en concurrence avec mergesort, un autre algorithme de sorting récursif, mais avec l’avantage du pire temps d’exécution Θ (nlogn). Mergesort est un type stable, contrairement au sorting rapide et à l’horticulture, et peut être facilement adapté pour fonctionner sur des listes liées et des listes très volumineuses stockées sur des supports lents tels que le stockage sur disque ou le stockage en réseau. Bien que le sorting rapide puisse être écrit pour fonctionner sur des listes liées, il sera souvent difficile de choisir un pivot sans access aléatoire. Le principal inconvénient de mergesort est que, dans les tableaux, il nécessite un espace auxiliaire Θ (n) dans le meilleur des cas, tandis que la variante de sorting rapide avec partitionnement sur place et récursion de la queue utilise uniquement de l’espace log (logn). (Notez que lorsque vous travaillez sur des listes liées, la fusion ne nécessite qu’une petite quantité constante de stockage auxiliaire.)

Les explications de Wikipedia sont:

En règle générale, le sorting rapide est beaucoup plus rapide dans la pratique que les autres algorithmes because (nlogn), car sa boucle interne peut être efficacement implémentée sur la plupart des architectures et dans la plupart des données réelles, il est possible de choisir .

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 quicksort n’ont pas. Dans le pire des cas, ils ont la même durée algorithmique, mais la fusion nécessite plus de stockage.

Quicksort n’est pas mieux que fusionner. Avec O (n ^ 2) (pire des cas), le sorting rapide est potentiellement beaucoup plus lent que le O (nlogn) du sorting de fusion. Quicksort a moins de surcharge, donc avec les petits ordinateurs et les ordinateurs lents, c’est mieux. Mais les ordinateurs sont tellement rapides aujourd’hui que les frais généraux supplémentaires liés à une fusion sont négligeables et que le risque d’un taux de réponse très lent dépasse largement le coût insignifiant d’une fusion dans la plupart des cas.

En outre, une fusion de lignes laisse des éléments avec des clés identiques dans leur ordre d’origine, un atsortingbut utile.

Je voudrais append aux excellentes réponses existantes des explications sur les performances de QuickSort en cas de divergence par rapport au meilleur et sur la probabilité, ce qui, je l’espère, aidera les gens à mieux comprendre pourquoi le cas O (n ^ 2) n’est pas réel préoccupation dans les implémentations plus sophistiquées de QuickSort.

En dehors des problèmes d’access aléatoire, deux facteurs principaux peuvent avoir un impact sur les performances de QuickSort. Ils sont tous deux liés à la manière dont le pivot se compare aux données en cours de sorting.

1) Un petit nombre de clés dans les données. Un dataset de la même valeur sortingera n ^ 2 fois sur un QuickSort vanilla à 2 partitions car toutes les valeurs, à l’exception de l’emplacement pivot, sont placées d’un côté à chaque fois. Les implémentations modernes traitent ceci par des méthodes telles que l’utilisation d’un sorting à 3 partitions. Ces méthodes s’exécutent sur un dataset de la même valeur en heure O (n). L’utilisation d’une telle implémentation signifie donc qu’une entrée avec un petit nombre de clés améliore le temps de performance et n’est plus un 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 seront plus petites et 50% que les données seront plus grandes, de sorte que l’entrée sera divisée par deux lors de chaque itération. Cela nous donne des comparaisons et des swaps fois les log-2 (n) récurrences pour l’heure O (n * logn).

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

Considérons un cas où le pivot est systématiquement choisi 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 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. Donc, cette qualité de choix de pivot prend 2,4 fois plus de temps que l’idéal.

À quelle vitesse cela devient-il pire?

Pas très rapide jusqu’à ce que le choix du pivot devienne (systématiquement) très mauvais:

  • 50% d’un côté: (cas idéal)
  • 75% d’un côté: 2,4 fois plus long
  • 90% d’un côté: 6.6 fois plus long
  • 95% d’un côté: 13,5 fois plus long
  • 99% d’un côté: 69 fois plus long

À l’approche de 100% d’un côté, la partie log de l’exécution est proche de n et l’exécution entière est asymptotiquement proche de O (n ^ 2).

Dans une implémentation naïve de QuickSort, des cas tels qu’un tableau sortingé (pour le pivot du premier élément) ou un tableau sortingé inversé (pour le pivot du dernier élément) produiront de manière fiable un temps d’exécution O (n ^ 2) le plus défavorable. De plus, les mises en œuvre avec une sélection de pivot prévisible peuvent être soumises à une attaque par déni de service 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 le sorting, 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 dataset. Le pire des cas est raisonnablement possible mais O (n ^ 2) n’est pas catastrophique car n est assez petit pour que n ^ 2 soit aussi petit.
  • Grand dataset. Le pire cas est possible en théorie mais pas en pratique.

Quelle est la probabilité de voir des performances terribles?

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 que les pivots qui se situent dans la plage de 25% à 75% sont «bons» et pivote dans la plage de 0% à 25% ou de 75% à 100% pour être «mauvais». Si vous regardez la dissortingbution de probabilités en utilisant la médiane de 3 index aléatoires, chaque récursivité a une chance de se retrouver avec un bon pivot de 11/16. Faisons 2 hypothèses prudentes (et fausses) pour simplifier le calcul:

  1. Les bons pivots sont toujours exactement à 25% / 75% et fonctionnent à 2,4 *. Nous ne obtenons jamais un partage idéal ou un partage meilleur que 25/75.

  2. Les mauvais pivots sont toujours les plus défavorables et ne consortingbuent essentiellement pas à la solution.

Notre implémentation QuickSort s’arrêtera à n = 10 et passera à un sorting par insertion, de sorte que nous avons besoin de 22 partitions pivot à 25% / 75% pour diviser la valeur de 5 000 entrées. (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 à n’importe quel moment, le sorting sera terminé, donc, dans le pire des cas, tout ce qui est proche nécessite beaucoup de malchance. Si cela nécessitait 88 récurrences pour atteindre les 22 bons pivots requirejs pour sortinger à 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 n’atteindrions pas les 22 bons pivots après 88 récurrences?

Les dissortingbutions de probabilité binomiale 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 seconde qu’il faut pour cliquer sur [TRIER] que de voir que 5 000 éléments sont plus mauvais. que 10 * cas idéal. Cette chance diminue lorsque le jeu de données devient plus grand. Voici quelques tailles de tableau et leurs chances de fonctionner plus longtemps que 10 * idéales:

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

Rappelez-vous que c’est avec 2 hypothèses prudentes qui sont 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 non.

Enfin, comme d’autres l’ont mentionné, même ces cas absurdement improbables peuvent être éliminés en passant à un sorting de tas si la stack de récurrence est trop profonde. Ainsi, le TLDR signifie que, pour de bonnes implémentations de QuickSort, le pire des cas n’existe pas, car il a été conçu et exécuté en O (n * logn).

La réponse serait légèrement orientée vers le quicksort par rapport aux changements apportés avec DualPivotQuickSort pour les valeurs primitives. Il est utilisé dans JAVA 7 pour sortinger 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 de JAVA7 ici – http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/7-b147/java/util/Arrays.java

Plus de lecture géniale sur DualPivotQuickSort – http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628

Bien qu’ils soient tous deux dans la même classe de complexité, cela ne signifie pas qu’ils ont tous deux le même temps d’exécution. Quicksort est généralement plus rapide que fusesort, simplement parce qu’il est plus facile de coder une implémentation serrée et que les opérations peuvent être plus rapides. C’est parce que le sorting rapide est généralement plus rapide que les gens l’utilisent au lieu de fusionner.

Toutefois! Personnellement, je vais souvent utiliser mergesort ou une variante de sorting rapide qui se dégrade pour fusionner lorsque le sorting rapide s’exécute mal. Rappelles toi. Le sorting rapide n’est que 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 un sorting simple.

Quicksort a une complexité de cas moyenne meilleure 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 à sortinger, il peut facilement construire un ensemble prenant la pire complexité temporelle de o (n ^ 2).

La complexité moyenne des cas de Mergesort et la complexité des cas les plus défavorables sont les mêmes et ne souffrent pas du même problème. Cette propriété de merge-sort en fait également le meilleur choix pour les systèmes en temps réel – précisément parce qu’il n’ya pas de cas pathologiques qui la font beaucoup courir, 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’attendrais à ce que la plupart des gens utilisent ce qui est le plus facilement 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 le sorting de radix ou de seau. Ils sont O (n), au moins sur les listes chaînées et il suffit d’une méthode pour convertir la clé en un nombre ordinal. (les chaînes 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 conférencier en parsing d’algorithme qu’il était en effet possible de sortinger plus rapidement que O (n log (n)). (Il avait la preuve que vous ne pouvez pas comparer le sorting plus rapidement que O (n log (n)), ce qui est vrai.)

Dans d’autres actualités, les flottants peuvent être sortingés sous forme d’entiers, mais vous devez inverser les nombres négatifs.

Edit: En fait, voici un moyen encore plus pervers de sortinger les flottants en tant qu’entiers: http://www.stereopsis.com/radix.html . Notez que l’astuce de retournement peut être utilisée quel que soit l’algorithme de sorting 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, c’est entre (n lg n – n + 1) et (ng n + n + O (lg n)). Mais pour QuickSort, le mieux est nlog2n (n est égal à 2 ^ k). Si vous divisez Mergesort par QuickSort, cela équivaut à 1 lorsque n est infini. c’est comme si le pire des cas de MergeSort était mieux que le meilleur cas de QuickSort, pourquoi nous utilisons quicksort? Mais rappelez-vous que MergeSort n’est pas en place, il nécessite 2n d’espace memeroy. n’inclut pas dans l’parsing de l’algorithme. En un mot, MergeSort est vraiment plus simple que QuickSort dans theroy, mais en réalité, vous devez considérer l’espace mémoire, le coût de la copie du tableau, la fusion plus lente que le sorting rapide. 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 bon?

  • QuickSort prend N ^ 2 dans le pire des cas et NlogN cas moyen. Le pire des cas se produit lorsque les données sont sortingées. Cela peut être atténué par un aléatoire aléatoire avant le début du sorting.
  • QuickSort ne prend pas de mémoire supplémentaire prise par sorting par fusion.
  • Si le jeu 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’éléments identiques est meilleur le sorting. Si tous les éléments sont identiques, il sortinge le temps 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é dans la sortie, vous utiliseriez Mergesort. La stabilité est requirejse 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, l’utilisation de Mergesort ne présente aucun danger.

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’object. Étant donné que les objects consumnt beaucoup de mémoire, l’ajout d’un peu de temps pour Mergesort peut ne poser aucun problème du sharepoint vue des performances.

Référence : Regardez les vidéos QuickSort de la troisième semaine du cours d’algorithmes de Princeton à Coursera

Le sorting rapide est le pire des cas O (n ^ 2), cependant, le cas moyen sort systématiquement du sorting par fusion. Chaque algorithme est O (nlogn), mais vous devez vous rappeler que lorsque vous parlez de Big O, nous omettons les facteurs de complexité inférieurs. Le sorting rapide a des améliorations significatives par rapport au sorting par fusion en ce qui concerne les facteurs constants.

Le sorting par fusion nécessite également la mémoire O (2n), tandis que le sorting rapide peut être effectué en place (ne nécessitant que O (n)). C’est une autre raison pour laquelle le sorting rapide est généralement préféré au sorting par fusion.

Informaitons supplémentaires:

Le pire cas de sorting 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, alors le sorting rapide sera exécuté dans O (n ^ 2). La probabilité de choisir l’élément qui est dans le plus grand ou le plus petit 25% de la liste est de 0,5. Cela donne à l’algorithme une chance sur 0,5 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 pivot faible est de 0,5 * n. Sur la base de cette probabilité, le sorting rapide est efficace pour le cas moyen (et typique).

En merge-sort, l’algorithme général est:

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

Au plus haut niveau, la fusion des deux sous-tableaux sortingés implique le traitement de N éléments.

Un niveau plus bas, chaque itération de l’étape 3 implique de traiter N / 2 éléments, mais vous devez répéter ce processus deux fois. Donc, vous avez toujours 2 * N / 2 == N éléments.

Un niveau plus bas, vous fusionnez 4 * N / 4 == N éléments, etc. Chaque profondeur de la stack récursive implique la fusion du même nombre d’éléments, pour tous les appels de cette profondeur.

Considérons plutôt l’algorithme de sorting rapide:

  1. Choisissez un sharepoint pivot
  2. Placez le point pivot au bon endroit dans le tableau, avec tous les éléments plus petits vers la gauche, et des éléments plus grands vers la 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 alors un sharepoint pivot, le placez dans la position correcte et vous pouvez ensuite l’ignorer complètement pour le rest de l’algorithme.

Un niveau en dessous de cela, vous traitez avec 2 sous-tableaux qui ont une taille combinée de N-1 (c.-à-d. Soustraire le point pivot précédent). Vous choisissez un sharepoint pivot pour chaque sous-masortingce, qui comprend 2 points de pivot supplémentaires.

One level below that, you’re dealing with 4 sub-arrays with combined size N-3, for the same reasons as above.

Then N-7… Then N-15… Then N-32…

The depth of your recursive stack remains approximately the same (logN). With merge-sort, you’re always dealing with a N-element merge, across each level of the recursive stack. With quick-sort though, the number of elements that you’re dealing with diminishes as you go down the stack. For example, if you look at the depth midway through the recursive stack, the number of elements you’re dealing with is N – 2^((logN)/2)) == N – sqrt(N).

Disclaimer: On merge-sort, because you divide the array into 2 exactly equal chunks each time, the recursive depth is exactly logN. On quick-sort, because your pivot point is unlikely to be exactly in the middle of the array, the depth of your recursive stack may be slightly greater than logN. I haven’t done the math to see how big a role this factor and the factor described above, actually play in the algorithm’s complexity.

When I experimented with both sorting algorithms, by counting the number of recursive calls, quicksort consistently has less recursive calls than mergesort. It is because quicksort has pivots, and pivots are not included in the next recursive calls. That way quicksort can reach recursive base case more quicker than mergesort.

Unlike Merge Sort Quick Sort doesn’t uses an auxilary space. Whereas Merge Sort uses an auxilary space O(n). But Merge Sort has the worst case time complexity of O(nlogn) whereas the worst case complexity of Quick Sort is O(n^2) which happens when the array is already is sorted.

Small additions to quick vs merge sorts.

Also it can depend on kind of sorting items. If access to items, swap and comparisons is not simple operations, like comparing integers in plane memory, then merge sort can be preferable algorithm.

For example , we sort items using network protocol on remote server.

Also, in custom containers like “linked list”, the are no benefit of quick sort.
1. Merge sort on linked list, don’t need additional memory. 2. Access to elements in quick sort is not sequential (in memory)

Something to consider is memory as well. Mergesort requires an additional array, say a “workspace array”. If your memory is barely big enough to store your original array, then mergesort will not work.

Quick sort is an in-place sorting algorithm, so its better suited for arrays. Merge sort on the other hand requires extra storage of O(N), and is more suitable for linked lists.

Unlike arrays, in liked list we can insert items in the middle with O(1) space and O(1) time, therefore the merge operation in merge sort can be implemented without any extra space. However, allocating and de-allocating extra space for arrays have an adverse effect on the run time of merge sort. Merge sort also favors linked list as data is accessed sequentially, without much random memory access.

Quick sort on the other hand requires a lot of random memory access and with an array we can directly access the memory without any traversing as required by linked lists. Also quick sort when used for arrays have a good locality of reference as arrays are stored contiguously in memory.

Even though both sorting algorithms average complexity is O(NlogN), usually people for ordinary tasks uses an array for storage, and for that reason quick sort should be the algorithm of choice.

EDIT: I just found out that merge sort worst/best/avg case is always nlogn, but quick sort can vary from n2(worst case when elements are already sorted) to nlogn(avg/best case when pivot always divides the array in two halves).

This is a pretty old question, but since I’ve dealt with both recently here are my 2c:

Merge sort needs on average ~ N log N comparisons. For already (almost) sorted sorted arrays this gets down to 1/2 N log N, since while merging we (almost) always select “left” part 1/2 N of times and then just copy right 1/2 N elements. Additionally I can speculate that already sorted input makes processor’s branch predictor shine but guessing almost all twigs correctly, thus preventing pipeline stalls.

Quick sort on average requires ~ 1.38 N log N comparisons. It does not benefit greatly from already sorted array in terms of comparisons (however it does in terms of swaps and probably in terms of branch predictions inside CPU).

My benchmarks on fairly modern processor shows the following:

When comparison function is a callback function (like in qsort() libc implementation) quicksort is slower than mergesort by 15% on random input and 30% for already sorted array for 64 bit integers.

On the other hand if comparison is not a callback, my experience is that quicksort outperforms mergesort by up to 25%.

However if your (large) array has a very few unique values, merge sort starts gaining over quicksort in any case.

So maybe the bottom line is: if comparison is expensive (eg callback function, comparing ssortingngs, comparing many parts of a structure mostly getting to a second-third-forth “if” to make difference) – the chances are that you will be better with merge sort. For simpler tasks quicksort will be faster.

That said all previously said is true: – Quicksort can be N^2, but Sedgewick claims that a good randomized implementation has more chances of a computer performing sort to be struck by a lightning than to go N^2 – Mergesort requires extra space

In c/c++ land, when not using stl containers, I tend to use quicksort, because it is built into the run time, while mergesort is not.

So I believe that in many cases, it is simply the path of least resistance.

In addition performance can be much higher with quick sort, for cases where the entire dataset does not fit into the working set.

One of the reason is more philosophical. Quicksort is Top->Down philosophy. With n elements to sort, there are n! possibilités With 2 partitions of m & nm which are mutually exclusive, the number of possibilities go down in several orders of magnitude. m! * (nm)! is smaller by several orders than n! alone. imagine 5! vs 3! *2!. 5! has 10 times more possibilities than 2 partitions of 2 & 3 each . and extrapolate to 1 million factorial vs 900K!*100K! vs. So instead of worrying about establishing any order within a range or a partition,just establish order at a broader level in partitions and reduce the possibilities within a partition. Any order established earlier within a range will be disturbed later if the partitions themselves are not mutually exclusive.

Any bottom up order approach like merge sort or heap sort is like a workers or employee’s approach where one starts comparing at a microscopic level early. But this order is bound to be lost as soon as an element in between them is found later on. These approaches are very stable & extremely predictable but do a certain amount of extra work.

Quick Sort is like Managerial approach where one is not initially concerned about any order , only about meeting a broad criterion with No regard for order. Then the partitions are narrowed until you get a sorted set. The real challenge in Quicksort is in finding a partition or criterion in the dark when you know nothing about the elements to sort. That is why we either need to spend some effort to find a median value or pick 1 at random or some arbitrary “Managerial” approach . To find a perfect median can take significant amount of effort and leads to a stupid bottom up approach again. So Quicksort says just a pick a random pivot and hope that it will be somewhere in the middle or do some work to find median of 3 , 5 or something more to find a better median but do not plan to be perfect & don’t waste any time in initially ordering. That seems to do well if you are lucky or sometimes degrades to n^2 when you don’t get a median but just take a chance. Any way data is random. right. So I agree more with the top ->down logical approach of quicksort & it turns out that the chance it takes about pivot selection & comparisons that it saves earlier seems to work better more times than any meticulous & thorough stable bottom ->up approach like merge sort. Mais