trie par fusion

trie par fusion - C++ - Programmation

Marsh Posté le 18-11-2002 à 01:31:58    

j'essaye de realiser le trie par fusion mais ce code affiche des valeurs bidons!
pourquoi tout ma pourtant l'air correct?
 

Code :
  1. #include <stdio.h>
  2. #include <stdlib.h>
  4. #define TAILLE 20
  7. void TriFusion(int* t ,int deb,int fin);
  8. void Fusion(int* t,int deb,int fin);
  9. int* RemplirTab(int max);
  10. void print(int* tab)
  11. { int i; for(i=0;i<TAILLE;i++) printf("%d ",tab[i]); }
  13. main()
  14. {
  15.   int* tab;
  16.   int i=0;
  17.  
  18.   tab=RemplirTab(30);
  19.  
  20.   TriFusion(tab,0,TAILLE);
  21.  
  22.   print(tab);
  24. }
  26. void Fusion(int* tab, int deb, int fin)
  27. {
  28.   int milieu=(deb+fin)/2;
  29.   int j,i=0,i1=deb,i2=milieu+1;
  30.   int temp[50];
  31.  
  33.   while(i1<milieu && i2<fin)
  34.     {
  35.       if(tab[i1] < tab[i2])
  36. {
  37.   temp[i]=tab[i1];
  38.   i1++;
  39. }
  40.       else
  41. {
  42.   temp[i]=tab[i2];
  43.   i2++;
  44. }
  45.       i++;
  46.     }
  47.  
  48.   if(i1 < milieu)
  49.     {
  50.       for(j=i1;j<milieu;j++,i++)     
  51.   temp[i]=tab[j];
  52.     }
  54.   else if(i2 < fin)
  55.     {
  56.       for(j=i2;j<fin;j++,i++)
  57.   temp[i]=tab[j];
  58.     }
  60.   for(i=deb;i<fin;i++)
  61.     tab[i]=temp[i];
  63. }
  65. void TriFusion(int* tab, int deb, int fin)
  66. {
  67.   int milieu;
  69.   if(deb<fin)
  70.     {
  71.       milieu=(deb+fin)/2;
  73.       TriFusion(tab,deb,milieu);
  74.       TriFusion(tab,milieu+1,fin);
  75.       Fusion(tab,deb,fin);
  76.     }
  77. }
  79. int* RemplirTab(int max)
  80. {
  81.   int* tab;
  82.   int i;
  84.   tab=(int*)malloc(TAILLE*sizeof(int));
  86.   srand((unsigned)time(NULL));
  87.  
  88.   for(i=0;i<TAILLE;i++)
  89.       tab[i]=rand()%max;   
  91.   return tab;
  92. }


 
les valeurs affichées sont du style '134554347 ... ...'

Reply

Marsh Posté le 18-11-2002 à 01:31:58   

Reply

Marsh Posté le 18-11-2002 à 10:30:28    

