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. |
| Moyenne | Cet article a été classé comme d'Importance moyenne selon le Tableau d'évaluation du projet. (Contester?) |
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 ...)
