Discussion:Tri rapide

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

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)

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

j'ai essayé d'exprimer cela un peu moins maladroitement. Est-ce un progrès ? Bluestorm (d) 25 mars 2008 à 23:10 (CET)

Complexité bis bis

La meilleure implémentation utilise un choix de pivot aléatoire, la complexité moyenne est toujours O(nlgn) mais la probabilité du pire des cas O(n2) est 1/n! soit infinitésimal. Il en est de même si on permute aléatoirement les données avant de les trier. L'importance n'est pas le pire des cas, mais la distribution de probabilité de la fonction de complexité. --Nipou (d) 8 août 2008 à 17:08 (CEST)

tout à fait, la complexité dans la pire des cas n'a d'intérêt que dans le cas de système temps réels. - phe 9 août 2008 à 09:36 (CEST)

Non, la complexité dans le pire des cas n'a d'intérêt qu'avec une mauvaise implémentation de quicksort, c'est-à-dire, autre chose que randomize-quicksort. --Nipou (d) 9 août 2008 à 11:11 (CEST)

Equivalent C Sharp

(Loloof64) => J'ai rajouté les modifications à éffectuer pour traduire le code en C Sharp, dans la section Java.

En C# les tableaux ne sont-ils pas intrinséquement passés par référence ? et non en valeur. D'où le fait que mot clé "ref" soit inutil.--Azgaroth (d) 4 décembre 2009 à 10:43 (CET)

Implémentation en Pascal

Bonjour, j'ai recopié l'implémentation en Pascal affichée, je l'ai testée et visiblement, elle ne fonctionne pas : un programme générant un tableau aléatoire, puis triant ce tableau grâce à l'algorithme (recopié tel quel, en vérifiant bien entendu la correspondance entre les types), puis vérifiant que le tableau est bien trié montre que cela ne marche pas.

Je ne maitrise pas bien cet algorithme, si quelqu'un de plus calé que moi peut vérifier la bonne marche du code...

Nouvelle version

Bonjour,

J'ai déjà pas mal modifié l'article ces derniers jours, mais je voudrais faire un remaniement plus global. J'ai préparé une nouvelle version sur Utilisateur:Nordald/Tri rapide. Pouvez-vous me dire si ça vous va ou pas ?

J'ai essayé de suivre l'organisation suivante :

• D'abord décrire une version efficace de l'algorithme de façon la plus simple possible. Actuellement, il y a déjà plein de remarques sur le choix du pivot, avant la partie qui est censé en parler.
• Ensuite, donner les différentes méthodes pour choisir le pivot, et parler de la complexité (ça semble assez indissociable). La version actuelle insiste beaucoup sur les problèmes posés par le choix du premier élément comme pivot, je pense qu'il suffit de le dire une fois. De toute façon, le choix aléatoire du pivot résout le problème.
• Enfin, regrouper dans la dernière partie toutes les variantes liées à des points moins fondamentaux (espace mémoire, optimisation en dessous d'une taille donnée, etc)

Dans la version actuelle, je n'ai pas conservé les remarques sur les DoS / overflow possibles, à mon avis ce n'est pas significatif.

• Ça n'arrive qu'avec une mauvaise implémentation.
• Il n'y a pas de source comme quoi cela a réellement posé un problème en pratique un jour.

et puis le premier résultat dans Google sur "quicksort buffer overflow" est un poisson d'avril...

J'ai aussi enlevé les références à la version dérécursifiée. Le fait que la mémoire soit utilisée de façon plus prévisible et indépendante des données et du code me semble douteux. À ma connaissance, tout ce qu'on peut faire, c'est utiliser une pile plutôt que des appels récursifs, c'est une technique générale mais je ne vois pas en quoi ça augmenterait la prévisibilité.

Cordialement,

Nordald (d) 26 avril 2010 à 21:57 (CEST)

Salut, je trouve ton organisation assez pertinente. Seul les $\Theta$ me perturbent, je croyais que cette notation avait juste été inventée pour embêter les étudiants :p Zandr4^[Kupopo ?] 26 avril 2010 à 22:21 (CEST)

En relisant, c'est même complètement mélangé pour l'instant, il y a des O et des $\Theta$ en vrac. Je vais mettre des des O, théoriquement c'est moins précis, mais si tu penses que c'est plus compréhensible, c'est l'essentiel. Nordald (d) 26 avril 2010 à 22:48 (CEST)

La remarque de Zandr4 sur les O et les Θ me semble un peu obscurantiste. Θ est une notion bien définie, claire et pertinente, ici en particulier c'est plus précis, donc plus informatif, tout en restant clair, sauf pour ceux qui font preuve de paresse intellectuelle. A mon avis il suffit mettre un lien bleu vers notation de Landau, où l'on trouve la définition. Je suis plutôt contre les compromis avec l'ignorance, lorsqu'ils se font au détriment de la précision, en particulier dans une encyclopédie, et en particulier lorsque le bénéfice au niveau de la clarté est très discutable.--Chassaing 27 avril 2010 à 15:20 (CEST)

Hola, le terme obscurantiste est complètement inapproprié. Je n'ai rien contre les Θ, vu que c'est une notion claire, définie, pertinente, précise, informative et que sais-je encore. Je fais juste remarquer que je ne connais personne/nulle part qui utilise/où est utilisée cette notation. Rien à voir avec de la paresse ou l'amour de l'ignorance, simplement l'habitude de respecter les conventions, dès lors que le travail produit est destiné à autrui et en plus de nature à amener plusieurs personnes à travailler dessus.

Je n'ai jamais vu nulle part écrit le tri rapide est en O(n^12), bien que ce soit vrai. Implicitement, la notation O tient souvent lieu de Θ. Après, je serais tout à fait satisfait du fait que les tendances évoluent vers l'utilisation du Θ, plus précis. Mais, c'est peut être ce qui se produit déjà, et peut être que je ne m'en suis pas encore rendu compte ;) Zandr4^[Kupopo ?] 27 avril 2010 à 16:48 (CEST)

