Je sais que la politique ne veut pas que l'on fasse les exercices des autres ...
Mais j'ai ici 3 questions dont je ne trouve réponse ... malgré que je sache comment fonctionne quicksort ...
Je devrais être capable de répondre par oui ou par non et d'expliquer les questions suivantes :
1. A cause des inégalités strictes des étapes suivantes :
(11) WHILE t[i].clé < cléRef DO INC(i) END;
(12) WHILE t[j].clé > cléRef DO DEC(j) END;
l'étape suivante:
(13) IF i <= j THEN tamp := t[i]; t[i] := t[j]; t[j] := tamp; INC(i); DEC(j) END
fais parfois traverser une clé égale à la clé de référence.
2. Le déplacement d’une clé égale à la clé de référence est inutile au tri.
3. Donc la version de QuickSort obtenue en transformant (11) et (12) en :
(11’) WHILE t[i].clé <= cléRef DO INC(i) END;
(12’) WHILE t[j].clé >= cléRef DO DEC(j) END;
est fonctionnelle et meilleure que la version de Hoare !
J'ai fais des recherches sur internet. En vain ...
Si vous connaissez un site qui puisse m'apporter des réponses à ces questions ou que vous êtes en mesure de m'aider .... merci ...
Partager