[Logique] Erreur dans le syllabus ?

Voir le sujet précédent Voir le sujet suivant Aller en bas

resolu [Logique] Erreur dans le syllabus ?

Message  mourad1081 le Ven 20 Mai 2016, 12:55

Bonjour à tous,

Je voulais réviser mon algorithmie, notamment le quick sort, et donc j'ai relu la partie consacrée à cela dans le syllabus de logique (chapitre sur la récursivité, p. 49). Je ne sais pas s'il a été mis à jour depuis ma BA2 (2013-2014) mais je viens de m'apercevoir qu'une erreur de logique s'y est glissée dans le code présenté :

Code:

module quicksortRécursif (tab↓↑ : tableau[1 à n] de T, bInf↓, bSup↓ : entiers)
    gauche, droite, pivot : entiers
    si bInf < bSup alors
        pivot ← tab[(bInf + bSup) DIV 2]
        gauche ← bInf
        droite ← bSup
        répéter
            tant que tab[gauche] < pivot faire
                gauche ← gauche + 1
            fin tant que
            tant que tab[droite] > pivot faire
                droite ← droite – 1
            fin tant que
            si gauche < droite alors
                swap(tab[gauche], tab[droite]) // échange des deux éléments
            fin si
        jusqu’à ce que gauche ≥ droite
        quicksortRécursif(tab, bInf, gauche – 1)
        quicksortRécursif(tab, droite + 1, bSup)
    fin si
fin module

En effet, d'après ce code, si la valeur l'élément courant à droite = l'élément courant à gauche = la valeur du pivot, alors il y a une boucle infinie et l'algorithme ne se termine jamais.

Je vais réfléchir à un correctif si cela n'a pas encore été fait

Edit : Le fait de forcer l'incrément et le décrément de gauche et droite après le swap règle le soucis Smile
Donc, rajouter ceci juste après le swap.
Code:

droite ← droite - 1
gauche ← gauche + 1

mourad1081

Nombre de messages : 65
Prénom : Mourad
Date d'inscription : 02/03/2013

Revenir en haut Aller en bas

resolu Re: [Logique] Erreur dans le syllabus ?

Message  pbt le Mer 25 Mai 2016, 10:15

Merci pour le retour, qd je croise un prof d'algo, je lui dis.

_________________
smartq.namok.be · faq ·  · IRC / irc.freenode.net #esi · blog.namok.be
style #pbt {heigth:189cm; weight:79kg; eye-color:#524000; hair:very short; dead pixels: some; }

pbt
Admin

Nombre de messages : 4862
Age : 45
Prénom : Pierre
Statut : prof
Localisation : La cité des géants
Date d'inscription : 24/11/2005

http://esi.namok.be

Revenir en haut Aller en bas

resolu Re: [Logique] Erreur dans le syllabus ?

Message  mourad1081 le Mer 25 Mai 2016, 10:27

Avec plaisir Smile

mourad1081

Nombre de messages : 65
Prénom : Mourad
Date d'inscription : 02/03/2013

Revenir en haut Aller en bas

resolu Re: [Logique] Erreur dans le syllabus ?

Message  Contenu sponsorisé Aujourd'hui à 18:57


Contenu sponsorisé


Revenir en haut Aller en bas

Voir le sujet précédent Voir le sujet suivant Revenir en haut


 
Permission de ce forum:
Vous ne pouvez pas répondre aux sujets dans ce forum