/*********************************************************   TD d'Algorithmique IN202    
ENSTA   
    
  Mardi 7 Novembre 2000   
    
  Exercices 1,2,3,6 et 7 : Tri a bulle et Tri fusion   
      
                                        Guillaume Poupard  
*********************************************************/   
#include <stdio.h>  
#include <stdlib.h>   
#include <time.h>  
   
/* Tri a bulle  
   Complexite=somme pour i allant de P+1 a r de i-p   
             =n(n-1)/2  
   dans tous les cas (independant du tableau a trier)*/   
     
int Tri_Bulle(int *A, int p, int r)   
  
{   
  int i,j,t;  
  int c=0;   
    
  for(i=r;i>p;i--)   
    for(j=p+1;j<=i;j++)  
      {   
        c++;  
        if (A[j-1]>A[j])   
          {  
            t=A[j-1];   
            A[j-1]=A[j];  
            A[j]=t;   
          }  
      }   
  return c;  
}   
  
   
/* Tri fusion  
   Complexite de Fusionner=r-p+1   
   Complexite=n*log2(n)=n*k pour n=2^k*/  
   
int Fusionner(int *A, int p, int q, int r)  
   
{  
  int * B;   
  int i,j,k;  
  int c=0;   
    
  B=(int *)malloc((r+1)*sizeof(int));   
    
  for(i=p;i<=q;i++)   
    B[i]=A[i];  
  for(j=q+1;j<=r;j++)   
    B[r+q+1-j]=A[j];  
  i=p;   
  j=r;  
  for(k=p;k<=r;k++)   
    {  
      c++;   
      if (B[i]<B[j])  
        {   
          A[k]=B[i];  
          i=i+1;   
        }  
      else   
        {  
          A[k]=B[j];   
          j=j-1;  
        }   
    }  
  free(B);   
  return c;  
}   
  
  
int Tri_Fusion(int *A, int p, int r)  
   
{  
  int q;   
    
  if (p<r)   
    {  
      int n1,n2,n3;   
        
      q=(p+r)/2;   
      n1=Tri_Fusion(A,p,q);  
      n2=Tri_Fusion(A,q+1,r);   
      n3=Fusionner(A,p,q,r);  
      return n1+n2+n3;   
    }  
  return 0;   
}  
   
void printtab(int *A, int p, int r)  
{   
  int i; 
  for(i=p;i<=r;i++)  
    printf("%d ",A[i]); 
  printf("\n");  
} 
  
void inittab(int *A, int p, int r) 
{  
  int i; 
  for(i=p;i<=r;i++)  
    A[i]=lrand48() % 100; 
}  
 
int main(int argc, char * argv[])  
{ 
  int n=atoi(argv[1]);  
  int *A; 
  time_t seed;  
  int c; 
  
  A=(int *)malloc(n*sizeof(int)); 
  
  time(&seed); 
  srand48(seed);  
 
  printf("Tri a bulle:\n");  
  inittab(A,0,n-1); 
  printtab(A,0,n-1);  
  c=Tri_Bulle(A,0,n-1); 
  printtab(A,0,n-1);  
  printf("Complexite=%d\n",c); 
  
  printf("\nTri fusion:\n"); 
  inittab(A,0,n-1);  
  printtab(A,0,n-1); 
  c=Tri_Fusion(A,0,n-1);  
  printtab(A,0,n-1); 
  printf("Complexite=%d\n",c);  
 
  exit(0);  
}