Le tri rapide : QSort

a marqué ce sujet comme résolu.
Auteur du sujet

Bonjour à tous,

J'ai commencé (il y a 5 jours, 23 heures) la rédaction d'un tutoriel dont l'intitulé est Le tri rapide : QSort.

J'aimerais obtenir un maximum de retour sur celui-ci, sur le fond ainsi que sur la forme, afin de proposer en validation un texte de qualité.

Si vous êtes intéressé, cliquez ci-dessous

Merci d'avance pour votre aide

Ce tutoriel est importé d'OC. Il est soumis à la vindicte populaire pour savoir si une publication sur Zeste est possible ;) .

Édité par Thunderseb

Responsable de la validation - TodoFox - Le JavaScript, c’est bon, mais pas jQuery ! Séries

+0 -0

Cette réponse a aidé l’auteur du sujet

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.

+0 -0

Cette réponse a aidé l’auteur du sujet

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

Édité par Karnaj

Assez des salamis, je passe au jambon — Je fais un carnage si ce car nage car je nage, moi, Karnaj ! — Le comble pour un professeur de mathématique ? Mourir dans l’exercice de ses fonctions.

+0 -0

Cette réponse a aidé l’auteur du sujet

Introduction

Salut à tous !

Salut !

et donne de bons résultats sur les listes très désordonnées.

Ca fait un peu bizarre de lire ça, parce que tu n'as pas dit qu'il s'agissait d'un tri sur des listes. ^^

Au passage, peut-être serait-il intéressant de parler plutôt de séquence, vu la distinction qu'on opère en OCaml entre liste et tableau ?

Dans tous les cas, je vous propose de découvrir cet algorithme sans plus tarder !

Peut-être quand même pas avant d'avoir indiqué les pré-requis (et, pourquoi pas, les objectifs de ce tuto) ? ^^

"Bienheureux celui qui sait rire de lui-même, il n’a pas fini de s’amuser." Joseph Folliet

+0 -0
Auteur du sujet

Màj de l'intro :


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.

Karnaj

J'ai modifié. Au niveau de son explication quant à cette dernière ligne, il y a un truc à modifier ? (je pige rien à Ocaml moi) :

  • et enfin, on met bout à bout (c'est l'opérateur @) debut, le pivot, et fin, en appelant qsort sur debut et fin avant.

Édité par Thunderseb

Responsable de la validation - TodoFox - Le JavaScript, c’est bon, mais pas jQuery ! Séries

+0 -0

Cette réponse a aidé l’auteur du sujet

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

Assez des salamis, je passe au jambon — Je fais un carnage si ce car nage car je nage, moi, Karnaj ! — Le comble pour un professeur de mathématique ? Mourir dans l’exercice de ses fonctions.

+0 -0

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.

Assez des salamis, je passe au jambon — Je fais un carnage si ce car nage car je nage, moi, Karnaj ! — Le comble pour un professeur de mathématique ? Mourir dans l’exercice de ses fonctions.

+0 -0

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.

+0 -0

Voici mes quelques remarques.

Intro

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.

1
2
3
4
5
6
qsort []  = []
qsort [x] = [x]
qsort (pivot:reste) = (qsort pluspetit) ++ [pivot] ++ (qsort plusgrand)
    where
        pluspetit = filter (<= pivot) reste
        plusgrand = filter (>  pivot) reste

Rapide… À quel point ?

… un tableau tout coloré

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

1
2
215* 37 *42 38----------------------------
<21 || >21 ****** <42 || >42

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.

Cette fois-ci, les valeurs à trier sont :

« sont les suivantes. ».

… un tableau tout coloré
… un tableau trié.

Pas d'espace après les points de suspension.

#JeSuisGrimur #OnVautMieuxQueÇa

+0 -0

Salut,

Je viens prendre des nouvelles du tutoriel. Il est toujours d’actualité ? En validation ?

Assez des salamis, je passe au jambon — Je fais un carnage si ce car nage car je nage, moi, Karnaj ! — Le comble pour un professeur de mathématique ? Mourir dans l’exercice de ses fonctions.

+0 -0

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.

"I think that it’s extraordinarily important that we in computer science keep fun in computing." — Alan J. Perlis

+2 -0
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