Pourquoi le quicksort est-il meilleur que le mergesort?

Question

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?

Answer 1

Quicksort a O(n²) pire cas d'exécution et de O(nlogn) en moyenne cas de l'exécution. Cependant, il est supérieur à la fusion de tri dans de nombreux scénarios, car de nombreux facteurs influent sur un algorithme d'exécution, et, lors de leur prise tous ensemble, quicksort qui l'emporte.

En particulier, souvent cité d'exécution des algorithmes de tri désigne le nombre de comparaisons ou le nombre d'échanges nécessaires à effectuer pour trier les données. C'est en effet une bonne mesure de la performance, surtout que c'est indépendant du matériel sous-jacent de la conception. Cependant, d'autres choses – comme la localité de référence (c'est à dire nous ne pouvons lire que 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, et cela le rend plus rapide que la fusion de tri dans de nombreux cas.

En outre, il est très facile de les éviter quicksort est des cas les pires temps d'exécution de O(n²) presque entièrement à l'aide d'un choix approprié de le pivot – telles que le prélèvement au hasard (ce qui est une excellente stratégie).

Dans la pratique, nombreux sont les implémentations modernes de quicksort (en particulier libstdc++' std::sort) sont en réalité des introsort, dont théorique pire des cas est O(nlogn), de même que la fusion de tri. Pour cela, il permet de limiter la profondeur de récursivité, et de passer à un autre algorithme (heapsort) une fois qu'il dépasse logn.

Answer 2

Comme beaucoup de gens l'ont noté, la moyenne des performances de tri rapide est plus rapide que mergesort. Mais cela n'est vrai que si vous êtes en supposant que la constante de temps d'accès à tout élément de mémoire à la demande.

Dans la mémoire vive cette hypothèse est généralement pas trop mal (il n'est pas toujours vrai, car des caches, mais il n'est pas trop mauvais). Toutefois, si votre structure de données est assez grand pour vivre sur le disque, puis quicksort obtient tué par le fait que la moyenne de votre disque fait quelque chose comme 200 aléatoire cherche par seconde. Mais ce disque n'a pas de difficultés de lecture ou d'écriture en mégaoctets par seconde de données de manière séquentielle. Ce qui est exactement ce mergesort.

Par conséquent, si les données sont triées sur le disque, vous vraiment, voulez vraiment utiliser une certaine variation sur mergesort. (En général, vous quicksort des sous-listes, puis commencer à les fusionner ensemble au dessus d'un certain seuil de taille.)

En outre, si vous avez à faire tout avec jeux de données de taille, de réfléchir à comment éviter cherche à disque. Par exemple, ce est pourquoi il est conseillé de le faire que de supprimer les index avant de faire de grands chargements de données dans des bases de données, puis de reconstruire l'index plus tard. Le maintien de l'index lors de la charge des moyens permanence à la recherche de disque. En revanche si vous supprimez l'index, puis la base de données peut reconstruire l'index par le premier tri de l'information (à l'aide d'un mergesort bien sûr!) et puis le charger dans un ARBRE discbased pour l'index. (BTREEs sont naturellement conservées dans l'ordre, de sorte que vous pouvez charger l'un de triés dataset avec quelques cherche sur le disque.)

Il y a eu un certain nombre d'occasions où la compréhension de la façon d'éviter de disque cherche a me laisser faire le traitement des données des emplois de prendre des heures plutôt qu'en jours ou semaines.

Answer 3

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

QuickSort est plus populaire parce qu'il:

1. Est en place (MergeSort nécessite des tonnes de mémoire supplémentaire).
2. A une petite caché constante.

Answer 4

Les algorithmes de tri animé présentent un certain nombre d'algorithmes sur 4 conditions initiales différentes et pourraient aider.

Answer 5

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

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

Oui, Quicksort avec triple partioning est probablement l'un des meilleurs algorithmes de tri à usage général, mais il n'y a pas de raison pour que le tri "Quick" soit beaucoup plus puissant que le tri "Merge".