Le principe est assez original et donne de bons résultats sur les listes très désordonnées. Par contre, sur une liste presque déjà triée, il faudra trouver autre chose…
à mettre en conclusion plutôt qu'en intro je pense.
Et puis une petite note vers "Réflexion sur la complexité algorithmique chapitre 1" renforcerait l'intégration à zds.
Dans l'implémentation en Ocaml, la dernière ligne peut être remplacée par (qsort debut) @ (pivot::(qsort fin). Utiliser le constructeur est mieux que l'opérateur de concaténation à mon avis.
EDIT : et le cours de bluestorm sur la récursivité existe aussi ici, donc le lien peut être changé.
Aujourd'hui, nous allons apprendre une méthode de tri : le tri rapide, aussi appelé QSort (QuickSort = tri rapide en anglais). C'est un algorithme de tri assez utilisé, et voilà l'occasion d'en apprendre plus à son sujet !
Afin de suivre ce cours, la connaissance du C est nécessaire. Un exemple d'implémentation sera également fait en Ocaml.
Dans l'implémentation en Ocaml, la dernière ligne peut être remplacée par (qsort debut) @ (pivot::(qsort fin). Utiliser le constructeur est mieux que l'opérateur de concaténation à mon avis.
L'explication peut rester la même. Ce qui change c'est qu'au lieu de concaténer un élément à une liste avec pivot @ (qsort fin) on crée une liste qui a pour tête l'élément pivot et pour queue la liste qsort fin. Donc, on peut écrire « et enfin, on met bout à bout debut, le pivot, et fin, en appelant qsort sur debut et fin avant ».
Salut, c'est encore moi pour une petite remarque : même si supprimer les données sur le graphique de la courbe de $n\log{n}$ part d'une bonne intention, je trouve qu'il faut au contraire les mettre, car sinon, je peux arriver avec un tri en $O(n^2)$ et donner une courbe de $n^2$ qui semble croître moins vite car j'aurais supprimé les nombres et changé l'échelle des abscisses.
Petit à petit il se fait remplacer par des tris avec une meilleure garantie de complexité dans les autres langages que le C où sa lib standard continue à le proposer. P.ex., en C++, introsort a pris la place du quicksort dans la STL – Je ne sais plus quel algo est employé aujourd'hui. Python a introduit TimSort.
Ce serait bien de mettre l'intro au « niveau d'accessibilité » que l'on cherche à développer depuis quelques temps. A minima, une description précise des prérequis et des objectifs. Plus spécifiquement, quand vous dites « une nouvelle sorte de tri », je me doute que vous faites référence à ce cours, à celui-ci et à celui-là, mais ça, votre lecteur ne le sait pas nécessairement. Bref, étoffer un peu cette intro ne peut pas lui faire de mal.
Le principe
cet algorithme a un principe un peu original si vous êtes habitués au tri à bulles ou au tri par sélection
Ça confirme qu'il faut étoffer l'intro concernant les prérequis.
bluestorm a écrit un tutoriel sur la récursivité
Vous pouvez remplacer l'URL par celle de la version sur ZdS. Accessoirement, je mettrais l'info en note plutôt qu'entre parenthèses.
toutes les valeurs qui lui sont inférieures sont à sa gauche
« inférieures ou égales ». Vu que vous le précisez plus haut, autant rester cohérents.
Passons à la pratique !
rien à OCaml, voyez par là
Idem, lien vers la version ZdS.
QSort simple en OCaml
C'est sans doute une question de goût, mais je trouve que le code serait beaucoup plus clair en Haskell.
Ça doit faire référence à la mise en forme sur OC, mais en l'état, ce n'est pas très compréhensible.
Orthotypo
Apostrophes typographiques, comme d'hab, quoi.
QuickSort = tri rapide en anglais
Guillemets autour de « tri rapide ».
sur une liste presque déjà triée
Je trouve que « déjà presque triée » sonnerait mieux.
Le principe
Bon, alors cet algorithme
Virgule après « alors ».
La réponse est très simple : quand il n'y a plus rien à trier (c'est-à-dire, quand les sous-tableaux restants sont soit des singletons, soit vides).
Pas besoin des parenthèses : une simple virgule après « tirer » serait stylistiquement meilleure. Par ailleurs, le lien wikipédia va boguer, il faudrait le remplacer par « http://fr.wikipedia.org/wiki/Singleton_(mathématiques) »
Un petit exemple ?
Ça fait bizarre d'avoir un titre 3 qui se ballade tout seul, comme ça…
Prenons cette liste :
les valeurs qui ne sont pas à leur place :
deux sous-listes restantes, on obtient donc ceci :
Un point à la place du deux-points.
1
2
3
21 5 37 42 38
-------------
<37|| >37
1
2
3
21 5 37 42 38
-------------
<37 || >37
Pour la phrase juste en dessous, l'italique est de trop. Vous pouvez utiliser la fonction « légende » du bloc de code, ou simplement en faire un paragraphe ordinaire. Dans le premier cas, ça donnerait ça.
1
2
3
21 5 37 42 38
-------------
<37 || >37
Ici, on voit la liste initiale séparée en deux : au milieu le pivot, 37. À gauche, les valeurs inférieures à 37 (<37) ont été insérées. De même à droite pour les valeurs supérieures à 37 (>37).
Y'a visiblement quelque chose qui a merdouillé à l'import (et idem pour le bloc de code suivant) mais je ne parviens pas à déterminer exactement ce que vous vouliez faire. Même remarque que ci-dessus sur l'italique des « légendes ».
Passons à la pratique !
QSort simple en OCaml
Une autre implémentation, en C
Encore un fois, les titres 2 qui se baladent sans titre 1, ça fait bizarre.
le 1er élément de la liste
premier
trois paramètres, comme ceci :
Que vous pouvez appeler comme dans cet exemple :
Un point à la place du deux-points.
(c'est-à-dire des numéros de cases)
Même remarque que plus haut sur l'absence de besoin de parenthèses.
Déjà, comme pour la version Caml
OCaml
Merci à shareman pour ses améliorations sur ce code.
Le mettre en note passerait mieux que l'italique.
Rapide… À quel point ?
Pire cas possible
Meilleur cas possible
Au final…
Les titres, toujours…
Supposons que l'on veuille ranger :
« ranger la liste qui suit avec notre algorithme. ». Et donc supprimer « avec notre algorithme » de la ligne suivante.
puis on effectue la partition :
Rebelote en ignorant le 1 et le 10 :
on divise donc le tableau en deux :
Un point à la place du deux-points.
a été permutée avec le 2
permuté
Cette idée se généralise très facilement à des tableaux de longueur N : quickSort fera N + (N - 1) + (N - 2) + … + 3 + 2 + 1 tests, et N permutations. En calculant la somme N + (N - 1) + (N - 2) + … + 3 + 2 + 1, on trouve qu'elle est égale à N*(N+1)/2, soit grossièrement N². Ainsi, si vous doublez la taille du tableau, dans le pire des cas, le temps d'exécution quadruplera.
Utiliser MathJax pourrait donner un rendu légèrement meilleur. À vous de voir.
Juste une petite remarque qui relève du détails : « Au final… » n'existe pas en français. On préfèrera « En définitive… » ou encore « Finalement… ». Plus d'informations : http://www.academie-francaise.fr/au-final
Sinon le tutoriel est très intéressant, j'aime bien le premier graphique de Wikipédia avec l'animation, ça permet de vraiment bien comprendre comment fonctionne cet algo.
Connectez-vous pour pouvoir poster un message.
Connexion
Pas encore membre ?
Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte
. 
