home *** CD-ROM | disk | FTP | other *** search
/ ftp.disi.unige.it / 2015-02-11.ftp.disi.unige.it.tar / ftp.disi.unige.it / pub / .person / CataniaB / teach-act / esempi / Ordinamenti / merge.c next >
C/C++ Source or Header  |  1997-05-15  |  1KB  |  73 lines
  1. /* Mergesort: ordinamento ricorsivo di un array. 
  2.  */
  3.  
  4. #include <stdio.h>
  5. #define MAX 20
  6.  
  7. void merge(int a[],int inf,int med, int sup)
  8. /* fondo i due pezzi ordinati dell'array a [inf-med e med+1-sup]
  9.  * mantenendo il tutto ordinato. 
  10.  */
  11.  
  12. { int b[MAX];
  13.   int i,j,k,m;
  14.  
  15.   i=inf; 
  16.   j=med+1;
  17.   k=inf;
  18.  
  19.   while ((i<=med) && (j<=sup))
  20.    if (a[i]<a[j])  b[k++]=a[i++];
  21.    else            b[k++]=a[j++];  
  22.  
  23.   if   (i<=med) 
  24.     for(m=i;  m<=med; m++) b[k++]=a[m];
  25.   for(m=inf; m<k;  m++) a[m]=b[m];
  26. }
  27.  
  28. void msort (int a[],int inf,int sup)
  29.  {
  30.   int med,i,temp;
  31.   
  32.   if (inf < sup) 
  33.    {
  34.      med=(inf+sup)/2;  /* con troncamento */
  35.      temp=med+1;
  36.    
  37.      msort(a,inf,med);      /* ordino la prima meta inf-med */
  38.      printf("\n Ho ordinato da %d a %d",inf,med);
  39.      for(i=inf;i<=med;i++) printf(" %d",a[i]);   
  40.    
  41.      msort(a,temp,sup);    /* ordino la seconda meta med+1-sup */
  42.      printf("\n Ho ordinato da %d a %d",temp,sup); 
  43.      for(i=temp;i<=sup;i++) printf(" %d",a[i]);
  44.      printf("\n");
  45.      merge(a,inf,med,sup);  /* fondo le due parti */
  46.    } 
  47.  }
  48.  
  49.  
  50. /* esempio di chiamata */
  51.  
  52. void main(void)
  53. { int a[MAX];
  54.   int i,n;
  55.  
  56.   printf("Dimensione?[Max:20]"); 
  57.   scanf("%d",&n);
  58.   if (n>MAX) printf("\n Dimensione > %d",MAX);
  59.   else 
  60.   {
  61.     printf("Input?\n");
  62.     for(i=0;i<n;i++) scanf("%d",&a[i]);
  63.  
  64.     printf("Echo\n");
  65.     for(i=0;i<n;i++) printf(" %d",a[i]);
  66.  
  67.     msort(a,0,n-1);
  68.  
  69.     printf("\nOutput\n");
  70.     for(i=0;i<n;i++) printf(" %d",a[i]);
  71.   }
  72. }
  73.