Tri à bulles

[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 :

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]

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]

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]

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

[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

[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

[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