Discuter:Tri rapide
Un article de Wikipédia, l'encyclopédie libre.
 |
Tri rapide fait partie du projet Informatique, qui a pour but d'enrichir le contenu de Wikipédia sur les sujets liés à l'informatique. Si vous voulez participer, vous pouvez modifier cet article ou visiter la page du projet où vous pourrez vous joindre au projet et consulter la liste des tâches et des objectifs. Le portail informatique pourrait aussi vous intéresser. |
| B | Cet article a été classé comme d'Avancement B selon le Tableau d'évaluation du projet. (Voir les statistiques) |
| Moyenne | Cet article a été classé comme d'Importance moyenne selon le Tableau d'évaluation du projet. (Contester?) |
[modifier] Complexité
J'ai supprimé dans:
Autre algorithme de tri compétitif
a partir de Musser reported that on a ...
A variation on quicksort which is becoming widely used is introspective sort, often called introsort (Musser 1997). This starts with quicksort and switches to heapsort when the recursion depth exceeds a preset value. This overcomes the overhead of increasingly complex pivot selection techniques while ensuring O(n log n) worst-case performance. Musser reported that on a median-of-3 killer sequence of 100,000 elements running time was 1/200th that of median-of-3 quicksort. Musser also considered the effect of Sedgewick delayed small sorting on caches, reporting that it could double the number of cache misses but that its performance with double-ended queues was significantly better and it should be retained for template libraries, in part because the gain in other cases from doing the sorts immediately was not great.
- quelqu'un connaissant ce papier de Musser devrait verifier le chiffre 1/200 iéme
The June 2000 SGI C++ Standard Template Library stl_algo.c implementation of unstable sort uses the Musser introsort approach with the recursion depth to switch to heapsort passed as a parameter, median-of-3 pivot selection and the Sedgewick final insertion sort pass. The element threshold for switching to the simple insertion sort was 16.
- pas intérréssant a mon avis
The C++ STL implementations generally significantly (several times as fast) outperform the C implementation because they are implemented to allow inlining, while the generic C equivalent must use function calls for comparisons. This advantage could be compensated for by using custom versions of the sort function, at the cost of losing the advantage of a totally generic library function. An example of the importance of constant and architecture factors.
- un bon moyen de lancer une flame war sur les news groupes :), il faut au moins dire sous quelles conditions ces chiffres sont correctes (s'il le sont ...)
Phe 8 avril 2004 à 13:57
[modifier] Date d'invention
Bonjour, un léger détail mais la version anglaise et la version française de cette page ne s'accordent pas sur les dates d'invention de cet algo. La page anglaise (et je viens de voir que la page allemande également) donne 1960 tandis que la page française donne 1962. Une recherche rapide sur google scholar me donne un article de 1962 [[1]]. Je retrouve 1960 ou 1962 un peu partout (et même un 1961...) en faisant une rapide recherche. Quelqu'un aurait il un peu de temps pour faire une recherche un peu plus approndie et aligner les dates ? D'ailleurs la page en français concernant l'auteur donne également 1960 pour la date de l'algo.
- La première date de publication est 1961 donné dans les références « Algorithm 64: Quicksort CAR Hoare - Communications of the ACM, 1961 », possible que l'algo a été développé plus tôt mais je n'en trouve pas de trace sure, il faudrait avoir accès à cette publication pour voir si Hoare en parle, en tout cas j'ai corrigé de 1962 à 1961 l'intro. - phe 15 novembre 2007 à 10:32 (CET)
[modifier] Compléxité bis
Les notions de complexité moyenne et au pire cas sont très mal présentées. Dans le langage courant de l'algorithmique, quand on donne la complexité sans plus préciser, il est clair que le "au pire cas" est sous-entendu. Ici Quicksort est présenté comme ayant une complexité en nlogn, avec des tournures comme "voire peut être lent (complexité en n2)", et la précision "si l'implémentation est malhabile (au niveau du choix du pivot)" n'a pas de sens car la complexité théorique n'est pas liée à l'implémentation (on peut toujours programmer n'importe quoi).83.206.37.61
