Merge – Sort

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