Connaisance de Quicksort ..

Version imprimable

13/08/2009, 15h17
haribooo

Connaisance de Quicksort ..

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 ...
13/08/2009, 22h18
Invité

Pour Quicksort et les améliorations qu'on peut lui apporter, une très bonne référence est le livre de Sedgewick sur les algorithmes.

Le problème de ton approche, si on l'applique telle quelle dans l'algorithme classique, c'est que les deux pointeurs peuvent se croiser (suppose par exemple que ton fichier à trier ne contienne que des clefs égales...).

Du coup, il va falloir ajouter une condition dans la boucle de recherche de pivot, qui va nettement ralentir l'algorithme (la vitesse de cette boucle est un des facteurs déterminants la rapidité de l'algorithme)...

Tu pourrais néanmoins utiliser une inégalité stricte et une inégalité ou égalité dans ta boucle, ceci éviterait certains échanges, mais je crois que dans ce cas, tu risques de créer un biais, qui va produire des "coupes" moins équilibrées par pivot. Là encore, si on a des clefs égales, ca risque de ralentir le programme... (il faudrait faire les calculs)

Maintenant, il existe des versions de quicksort qui prennent en compte les clef égales (en les stockant en début ou en fin de fichier, et en les remettant au milieu après chaque étape). Tu perds du temps dans cette gestion, toutes les valeurs égales au pivot sont éliminées des boucles suivantes (ça peut faire beaucoup...) Elles sont effectivement plus efficaces que le quicksort classique si on a peu de valeurs, mais elles sont plus lentes dans les autres cas...

Quicksort est un algorithme bizzare. De petits changements de sa structure peuvent changer nettement ses performances. Dans ce genre de situation, il est très important d'effectuer des tests, sur des données pas du tout au hasard (les vraies données qu'on trie ne le sont jamais)...

Francois
14/08/2009, 11h28
pseudocode
Citation:

Envoyé par haribooo

1. l'étape suivante (...) fais parfois traverser une clé égale à la clé de référence.

oui.

Citation:

2. Le déplacement d’une clé égale à la clé de référence est inutile au tri.

sauf si c'est la référence elle même !

Tableau de 7 valeurs, la référence est 8:
{1,2,3,[8],7,5,9}

Algo de Hoare => échange de 8 et 5:
Code:

1 2 {1,2,3,[8],4,5,9} i-------^ ^--j
Cet échange est nécessaire pour que le tableau soit partitionné correctement.

Citation:

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 !

Question sans objet vu la réponse a la question 2 :P
14/08/2009, 14h16
haribooo

Citation:

Envoyé par pseudocode

oui.

J'étais arrivé à la même conclusion. Je ne comprends juste pas pourquoi ?
Comment expliquer ca ? ...
14/08/2009, 14h57
haribooo
Citation:

sauf si c'est la référence elle même !

Donc, on ne bougera pas un élément si il est égal à la clé ?

Imaginons ce tableau :

{2;4;6;2;9;6;7} ..

Si nous prenons comme référence le premier élément comme clé ...
Commençons donc à partir de la droite à la recherche d'un élément plus petit ou égal ... Une fois tombé sur le "2", devons nous le déplacé ?
Parce que ensuite le "4" prendra l'ancienne place du "2", et le "2" que nous avions placé en clé de référence, prendra l'ancienne place du 4.

.... Mon raisonement est-il faux ? Doit-on ignoré le 2 en passant dessus ? ...

Parce que d'après ces deux lignes
Code:

1 2 3 WHILE t[i].clé <= cléRef DO INC(i) END; WHILE t[j].clé >= cléRef DO DEC(j) END;
Nous devons considérer les égalités, ou suis-je completement à coté de la plaque ?

concernant le point "3" posté dans mon premier poste ...
Je pense qu'elle est plus fonctionnelle et meilleure, non ? D'après ce que je viens d'avancer ...
14/08/2009, 15h22
pseudocode
Citation:

Envoyé par haribooo

Donc, on ne bougera pas un élément si il est égal à la clé ?

Au contraire : il faut toujours bouger la clé de référence, sinon le partitionnement peut devenir faux !

Citation:

Imaginons ce tableau :

{2;4;6;2;9;6;7} ..

Si nous prenons comme référence le premier élément comme clé ...
Commençons donc à partir de la droite à la recherche d'un élément plus petit ou égal ... Une fois tombé sur le "2", devons nous le déplacé ?
Parce que ensuite le "4" prendra l'ancienne place du "2", et le "2" que nous avions placé en clé de référence, prendra l'ancienne place du 4.

.... Mon raisonement est-il faux ? Doit-on ignoré le 2 en passant dessus ? ...

Dans l'algo de Hoare, le premier échange sera "2" (position 1 = la référence) avec "2" (position 4).
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 initial: {[2],4,6,2,9,6,7} {[2],4,6,2,9,6,7} i-^ ^------j swap 2 <-> 2 {[2],4,6,2,9,6,7} i----^----------j split {2} {4,6,2,9,6,7}
Citation:
Parce que d'après ces deux lignes

Code:

1 2 3 WHILE t[i].clé <= cléRef DO INC(i) END; WHILE t[j].clé >= cléRef DO DEC(j) END;

Nous devons considérer les égalités, ou suis-je completement à coté de la plaque ?
L'algo avec les égalités est faux. Déjà il risque de provoquer des dépassements de tableau. Mais surtout, il faut absolument bouger la référence afin que le partitionnement soit correcte : c'est à dire que la partition basse ne contienne que des éléments inferieurs-ou-égaux à la référence, et que la partition haute ne contienne que des éléments supérieurs-ou-egaux à la référence.