daily pastebin goal
20%
SHARE
TWEET

mergesortdewikipedia :p

alduncin Feb 2nd, 2012 76 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*# split in half
  2. m = n / 2
  3.  
  4. # recursive sorts
  5. sort a[1..m]
  6. sort a[m+1..n]
  7.  
  8. # merge sorted sub-arrays using temp array
  9. b = copy of a[1..m]
  10.   i = 1, j = m+1, k = 1
  11.   while i <= m and j <= n,
  12.   a[k++] = (a[j] < b[i]) ? a[j++] : b[i++]
  13.     → invariant: a[1..k] in final position
  14.     while i <= m,
  15.     a[k++] = b[i++]
  16.   → invariant: a[1..k] in final position
  17. */
  18. /*main (int argc,char **)
  19. {
  20.   int lo= 10, m=7, hi=19;
  21.   int i, j, k;
  22.    // copy both halves of a to auxiliary array b
  23.   for (i=lo; i<=hi; i++)
  24.     b[i]=a[i];
  25.  
  26.   i=lo; j=m+1; k=lo;
  27.   // copy back next-greatest element at each time
  28.   while (i<=m && j<=hi)
  29.     if (b[i]<=b[j])
  30.       a[k++]=b[i++];
  31.     else
  32.       a[k++]=b[j++];
  33.  
  34.   // copy back remaining elements of first half (if any)
  35.   while (i<=m)
  36.     a[k++]=b[i++];
  37. }
  38. main (int argc,char **)
  39. {
  40.   int a[],b[];
  41.   merge(10,5,19);
  42.  
  43.   }*/
  44.   void mezclar(int arreglo1[], int n1, int arreglo2[], int n2, int arreglo3[])
  45.   {
  46.     int x1=0, x2=0, x3=0;
  47.  
  48.     while (x1<n1 && x2<n2) {
  49.       if (arreglo1[x1]<arreglo2[x2]) {
  50.         arreglo3[x3] = arreglo1[x1];
  51.         x1++;
  52.       } else {
  53.         arreglo3[x3] = arreglo2[x2];
  54.         x2++;
  55.       }
  56.       x3++;
  57.     }
  58.     while (x1<n1) {
  59.       arreglo3[x3] = arreglo1[x1];
  60.       x1++;
  61.       x3++;
  62.     }
  63.     while (x2<n2) {
  64.       arreglo3[x3] = arreglo2[x2];
  65.       x2++;
  66.       x3++;
  67.     }
  68.   }
  69.  
  70. void mezcla(int vector[], int n)
  71. {
  72.   int *vector1, *vector2, n1, n2,x,y;
  73.   if (n>1)
  74.     {
  75.       if (n%2 == 0)
  76.         n1=n2=(int) n / 2;
  77.       else
  78.         {
  79.           n1=(int) n / 2;n2=n1+1;
  80.         }
  81.       vector1=(int *) malloc(sizeof(int)*n1);
  82.       vector2=(int *) malloc(sizeof(int)*n2);
  83.       for(x=0;x<n1;x++)
  84.         vector1[x]=vector[x];
  85.       for(y=0;y<n2;x++,y++)
  86.         vector2[y]=vector[x];
  87.       mezcla(vector1, n1);
  88.       mezcla(vector2,n2);
  89.       mezclar(vector1, n1, vector2, n2, vector);
  90.       free(vector1);
  91.       free(vector2);
  92.     }      
  93. }
  94.  
  95. int main(){
  96.   int i, vector[] = {2,3,5,7,2,6,1,5,8,3,2};
  97.  
  98.   mezcla(vector,12);
  99.  
  100.   for(i=0;i<12;i++)
  101.     printf("%i,\n", vector[i]);
  102.  
  103.   return 0;
  104. }
RAW Paste Data
Top