les valeurs tordus de ce genre sont en général due à une erreur d'indirection ou d'allocation avec les pointeurs. (g lu le code et j'y comprends rien, mais g souvent des nombres pareils et c du à ca)


---------------
-( BlackGoddess )-
Reply

Marsh Posté le 18-11-2002 à 11:07:25    

salut,
 
j'ai pas la reponse a ta question, par contre prend l'habitude de remplacer tes :
 
(a+b)/2 par (a+b) >> 1 si a et b sont des entiers.
 
Effectivement une division prend de 10 a 30 cycles au microprocesseur et un décalage a droite (qui l'équivalent d'une division par 2) de 1 a 2 cycles (plus les chiffres exactes en tete, mais les ordres de grandeur sont bons)

Reply

Marsh Posté le 18-11-2002 à 11:50:40    

barbarella a écrit a écrit :

par contre prend l'habitude de remplacer tes :
 
(a+b)/2 par (a+b) >> 1 si a et b sont des entiers.




 
Oui, prend l'habitude de faire du code incompréhensible, déjà que le C, c'est facilement le bordel, rajoute en encore.


---------------
brisez les rêves des gens, il en restera toujours quelque chose...  -- laissez moi troller sur discu !
Reply

Marsh Posté le 18-11-2002 à 11:56:12    

kadreg a écrit a écrit :

 
 
Oui, prend l'habitude de faire du code incompréhensible, déjà que le C, c'est facilement le bordel, rajoute en encore.




 
:lol:

Reply

Marsh Posté le 18-11-2002 à 12:29:39    

:( snif! toujours pas de réponse à mon pbm

Reply

Marsh Posté le 18-11-2002 à 22:02:42    

barbarella a écrit a écrit :

salut,
j'ai pas la reponse a ta question, par contre prend l'habitude de remplacer tes :
(a+b)/2 par (a+b) >> 1 si a et b sont des entiers.




 
Il faut surtout prendre l'habitude d'optimiser a la fin! Voire laisser soin au compilo de faire ca tout seul.

Reply

Marsh Posté le 18-11-2002 à 22:03:31    

weblook$ a écrit a écrit :

:( snif! toujours pas de réponse à mon pbm  




Je veux bien jeter un oeil a ton code, mais pourrais tu expliquer en quoi ca consiste le tri par fusion? On m'a déja expliqué mais je ne me souviens plus.

Reply

Marsh Posté le 18-11-2002 à 22:33:37    

barbarella a écrit a écrit :

 
(a+b)/2 par (a+b) >> 1 si a et b sont des entiers.




 
Ca c'était valable il y a quelques années. Les compilateurs modernes savent très bien détecter ces genres de cas. D'ailleurs on peut vérifier ca en activant la sortie assembleur de la compilation (sous Visual C++ c'est Project Settings / C++ / Preprocessor / Listing files je crois).
 
Si tu veux optimiser, apprends a connaitre ton compilateur, Luke !

Reply

Marsh Posté le 18-11-2002 à 23:06:50    

Ace17 a écrit a écrit :

 
 
Il faut surtout prendre l'habitude d'optimiser a la fin! Voire laisser soin au compilo de faire ca tout seul.




 
c'est en rien une optimisation, faur arreter cinq minutes. c'est un opérateur.  
 
Faut pas confondre optimisation et utilisation d'operateur.  

Reply

Marsh Posté le 18-11-2002 à 23:06:50   

Reply

Marsh Posté le 18-11-2002 à 23:08:31    

fabsk a écrit a écrit :

 
 
Ca c'était valable il y a quelques années. Les compilateurs modernes savent très bien détecter ces genres de cas. D'ailleurs on peut vérifier ca en activant la sortie assembleur de la compilation (sous Visual C++ c'est Project Settings / C++ / Preprocessor / Listing files je crois).
 
Si tu veux optimiser, apprends a connaitre ton compilateur, Luke !




 
au lieu de donner des leçons, tu devrais essayé de sortir dans le vaste monde, et te rendre compte qu'il n'y pas que VC :D
 
Et c'est quoi cette aggressivité, j'ai donné un conseil, j'ai rien ordonné du tout, alors venez pas le prendre de haut.

Reply

Marsh Posté le 18-11-2002 à 23:41:16    

barbarella a écrit a écrit :

 
il n'y pas que VC :D




 
J'ai essayé sur le gcc que j'ai au bureau (2.7.2, donc putoujeune), il fait aussi l'optimisation lui-même.


---------------
brisez les rêves des gens, il en restera toujours quelque chose...  -- laissez moi troller sur discu !
Reply

Marsh Posté le 19-11-2002 à 00:11:06    

Juste une remarque, fais gaffe à tes intervalles. Le standard en C c'est que la borne initialle est incluse mais pas la borne de fin. Donc dans ce cas TriFusion deviens :
 

Code :
  1. void TriFusion(int* tab, int deb, int fin)
  2. {
  3. int milieu;
  5. if(deb<fin-1)
  6.    {
  7.      milieu=(deb+fin)/2;
  9.      TriFusion(tab,deb,milieu);
  10.      TriFusion(tab,milieu,fin);
  11.      Fusion(tab,deb,fin);
  12.    }
  13. }

Reply

Marsh Posté le 19-11-2002 à 00:52:52    

bon j'ai pas réussi à trouver l'erreur, mais je suis à peu prés certain qu'un problème d'adressage est en cause.
 
sinon j'ai réussi à faire ce que je voulais en modifiant le code de     Fusion()
 
Pour les intéréssés:

Code :
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  5. typedef char BOOL;
  6. enum{faux,vrai};
  8. int TAILLE;
  11. void TriFusion(int* t ,int deb,int fin);
  12. void Fusion(int* t,int deb,int fin);
  13. int* RemplirTab(int max);
  14. void Permut(int*,int,int);
  15. void print(int* tab,int m,int s,char* mes);
  17. main(int argc,char **argv)
  18. { 
  19.   if(argc>1)    TAILLE=atoi(argv[1]);
  20.   else      {    exit(0);              }
  21.    
  22.   tab=RemplirTab(30);
  24.   print(tab,0,TAILLE-1,"Tab avant traitement: " );
  26.   TriFusion(tab,0,TAILLE-1);
  28.   print(tab,0,TAILLE-1,"Tab aprés traitement: " );
  30. }
  32. void Fusion(int* tab,int deb,int fin)
  33. {
  34.   BOOL continuer;
  35.   int mid=(deb+fin)/2;
  36.   int j,i=mid+1;
  38.   while(i<=fin)
  39.   {
  40.       j=0;
  41.       continuer=vrai;
  42.       while(j<i && continuer)
  43.       {
  44. if( tab[i-j-1] > tab[i-j] )
  45.   Permut(tab,i-j-1,i-j);
  46. else
  47.   continuer=faux;
  48. j++;
  49.       }
  50.       i++;
  51.   }
  52. }
  54. void TriFusion(int* tab, int deb, int fin)
  55. {
  56.   int milieu;
  57.   if(deb<fin)
  58.     {
  59.        milieu=(deb+fin)/2;
  60.      
  61.        if(milieu>deb)
  62.  TriFusion(tab,deb,milieu);
  63.      
  64.        if(milieu+1<fin)
  65.  TriFusion(tab,milieu+1,fin);
  66.      
  67.        Fusion(tab,deb,fin); 
  68.     }
  69. }
  71. void Permut(int* tab,int a,int b)
  72. {
  73.   int temp;
  74.   temp=tab[a];
  75.   tab[a]=tab[b];
  76.   tab[b]=temp;
  77. }
  79. int* RemplirTab(int max)
  80. {
  81.   int* tab;
  82.   int i;
  84.   tab=(int*)malloc(TAILLE*sizeof(int));
  86.   srand((unsigned)time(NULL));
  87.  
  88.   for(i=0;i<TAILLE;i++)
  89.       tab[i]=rand()%(max+1);   
  91.   return tab;
  92. }
  94. void print(int* tab,int m,int s,char* mes)
  95. {
  96.   int i;
  97.   if(strlen(mes)>0)
  98.     printf("%s",mes);
  100.   for(i=m;i<=s;i++)
  101.     printf("%d ",tab[i]);
  102.  
  103.   putchar('\n');
  105. }


Message édité par weblook$ le 19-11-2002 à 00:54:48
Reply

Marsh Posté le 19-11-2002 à 04:16:37    

L'erreur ne viendrait pas du fait que comme il ne respecte pas l'intervalle de son tableau (il faut mettre TriFusion(tab,0,TAILLE-1) dans ton main), il va dans trifusion chercher des valeurs dans des zones memoires bidon et donc du coup va les rapatrier dans son tableau tout beau?


Message édité par Angel_Dooglas le 19-11-2002 à 04:22:12
Reply

Marsh Posté le 19-11-2002 à 04:17:59    

Code :
  1. TriFusion(tab,0,TAILLE); //très probablement TAILLE-1
  3. int temp[50]; //je m'étonne d'une taille fixe...
  5. //ceci...
  6. while(i1<milieu && i2<fin)
  7. {
  8. if(tab[i1] < tab[i2])
  9. {
  10.  temp[i]=tab[i1];
  11.  i1++;
  12. }
  13. else
  14. {
  15.  temp[i]=tab[i2];
  16.  i2++;
  17. }
  18. i++;
  19. }
  20. //...peut s'écrire comme ça.
  21. for(i= 0 ; i1<milieu && i2<fin ; ++i){
  22. int* pi= (tab[i1] < tab[i2]) ? &i1 : &i2 ;
  23. temp[i]= tab[*pi];
  24. (*pi)++;
  25. }


 
J'ai eu la flemme de vérifier l'alorithme... désolé.
 

Citation :

(a+b)/2 par (a+b) >> 1 si a et b sont des entiers.

A condition que ce soient (1)des entiers (2)positifs représentés en (3)base 2 en (4)numération arabe.
 
Il faut coder l'opération qu'on veut faire, et laisser au compilateur ce genre d'optimisation.


---------------
Bricocheap: Montage de ventilo sur paté de mastic silicone
Reply

Marsh Posté le 19-11-2002 à 06:58:33    

barbarella a écrit a écrit :

salut,
 
j'ai pas la reponse a ta question, par contre prend l'habitude de remplacer tes :
 
(a+b)/2 par (a+b) >> 1 si a et b sont des entiers.
 
Effectivement une division prend de 10 a 30 cycles au microprocesseur et un décalage a droite (qui l'équivalent d'une division par 2) de 1 a 2 cycles (plus les chiffres exactes en tete, mais les ordres de grandeur sont bons)  




 
Le compilateur fait ca vraiment tres bien tout seul tu sais.
 
Remplacer /2 par >>1 , n'importe quel compilo bidon peux le faire.
 
Par contre, si tu veux produire du code incomprehensible, oui, fais comme ca.
 


---------------
L'ingénieur chipset nortiaux : Une iFricandelle svp ! "Spa du pâté, hin!" ©®Janfynette | "La plus grosse collec vivante de bans abusifs sur pattes" | OCCT v12 OUT !
Reply

Marsh Posté le 19-11-2002 à 09:44:00    

Ai déja essayé mesurer différences de rapidité avec BC 3 sous Windows 3.11 sur mon 486/100MHz, car on voit mieux au chrono :D.
 
Multipl/divis par 2^n ou décalages, pas vu la moindre différence de rapidité. J'ai donc opté pour lecture facile.

Reply

Marsh Posté le 20-11-2002 à 23:56:28    

ouf enfin c'est trouvé  :)
c'était tout simplement des erreurs d'indice dans la fonction Fusion :sarcastic:

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed