Lors de la fusion de tri est préféré au tri Rapide?
Tri rapide est beaucoup mieux que la fusion de tri dans de nombreux cas. Mais, quand est-ce le cas lors de la fusion de tri pourrait être une meilleure solution que le tri rapide?
Par exemple, la fusion de tri fonctionne mieux que le tri rapide lorsque les données ne peuvent pas être chargées dans la mémoire à la fois. Existe-il d'autres cas?
EDIT:
Les réponses de cette double question de la liste de tous les avantages de la fonction de tri rapide au cours de fusion de tri. Je pose la question ici sur le cas possibles et des applications à l'aide de fusion de tri en serait avantageux que d'utiliser la fonction de tri rapide.
- Dupliquer l'omi: why-is-quicksort-better-than-mergesort
Vous devez vous connecter pour publier un commentaire.
Je devrais probablement commencer par mentionner que les deux quicksort et mergesort peut très bien fonctionner si vous ne pouvez pas tout faire rentrer dans la mémoire à la fois. Vous pouvez mettre en œuvre quicksort par le choix d'un pivot, puis streaming éléments à partir de la disquette dans la mémoire et l'écriture des éléments dans l'une des deux fichiers différents selon la manière dont l'élément de comparaison, le pivot. Si vous utilisez un double clos file d'attente de priorité, vous pouvez réellement faire cela de manière encore plus efficace en ajustant le nombre maximum d'éléments possibles en mémoire à la fois.
D'autres ont mentionné l'intérêt que mergesort est le pire des cas en O(n log n), ce qui est certainement vrai. Cela dit, vous pouvez facilement modifier le quicksort pour produire de l' introsort algorithme, un hybride entre quicksort, le tri par insertion, et heapsort, c'est le pire des cas O(n log n), mais conserve la vitesse de quicksort dans la plupart des cas.
Il pourrait être utile de voir pourquoi quicksort est généralement plus rapide que mergesort, car si vous comprenez les raisons pour lesquelles vous pouvez très rapidement trouver des cas où mergesort est un gagnant clair. Quicksort est généralement mieux que mergesort pour deux raisons:
Quicksort a mieux la localité de référence de mergesort, ce qui signifie que l'accès réalisés dans quicksort sont généralement plus rapides que les accès en mergesort.
Quicksort utilise pire des cas en O(log n) de la mémoire (si elles sont appliquées correctement), tandis que mergesort nécessite O(n) de la mémoire en raison de la surcharge de la fusion.
Il y a un scénario, cependant, lorsque ces avantages disparaissent. Supposons que vous voulez trier une liste chaînée d'éléments. La liste liée éléments sont dispersés à travers la mémoire, de sorte que l'avantage (1) disparaît (il n'y a pas de localité de référence). Deuxièmement, les listes peuvent être fusionnés avec seulement O(1) espace supplémentaire au lieu de O(n) l'espace des frais généraux, de sorte avantage (2) disparaît. Par conséquent, généralement, vous trouverez que mergesort est supérieure algorithme de tri des listes liées, car il fait moins le total des comparaisons et n'est pas sujet à une mauvaise pivot choix.
Espérons que cette aide!
Un seul, le plus important avantage de la fusion de tri plus rapide, le tri est sa stabilité: les éléments par rapport égal à conserver leur ordre d'origine.
Quicksort est dans la moyenne des cas O(n log n), mais a un pire cas O(n^2). Mergesort est toujours O(n log n). En plus de l'asymptotique pire des cas et de la mémoire de chargement de mergesort, je ne peux pas penser à une autre raison.
Scénarios lorsque quicksort est pire que mergesort:
Prendre mergesort plus de quicksort si vous ne savez pas quelque chose sur les données.
De fusion de tri a une garantie sur la limite supérieure de O(N log2N). Tri rapide a la limite, trop, mais il est beaucoup plus élevé, il est O(N2). Lorsque vous avez besoin d'une garantie de limite supérieure sur le calendrier de votre code, utilisez de fusion de tri plus rapide de tri.
Par exemple, si vous écrivez du code pour un système en temps réel qui s'appuie sur le tri, la fusion pourrait être un meilleur choix.