Personnellement, je n'utilise que rarement la notation Θ et j'ai tendance à employer O à la place. Il me semblait que c'était ce qu'il y avait dans Introduction à l'algorithmique de Cormen/Leiserson/Rivest/Stein, mais après vérification ils mettent des Θ. De même sur la Wikipédia anglaise. En fait, je n'ai pas trouvé de référence où il y un O(n log n) : dans les autres, soit le nombre de comparaison est calculé précisément, soit il y a une phrase "est proportionnel à n log n".
Donc je propose de repasser aux Θ, en wikifiant le premier, sauf dans l'introduction où je mettrais une formule du type "est proportionnel à" pour que ça reste directement compréhensible. Est-ce que ça va comme ça ? Nordald (d) 27 avril 2010 à 20:53 (CEST)

Pour ma part, ça me va très bien. Par ailleurs, le terme « obscurantiste » s'applique (peut-être de manière inapproppriée, je m'en excuse) uniquement à la remarque (pas à la personne). Je travaille occasionnellement avec des informaticiens spécialistes d'analyse d'algorithmes qui font couramment usage de la notation de Landau avec virtuosité (cf Flajolet et Sedgewick), mais peut-être ne sont-ils pas représentatifs. Cela dit, une encyclopédie a valeur éducative, donc il n'y a pas de mal à accompagner une évolution vers plus de précision.--Chassaing 27 avril 2010 à 22:08 (CEST)

Un autre point auquel je n'avais pas pensé est la difficulté à produire le caractère Θ. Cela a pu contribuer à cet abus de O... Bref, du moment que l'on reste cohérent, tout va bien.Zandr4^[Kupopo ?] 27 avril 2010 à 23:28 (CEST)

Incohérence ?

À force de récursions… Il est dit dans cette page : « Une variante du tri rapide devenue largement utilisée est introsort alias introspective sort. Elle démarre avec un tri rapide puis utilise un tri par tas lorsque la profondeur de récursivité dépasse une certaine limite prédéfinie. »

Et dans la page sur le tri par tas : « A la fin du tri par tas, pour les 15 derniers éléments environ, l'algorithme effectue plusieurs fois de suite les mêmes inversions, ce qui est inutile. On peut à la place arrêter l'algorithme quand il n'y a plus beaucoup d'éléments et passer à un autre. Les données qui restent sont à peu près triées à l'envers. On peut donc, par exemple : effectuer un tri rapide sur les données restantes »

En gros, on peut améliorer un tri rapide en finissant par un tri par tas et vice-versa. J'ai mal compris ou c'est louche ? — Le message qui précède, non signé, a été déposé par Orena Radrax (discuter), le 16 mai 2010 à 16:55

Bonjour. À mon avis, la remarque dans l'article tri par tas était injustifiée. Je l'ai supprimée. L'idée, c'est que le tri rapide est plus rapide que le tri par tas en moyenne mais plus lent dans le pire cas. En mettant du tri par tas dans le tri rapide, Introsort améliore le pire cas sans trop changer le cas moyen. Par contre, il n'y a pas d'intérêt à finir le tri par tas avec un tri rapide. Cordialement, Nordald (d) 16 mai 2010 à 19:10 (CEST)

Commentaire du lecteur : il y a une petite er...

83.145.122.242 a publié ce commentaire le 4 octobre 2013 (voir tous les retours).

il y a une petite erreur dans votre algorithme

échanger T[pivot] et T[dernier] n'est pas possible car pivot n'est pas un indice de tableau

merci quand meme

Avez-vous des remarques à formuler ?

Litlok (m'écrire) 2 mars 2014 à 23:41 (CET)

Source pour Introsort

Le fait que ce tri est largement utilisé a des sources potentiels: Code source std::sort de gcc