Page 1 sur 1
Tri à bulles
Publié : mar. nov. 19, 2013 2:33 am
par maurice
Bonjour,
je suis en train de préparer une cativité sur le tri à bulles en 1S.
Pour cela, j'ai testé la procédure Xcas de Guillaume conan dans son recueil libre d'algorithmes auquel j'ai ajouté le variables locales :
Code : Tout sélectionner
bulle(L):={
local LT, compteur, k, temp;
LT:=L;
compteur:=0;
pour k de 0 jusque size(LT)-1 faire
si LT[k]>LT[k+1] alors
temp:=LT[k];
LT[k]:=LT[k+1];
LT[k+1]:=temp;
k:=k-1;
compteur:=compteur+1;
fsi;
fpour;
retourne(LT,compteur);
}:;
Lorsque je le teste j'ai un message d'erreur :
puis :
j'obtiens :
"Index hors limite : 3, vector size is 3, syntax compatibility mode xcas
Erreur: Dimension incorrecte"
mais je ne vois pas pourquoi la dimension serait trop grande ...
merci de votre aide
maurice
Re: Tri à bulles
Publié : mar. nov. 19, 2013 5:49 am
par alb
salut,
c'est size(LT)-1 qui ne va pas.
meme en enlevant le k:=k-1 et en mettant size(LT)-2 le resultat de bulle(L) est [2,1,3]
Je propose:
Code : Tout sélectionner
Trier(L):={
local res,s,j,k,temp;
res:=L;
s:=size(L);
pour j de 0 jusque s-2 faire
pour k de j+1 jusque s-1 faire
si res[j]>res[k] alors
temp:=res[j];
res[j]:=res[k];
res[k]:=temp;
fsi;
fpour;
fpour;
retourne res;
}
:;
Re: Tri à bulles
Publié : mar. nov. 19, 2013 1:24 pm
par maurice
Bonjour, merci pour la réponse.
En réalité dans la version de Guillaume Connan, il n'y avais pas k:=k+1 mais k:=-1.
Du coup, en changeant le size(LT)-1 en size(LT)-2, ça marche.
Code : Tout sélectionner
bulle(L):={
local LT, compteur, k, temp;
LT:=L;
compteur:=0;
pour k de 0 jusque size(LT)-2
faire
si LT[k]>LT[k+1] alors
temp:=LT[k];
LT[k]:=LT[k+1];
LT[k+1]:=temp;
k:=-1;
compteur:=compteur+1;
fsi;
fpour;
retourne(LT,compteur);
}:;
retourne :
Code : Tout sélectionner
([2,3,4,5,6,7,8,9,11,87],13)
Merci pour votre aide.
Maurice
Re: Tri à bulles
Publié : mar. nov. 19, 2013 4:05 pm
par alb
exact, je n'ai pas vu l'astuce pour ramener k à 0.
Un truc interessant avec les eleves: L:=....;debug(bulle(L));
Re: Tri à bulles
Publié : mar. nov. 19, 2013 4:58 pm
par alb
Comparaison des fonctions bulle et Trier.
Code : Tout sélectionner
bulle(L):={
local LT, compteur, k, temp;
LT:=L;
compteur:=0;
pour k de 0 jusque size(LT)-2 faire
si LT[k]>LT[k+1] alors
temp:=LT[k];
LT[k]:=LT[k+1];
LT[k+1]:=temp;
k:=-1;
compteur:=compteur+1;
fsi;
fpour;
retourne(LT,compteur);
}:;
Trier(L):={
local res,s,j,k,temp,c;
res:=L;
s:=size(L);
c:=0;
pour j de 0 jusque s-2 faire
pour k de j+1 jusque s-1 faire
si res[j]>res[k] alors
temp:=res[j];
res[j]:=res[k];
res[k]:=temp;
c:=c+1;
fsi;
fpour;
fpour;
retourne res,c;
}
:;
L:=seq(k,k,500,0,-1);
Trier(L); // en 6.24 s, compteur: 125250
bulle(L); // en 175.43 s, compteur: 125250
L:=randvector(300,'alea(300)');
Trier(L); // par ex en 0.82 s, compteur: 16176
bulle(L); // en 26.08 s, compteur: 23125
Re: Tri à bulles
Publié : mar. nov. 19, 2013 6:55 pm
par maurice
Bonsoir,
Merci pour les infos, les comparaisons sont effectivement intéressantes.
J'arrive à la fin de mon activité à ça :
Code : Tout sélectionner
echange(L,j,k):={
local temp;
temp:=L[j];
L[j]:=L[k];
L[k]:=temp;
return L;
}:;
bulle(L):={
local LT, j, k;
LT:=L;
pour j de 0 jusque size(LT)-1 faire
pour k de 0 jusque size(LT)-2 faire
si LT[k+1] < LT[k] alors
LT:=echange(LT,k,k+1)
fsi;
fpour;
fpour;
return LT;
}:;
Qui est moins performant que le votre mais que l'on peut perfectionner après coup avec les élèves.
Je voulais comparer avec la fonction sort d'Xcas mais, si elle est bien sur bien plus rapide, le temps de calcul ne s'affiche pas.
Y'a-t-il un moyen de l'aqfficher.
Cordialement.
maurice
Re: Tri à bulles
Publié : mar. nov. 19, 2013 8:18 pm
par alb
oui, time(sort(L))
On peut aller plus vite en utilisant l'affectation par reference =< (voir paragraphe 8.4.11 et suivants du manuel de reference)
Code : Tout sélectionner
TrierRef(L):={
local res,s,j,k,temp,c;
res:=copy(L);
s:=size(L);
c:=0;
pour j de 0 jusque s-2 faire
pour k de j+1 jusque s-1 faire
si res[j]>res[k] alors
temp=<res[j];
res[j]=<res[k];
res[k]=<temp;
c:=c+1;
fsi;
fpour;
fpour;
retourne res,c;
}
:;
L:=randvector(1000,'alea(1000)');
TrierRef(L); // environ 5s
time(sort(L)); // voir explication
ici