Tri rapide contre le tri par fusion

Question

Pourquoi le tri rapide peut-il être meilleur que le tri par fusion?

Answer 1

Voir Quicksort sur wikipédia:

Généralement, quicksort est significativement plus rapide dans la pratique que les autres Θ(nlogn) les algorithmes, car sa boucle interne peut être efficacement mis en œuvre sur la plupart des architectures, et dans la plupart du monde réel de données, il est possible de faire de la conception de des choix qui réduisent au minimum la probabilité d'exiger quadratique du temps.

Notez que la très faible capacité de mémoire est un gros plus.

Answer 2

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

Answer 3

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

Voir cette comparaison .

Vous pouvez également le voir visuellement .

Answer 4

Alors que quicksort est souvent un meilleur choix que la fusion de tri, il y a certainement des moments où de fusion tri est thereotically un meilleur choix. La plupart de temps évident, c'est quand il est extrêmement important que votre algorithme de courir plus vite que O(n^2). Quicksort est généralement plus rapide que cela, mais compte tenu de l'théorique pire d'entrée possibles, il pourrait s'exécuter en O(n^2), qui est pire que le pire fusion possible de trier.

Quicksort est aussi plus compliqué que mergesort, surtout si vous voulez écrire un solide de mise en œuvre, et donc, si vous visez la simplicité et la facilité de maintenance, de fusion et le tri devient une alternative prometteuse avec très peu de perte de performance.

Answer 5

Personnellement, je voulais tester la différence entre la fonction de tri Rapide et de fusion le tri moi-même et vu le temps d'exécution pour un échantillon de 1 000 000 d'éléments.

Tri rapide a été en mesure de le faire dans 156 millisecondesalors que Fusion de tri a fait de même dans 247 millisecondes

Le tri Rapide des données a été, cependant, a été aléatoire et rapide de tri fonctionne bien si les données sont aléatoires, où qu'il ne soit pas le cas de la fusion ie tri fusion tri effectue indépendamment de la même lorsque les données sont triées ou non. Mais la fusion de tri nécessite un plein d'espace supplémentaire et tri rapide n'est pas comme une sorte

J'ai écrit complet de programme de travail pour eux des illustrations trop.