tri

[Nath]

je suis quasi novice en programmation.

j'aimerais comprendre le tri rapide.

j'ai essayé ça :


partition(A,p,r):={
local x,k,j;
x:=A[r-1];
k:=p-1;
pour j de p jusque r-1 faire
si A[j-1]<=x alors k:=k+1;(A[k-1],A[j-1]):=(A[j-1],A[k-1]);fsi;
fpour;
(A[k],A[r-1]):=(A[r-1],A[k]);
return (k+1,A);
}:;


trirapide(A,p,r):=
{local q,b;
si p<r alors
b:=partition(A,p,r);
q:=b[0];
A:=b[1];
trirapide(A,p,q-1);trirapide(A,q+1,r);
fsi;
return A;
}:;

puis trirapide([2,8,7,1,3,5,6,4],1,8) ...

si quelqu'un peut m'indiquer où sont mes erreurs, merci d'avance.

[parisse]

Pouvez-vous expliquer ce que devraient faire chacune de vos routines? Sinon, je vous conseille d'executer la commande
debug(trirapide([2,8,7,1,3,5,6,4],1,8))
qui vous permettra en cliquant sur le bouton sst (ou touche F5) d'executer le programme ligne par ligne en voyant évoluer la valeur des variables locales. Utiliser plutot le bouton in (raccourci F6) pour entrer dans une fonction (un appel récursif par exemple).

[Nath]

j'ai pris les algo présentés dans Cormen, rivest, stein pour le tri rapide-

c'est dans les remontées des appels récursifs que je ne maitrise pas ce qu'il se passe.

Si je passe A en "global" comme ci-dessous :

partition(A,p,r):={
local x,k,j;
x:=A[r-1];
k:=p-1;
pour j de p jusque r-1 faire
si A[j-1]<=x alors k:=k+1;(A[k-1],A[j-1]):=(A[j-1],A[k-1]);fsi;
fpour;
(A[k],A[r-1]):=(A[r-1],A[k]);
return (k+1,A);
}:;


trirapide(p,r):=
{local q,b;
si p<r alors
b:=partition(A,p,r);
q:=b[0];
A:=b[1];
trirapide(p,q-1);trirapide(q+1,r);
fsi;
return;
}:;



puis exécution avec :

A:=[2,3,0,23,35,89,-1];trirapide(1,dim(A));A

A est bien triée dans l'ordre croissant comme voulu.

[parisse]

ok, le probleme c'est que dans l'appel recursif, trirapide modifie une copie de A, pas sur l'original, il faudrait faire A:=trirapide(...) pour que A soit modifie dans la fonction appelante. En fait une copie de A est generee des qu'on utilise := avec A a gauche (ce qui du reste empechera d'avoir un tri rapide puisque la copie prendra un temps proportionnel a dim(A)). Il faudrait utiliser l'affectation en place avec l'operateur =< pour eviter ca (mais ca ne marchera pas avec la syntaxe (A[k],A[r-1]):=(A[r-1],A[k]) il faudra faire les 2 separement avec une variable temporaire). Le langage de Xcas n'est pas vraiment concu pour ca (et de toutes facons il faudrait un langage compile pour avoir une performance satisfaisante), il ne pourra servir que dans un but pedagogique pour montrer le deroulement de l'algorithme, en mettant en garde sur la question des copies de liste lors d'une affectation par :=.

[Nath]

merci

la version suivante :

partition(A,p,r):={
local x,k,j,tmp;
x:=A[r-1];
k:=p-1;
pour j de p jusque r-1 faire
si A[j-1]<=x alors k:=k+1;tmp=<A[k-1];A[k-1]=<A[j-1];A[j-1]=<tmp;fsi;
fpour;
tmp=<A[k];A[k]=<A[r-1]; A[r-1]=<tmp;
return (k+1,A);
}:;


trirapide(A,p,r):=
{local q,b;
si p<r alors
b:=partition(A,p,r);
q:=b[0];
A:=b[1];
A=<trirapide(A,p,q-1);A=<trirapide(A,q+1,r);
fsi;
return A;
}:;


fonctionne.

Où peux-t-on trouver de la doc sur les différences entre := et =< ?

[parisse]

Où peux-t-on trouver de la doc sur les différences entre := et =< ?

Dans le menu Aide, rechercher un mot, saisissez affectation, puis selectionnez le 2eme item Les affectations infixees. Voir aussi plus loin le tri fusion.