Tri à bulles

Discussion sur l'enseignement de l'algorithmique avec Xcas au lycee
maurice
Messages : 50
Inscription : jeu. déc. 10, 2009 6:48 pm

Tri à bulles

Message par maurice » mar. nov. 19, 2013 2:33 am

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 :

Code : Tout sélectionner

L:=[3,2,1]
puis :

Code : Tout sélectionner

bulle(L)
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

alb
Messages : 1320
Inscription : ven. août 28, 2009 3:34 pm

Re: Tri à bulles

Message par alb » mar. nov. 19, 2013 5:49 am

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;
}
:;

maurice
Messages : 50
Inscription : jeu. déc. 10, 2009 6:48 pm

Re: Tri à bulles

Message par maurice » mar. nov. 19, 2013 1:24 pm

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);
}:;

Code : Tout sélectionner

L:=[4,8,2,7,6,3,5,9,87,11]
bulle(L)
retourne :

Code : Tout sélectionner

([2,3,4,5,6,7,8,9,11,87],13)
Merci pour votre aide.

Maurice

alb
Messages : 1320
Inscription : ven. août 28, 2009 3:34 pm

Re: Tri à bulles

Message par alb » mar. nov. 19, 2013 4:05 pm

exact, je n'ai pas vu l'astuce pour ramener k à 0.
Un truc interessant avec les eleves: L:=....;debug(bulle(L));

alb
Messages : 1320
Inscription : ven. août 28, 2009 3:34 pm

Re: Tri à bulles

Message par alb » mar. nov. 19, 2013 4:58 pm

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

maurice
Messages : 50
Inscription : jeu. déc. 10, 2009 6:48 pm

Re: Tri à bulles

Message par maurice » mar. nov. 19, 2013 6:55 pm

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

alb
Messages : 1320
Inscription : ven. août 28, 2009 3:34 pm

Re: Tri à bulles

Message par alb » mar. nov. 19, 2013 8:18 pm

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

Répondre