Discussion:Algorithme de tri

Discussion de 2005

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).

Dtube

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)

---

Comme le dit Louis, il est toujours "possible" de tomber par "hasard" sur un pivot majorant (ou minorant) tout le sous-ensemble à partitionner. Et cela à chaque itération. La probabilité en est moindre, mais mathématiquement différente de 0. Donc ce pire cas reste $O(n^{2})$.

Argos42 (d) 23 décembre 2008 à 14:27 (CET)

---

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

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)

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)

Comparaison des algorithmes de tri en place

Bonjour, je me pose des questions concernant la section « Comparaison des algorithmes de tri en place ». Il est vrai que les complexités asymptotiques ne font pas tout, et il peut être intéressant de comparer empiriquement certains algorithmes entre eux. Toutefois, on ne compare plus vraiment des algorithmes, mais des implémentations précises, dans un langage donné, compilées d'une certaine manière, exécutées sur une machine donnée. J'ai l'impression que la section en l'état manque de précisions (quelle implémentation, sur combien d'exécutions sont effectuées les moyennes etc.). De plus la manière dont la complexité est évaluée (« nb. de comparaisons + nb. d'écritures ») me semble discutable, et pourrait créer des interrogations chez certains lecteurs ; cela semble un peu à mi-chemin entre une évaluation théorique et empirique. Quitte à effectuer une implémentation, pourquoi ne pas mesurer directement le temps d'exécution ?

Serait-il possible d'avoir plus de détails sur la manière dont les graphes ont été générés, de sorte à donner plus d'indications et à éventuellement compléter la section (évaluation du temps lorsque l'entrée est triée par exemple) ? (Peut-être que Circular, qui semble à l'origine de ces ajouts si je ne me trompe pas, est dans les parages :) ?)

Tous les avis et points de vue sont les bienvenus.

-- Zooky (discuter) 19 octobre 2015 à 11:45 (CEST)

Bonjour, apparemment Circular (d · c · b) contribue deux-trois jours par an, donc il y a peu de chances qu'il réponde tout de suite. De mon point de vue une grosse partie de cet article vient d'un travail personnel, assez intéressant mais plus en accord avec le style de la wikipedia actuelle. Il faudrait faire une refonte et un gros sourçage, mais j'en ai toujours eu la flemme. --Roll-Morton (discuter) 19 octobre 2015 à 16:25 (CEST)

Oui j'ai vu que Circular ne contribuait plus trop récemment, c'était au cas où… et c'est aussi pour avoir des avis externes du coup. J'ai commencé à compléter des paragraphes, ajouter quelques infos, je projette de sourcer au maximum, mais je ne veux pas supprimer toute une partie comme ça d'un coup :) Surtout que l'idée de départ est bonne. -- Zooky (discuter) 19 octobre 2015 à 17:04 (CEST)

Références

Bonjour, il y a un bandeau « travail inédit / déclarations non vérifiés », mais je ne suis pas sûr de comprendre pourquoi. J'ai supprimé l'affirmation sur quicksort/heapsort qui est fausse jusqu'à preuve du contraire. Quelles seraient les informations à sourcer ? Je ne suis pas certain qu'il soit utile de justifier chaque complexité énoncée, étant donné que les détails sont donnés sur les pages des algorithmes, si ? − Zooky (discuter) 2 novembre 2015 à 18:04 (CET)

Ce bandeau « inédit » a été ajouté par un script nommé xpatrol, à qui il semble difficile de demander de se justifier. Je supprime le bandeau. --Pierre de Lyon (discuter) 4 novembre 2015 à 11:21 (CET)

Je pense que ce serait bien d'avoir quand même une source pour toutes ces complexités. Le mieux serait un ouvrage de référence, mis en ref au tout début du paragraphe, avec une note disant que tout y est. --Roll-Morton (discuter) 5 novembre 2015 à 11:02 (CET)

"ence"

Je lis "L'algorithme obtenu n'est toutefois pas en place. ence en travaillant sur des listes". Ce n'est pas causé par une modification récente ! domsau2 (discuter) 16 janvier 2022 à 09:02 (CET)

"* Tri par sélection − $T(n)=O(n^{2})$ dans tous les cas ; sur place ; instable par défaut (peut être rendu stable, mais de préférence en travaillant sur des listes)." ? domsau2 (discuter) 16 janvier 2022 à 09:10 (CET)