Tri rapide Vs Tri par fusion [dupliquer]

le tri rapide est généralement plus rapide que le tri par fusion lorsque les données sont stockées en mémoire. Toutefois, lorsque l'ensemble de données est énorme et est stocké sur des périphériques externes tels qu'un disque dur, de fusion, le tri est le gagnant clair en termes de vitesse. Il minimise les lectures coûteuses du lecteur externe et se prête également bien à l'informatique parallèle.

pour le tri par fusion le pire cas est O(n*log(n)) , pour le tri rapide: O(n ² ) . Pour les autres cas (avg, best) tous les deux ont O(n*log(n)) . Cependant le tri rapide est constante d'espace où le tri de fusion dépend de la structure que vous triez.

voir cette comparaison .

, Vous pouvez aussi le voir visuellement .

j'ai personnellement voulu tester la différence entre le tri rapide et le tri par fusion moi-même et j'ai vu les temps de fonctionnement pour un échantillon de 1.000.000 éléments.

Quick sort a pu le faire en 156 millisecondes alors que Merge sort a fait la même chose en 247 millisecondes

les données de tri rapide était, cependant, était aléatoire et tri rapide fonctionne bien si les données est aléatoire où comme ce n'est pas le cas avec fusion ie tri fusion tri effectue indépendamment de la même lorsque les données sont triées ou non. Mais le tri de fusion nécessite un espace supplémentaire complet et le tri rapide ne fait pas comme son tri en place

j'ai écrit programme de travail complet pour eux illustrera des images aussi.

bien que quicksort soit souvent un meilleur choix que le sort de fusion, il y a certainement des moments où le sort de fusion est un meilleur choix. Le moment le plus évident est quand il est extrêmement important que votre algorithme tourne plus vite que O(N^2). Quicksort est généralement plus rapide que cela, mais compte tenu de la pire entrée théorique possible, il pourrait fonctionner dans O(N^2), qui est pire que la pire sorte de fusion possible.

Quicksort est aussi plus compliqué que mergesort, surtout si vous voulez écrire une implémentation vraiment solide, et donc si vous visez la simplicité et la maintenabilité, merge sort devient une alternative prometteuse avec très peu de perte de performance.

en plus des autres: Merge sort est très efficace pour les structures de données immuables comme les listes liées et est donc un bon choix pour les langages de programmation (purement) fonctionnels.

un quicksort mal mis en œuvre peut être un risque de sécurité .

Quicksort est en place. Vous avez juste besoin d'échanger les positions des données pendant la fonction de partitionnement. Mergesort nécessite beaucoup plus de copie de données. Vous avez besoin d'un autre stockage temporaire (généralement la même taille que votre tableau de données original) pour la fonction de fusion.

quicksort est nommé ainsi pour une raison,

souligne : les deux sont des sortes stables, (simplement une nuisance de mise en œuvre), alors passons aux complexités

sa très confus avec juste le big-oh notations renversé et "abusé" , les deux ont la moyenne la complexité de l'affaire de 0(nlogn) ,

mais le tri de fusion est toujours 0 ( nlogn), alors que quicksort pour les mauvaises partitions, c'est-à-dire les partitions asymétriques comme 1 élément - 10 élément (ce qui peut se produire en raison de la liste triée ou inversée ) peut conduire à un 0(N^2)..

.. et donc nous avons un quicksort aléatoire, où nous choisissons le pivot au hasard et évitons un tel partitionnement asymétrique, annulant ainsi l'ensemble du scénario n^2 quoi qu'il en soit , même pour un partitionnement modérément asymétrique comme 3-4, nous avons un nlog(7/4)n, idéalement nous voulons 1-1 partion, donc le 2 entier de O(nlog(2)n).

ainsi il est O ( nlogn), presque toujours et à la différence de fusionner trier le les constantes cachées sous la notation "big-oh" sont meilleures pour quicksort que pour mergesort ..et il n'utilise pas d'espace supplémentaire comme une sorte de fusion.

mais obtenir quicksort exécuter parfaitement exige de peaufinage ,reformuler , quicksort vous fournit des occasions de peaufiner ....

la réponse pencherait légèrement vers quicksort W. R. t to changes brought with DualPivotQuickSort for primitive values . Il est utilisé dans JAVA 7 pour trier dans java.util.Tableaux

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

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

Il n'est pas vrai que quicksort est mieux. De plus, cela dépend de ce que vous voulez dire par "mieux", "consommation de mémoire" ou "vitesse".

en termes de consommation de mémoire, dans le pire des cas, mais quicksort peut utiliser n^2 mémoire (c.-à-d. chaque partition est de 1 À n-1), tandis que merge sort utilise nlogn.

ce qui précède suit en termes de vitesse.

Quicksort est en place. Vous avez besoin de très peu de mémoire supplémentaire. Ce qui est extrêmement important.

le bon choix de la médiane le rend encore plus efficace mais même un mauvais choix de la médiane en quarantaine Theta (nlogn).