Comme nous le savons, la performance Quicksort est O (n * journal (n)) en moyenne, mais la performance fusion- et tastort est également (n * log (n)) en moyenne. Donc, la question est de savoir pourquoi Quicksort est plus rapide en moyenne.
3 Réponses :
Typiquement, le Quicksort est significativement plus rapide dans la pratique que d'autres O (nlogn) algorithmes, parce que sa boucle interne peut être efficacement mis en œuvre sur la plupart Architectures, et dans la plupart des pays réels données, il est possible de faire des conceptions choix qui minimisent la probabilité de nécessiter de temps quadratique. De plus, QuicksTort a tendance à faire Excellente utilisation de la mémoire hiérarchie, prenant un avantage parfait de Mémoire virtuelle et caches disponibles. Bien que le Quicksort n'est pas un pays trier et utilise la mémoire auxiliaire, il est très bien adapté à l'ordinateur moderne Architectures.
Regardez également Comparaison avec d'autres algorithmes de tri sur la même page.
Voir aussi Mieux vaut-il mieux que autres algorithmes de tri dans la pratique? sur le site CS.
Savez-vous comment il "profite de la mémoire virtuelle et du cache"? N'importe quel exemple?
Si vous cherchez à penser en termes d'algorithme lui-même, ne vous inquiétez pas de la mémoire virtuelle et du cache. Les algorithmes ne s'appuient pas sur le matériel.
L'algorithme traverse séquentiellement qui fait du bon localité de référence ( en.wikipedia.org / wiki / localité_of_reference ) qui fait bien fonctionner votre cache (et accélère donc le travail)
Je pense toujours que les algos ne dépendent pas du cache du tout. Un algorithme étant stable ou en place fait la différence en termes de mémoire, mais que tous. Les algorithmes n'ont rien à voir avec aucun type de cache, à l'exception de la mémoisation.
Les algorithmes qui lisent la mémoire de manière séquentielle potentiellement potentiellement l'élément suivant sont facilement disponibles dans le cache (rapide) en raison de la taille de la ligne de cache. Pourquoi ne pouvait-elle pas influencer la vitesse opposée à un algorithme qui traverse des emplacements de mémoire plutôt imprévisibles?
@Michael: Quicksort a deux avantages concernant le cache. Tout d'abord, l'accès séquentiel - les points de lecture et d'écriture se déplacent dans la mémoire de manière à ce que vous n'ayez accessible que quelques pages à la fois, et la préfecture a de bonnes chances de travailler. Comparez quelque chose comme la recherche binaire dans une sorte d'insertion, qui ne visite pas autant d'emplacements (dans chaque passage), mais visites des emplacements dispersés, il risque donc d'être plus lent par accès. Deuxièmement, la récursivité descendante offre une forme d'oblibilité cache - une fois que les sections que vous travaillez sont plus petites qu'une page, tout accélère considérablement.
(Ce n'est pas que le tri d'insertion est l'une des n logements N TRES que nous comparons, mais la comparaison entre QuickSort et Sort d'insertion est très importante, car généralement avec QuickSort, vous souhaitez passer à l'insertion Trier à une taille de grande taille surprenante, où l'insertion devient plus rapide). Mergesort est également un accès séquentiel. Heapsort a une structure à l'accès, bien sûr, mais est un peu partout.
Timsort pourrait être un option meilleure car il est optimisé pour le type de données observées lors du tri en général, dans la langue Python où les données sont souvent Contient des «courses» intégrées d'éléments pré-ardents. Il a été récemment adopté par Java aussi.
Le pire cas de tri rapide est effectivement pire que le tasPher et Mergesort, Pourquoi, il faudra du temps pour expliquer et donc je vais faire référence à Skiena, le manuel de conception d'algorithme.
une citation qui résume le QuickSort VS Fusion / HeapSort:
face aux algorithmes de la même complexité asymptotique, la mise en œuvre
Les détails et les bizarreries de système tels que la performance de cache et la taille de la mémoire peuvent
bien se révéler être le facteur décisif.
Ce que nous pouvons dire, c'est que les expériences montrent que lorsqu'il est correctement mis en œuvre
Quicksort est bien implémenté, il est typiquement 2 à 3 fois plus rapide que Mergesort ou
tasort. La principale raison est que les opérations de la boucle la plus interne sont
Plus simple. Mais je ne peux pas discuter avec vous si vous ne me croyez pas quand je dis Quicksort est
plus rapide. C'est une question dont la solution réside en dehors des outils analytiques que nous utilisons.
La meilleure façon de dire est de mettre en œuvre des algorithmes et une expérience.
Heapsort est O (n * log (n)) dans le pire des cas - probablement dans tous les cas.