Chalvantzis Konstantinos

1: Merge - Sort

   2:  #include <stdio.h>

   3:  #include <stdlib.h>

   4:  

   5:  void Merge (int c[], // Phgh : 2 taksinomhmena tmhmata etoima gia sygxoneush

   6:              int d[], // Pinakas proorismou

   7:              int L,   // Arxh tou 1ou tmhmatos

   8:              int M,   // Telos tou 1ou tmhmatos

   9:          int R,   // Telos tou 2ou tmhmatos

  10:          int *plithos); //metritis gia to plithos sigrisewn

  11:  void MergePass (int x[], // Phgh : me zeygaria apo taksinomhmena tmhmata

  12:                  int y[], // Pinakas proorismou

  13:                  int s,   // Megethos tmhmatos

  14:          int n,   // Synoliko megethos tou x[] kai tou y[]

  15:          int *plithos); //metritis gia to plithos sigrisewn

  16:  void MergeSort (int a[], //Pinakas gia taksinomisi

  17:          int b[],   //bohthitikos pinakas

  18:          int n,   // Arithmos stoixeiwn ston a[]

  19:          int *plithos); //metritis gia to plithos sigrisewn

  20:  

  21:  int main()main()()

  22:  {

  23:   int plithos;

  24:   int max;

  25:   int i;

  26:   int *x;

  27:   int *z;

  28:   printf(“dose to megethos toy pinaka:”);

  29:   scanf(“%d”,&max);

  30:   x=(int*)malloc(max*sizeof(int));

  31:   i=0;

  32:   while(i<max)

  33:    {

  34:     printf(“\nDwse ena x%d arithmo:  “,i);

  35:     scanf(“%d”,&x[i]);

  36:     i++;

  37:     }

  38:   i=0;

  39:   printf(“\nOi arithmoi tou X pinaka einai:\n”);

  40:   while(i<max)

  41:    {

  42:     printf(“%d,”,x[i]);

  43:     i++;

  44:     }

  45:   i=0;

  46:   plithos=0;

  47:   MergeSort(x,z,max,&plithos);

  48:   i=0;

  49:   printf(“\nO neos Z pinakas einai:\n”);

  50:   while(i<max)

  51:    {

  52:     printf(“%d,”,x[i]);

  53:     i++;

  54:     }

  55:   printf(“\nto plithos ton sygkriseon pou eginan einai: %d”,plithos);

  56:   return 0;

  57:  }

  58:  

  59:  

  60:  //Sugxoneuei ta: c[L:M] , c[M+1:R] sto d[L:R]

  61:  void Merge (int c[], // Phgh : 2 taksinomhmena tmhmata etoima gia sygxoneush

  62:              int d[], // Pinakas proorismou

  63:              int L,   // Arxh tou 1ou tmhmatos

  64:              int M,   // Telos tou 1ou tmhmatos

  65:          int R,   // Telos tou 2ou tmhmatos

  66:          int *plithos) //metritis gia to plithos sigrisewn

  67:  {

  68:     int i = L,        // deikths gia to 1o tmhma

  69:         j = M+1,      // deikths gia to 2o

  70:         k = L;        // deikths gia to apotelesma

  71:  

  72:  // sygxoneuei mexri to i h to j ginoun megalutera ap’to megethos twn adistoixwn tmhmatwn

  73:     while ( (i <= M) && (j <= R) )

  74:       {

  75:        (*plithos)++;

  76:        if (c[i] <= c[j])  d[k++] = c[i++];

  77:        else               d[k++] = c[j++];

  78:        }

  79:  

  80:  // analambanei ta ypoloipa stoixeia

  81:     while ( i <= M )

  82:        d[k++] = c[i++];

  83:     while ( j <= R )

  84:        d[k++] = c[j++];

  85:  }

  86:  

  87:  //Sygxoneuei taksinomimena tmhmata megethous ’s’.

  88:  void MergePass (int x[], // Phgh : me zeygaria apo taksinomhmena tmhmata

  89:                  int y[], // Pinakas proorismou

  90:                  int s,   // Megethos tmhmatos

  91:          int n,   // Synoliko megethos tou x[] kai tou y[]

  92:          int *plithos) //metritis gia to plithos sigrisewn

  93:  {

  94:          int i=0; // Arxikos deikths gia ta tmhmata pou epeksergazontai

  95:                  int j;

  96:  

  97:  // xeirizetai ola ta zeygaria twn tmhmatwn plhrous-megethous

  98:     while (i <= n - 2 * s)

  99:     {

 100:  //  Sygxoneuei 2 taksinomhmena tmhmata megethous ’s’

 101:        Merge (x, y, i, i+s-1, i+2*s-1,plithos);

 102:        i = i + 2*s;

 103:     }

 104:  //ligotera apo 2s stoixeia menoun

 105:     if (i + s < n)

 106:        Merge (x, y, i, i+s-1, n-1,plithos);

 107:     else

 108:        for ( j = i; j <= n-1; j++)

 109:           y[j] = x[j];   //antigrafei to teleytaio tmhma sto y

 110:  }

 111:  // Taksinomei ton pinaka a[0:n-1] .

 112:  void MergeSort (int a[], //Pinakas gia taksinomisi

 113:          int b[],   //bohthitikos pinakas

 114:          int n,   // Arithmos stoixeiwn ston a[]

 115:          int *plithos) //metritis gia to plithos sigrisewn

 116:  {

 117:     int s = 1;            // megethos tmhmatos

 118:     while (s < n)

 119:     {

 120:        MergePass (a, b, s, n,plithos); // sygxoneuei apo ton a[] ston b[]

 121:        s += s;                 // diplasiazei to megethos tou tmhmatos

 122:        MergePass (b, a, s, n,plithos); // sygxoneuei apo ton b[] ston a[]

 123:        s += s;                 // ksanadiplasiazei to megethos tou tmhmatos

 124:     }

 125:  }