• API
• FAQ
• Tools
• Archive
daily pastebin goal
73%
SHARE
TWEET

# mergesortdewikipedia :p

alduncin Feb 2nd, 2012 77 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top