Discuter:Algorithme de tri
Un article de Wikipédia, l'encyclopédie libre.
 |
Algorithme de tri 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?) |
Il me semble que le tri rapide est en O(n^2) au pire cas, mais qu en moyenne il est en n.log(n)
Dtcube
Je crois que tu as raison. Mais il me semble qu'il est possible de le modifier légérement pour qu'il soit toujours de l'ordre de n.log(n) (en choisissant intelligemment le pivot au lieu de le prendre au hasard)
Apres verification il semble bien que non
Dtcube
- Non pour quoi? Pour la complexité en O(n^2) ou pour la possibilité d'amélioration?
Non pour la possibilite d'amelioration. Il y a des variantes pour le choix du pivot mais la complexite au pire cas reste O(n^2).
En effet, en choisissant le pivot adéquatement, il est possible de réduire la probabilité de la performance en O(n^2), mais pas de l'éliminer.
Tiré de Wikipedia anglais Louis 18 avr 2005 à 05:17 (CEST)
Bonjour, après lecture de l'article sur le tri par dénombrement (ou comptage), il me semble que sa complexité soit pseudo-polynomiale : on doit initialiser un tableau dont la longueur est au moins égale au maximum des valeurs à trier. Je ne sais pas s'il est possible d'utiliser des structures de données pour compter les occurrences de chacune des valeurs permettant un réel O(n). Si c'est le cas, on pourrait peut-être le mentionner dans l'article du tri par dénombrement. Sinon, il faudrait corriger la page sur les algorithme de tri. Qu'en pensez-vous ? bweps
[modifier] Complexité comparée de heapsort et quicksort
L'article affirme que quicksort est en pratique 2× plus rapide que merge-sort. A-t-on une référence? (Sachant que de nos jours on a des machines avec du cache etc. donc les comparaisons d'il y a 20 ans ne sont pas forcément pertinentes.) David.Monniaux 23 octobre 2006 à 10:36 (CEST)
[modifier] Aspects out-of-core
Il me semble que notre classification des algorithmes de tri gagnerait à avoir une analyse des cas où l'on a plusieurs niveaux de mémoire (cache vs mémoire principale, mémoire principale vs disque). À vue de nez, par exemple, le tri par tas est désastreux sur disque dur (accès non locaux), tandis que le tri fusion passe bien (accès séquentiels). Je n'ai pas trop le temps de chercher la littérature sur le sujet... David.Monniaux 23 octobre 2006 à 10:38 (CEST)
