Program/st.cpp at master · DongYuYu/Program · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <stdio.h>
#include<stdlib.h>
#include<time.h>


//int *temp= (int *)malloc(sizeof(int)*(10));

void merge(int *a,int L,int m,int R){

//if (m==8) printf("runs here\n");
int *temp= (int *)malloc(sizeof(int)*(R-L+1));

//int temp[R-L+1]={0};
//printf("merge%d, %d\n", L, R);
int *temp1 = a+L;

int *temp2 = a+m+1;

for (int i=L; i<=R; i++){

if (temp1>a+m){ temp[i-L]=*temp2;    //temp1 runs out of bound
//printf("temp[%d]:%d\n", i, temp[i-L]);
                temp2 ++;}
else if (temp2>a+R) {temp[i-L]=*temp1;
//printf("temp[%d]:%d\n", i, temp[i-L]);
                    temp1++;}

else if ( *temp1>=*temp2) {

     temp[i-L]=*temp2;
     temp2+=1;

  //   printf("temp[%d]:%d\n", i, temp[i-L]);
     }
else{

     temp[i-L]=*temp1;
     temp1+=1;
    // printf("temp[%d]:%d\n", i, temp[i-L]);

     }

}

for (int i=L;i<=R;i++)
a[i]=temp[i-L];

//printf("helfdone%d %d\n",L,R);
free(temp);
//system("pause");


//printf("Done%d %d\n", L,R);
}

void mergesort(int * a, int L, int R){
//printf("mergesort %d, %d\n", L,R);
if (L==R) return;
int m = (L+R)/2;
mergesort (a, L, m);
mergesort (a, m+1, R);
merge(a,L,m,R);
return ;


}


int main (){

    int n= 23;
  //  int a[]={1,3,5,7,9,23,5,0,12,13};
      //  int a[]={1,3,5,7,9,23,5};
    srand(time(0));
    int a[n];

    for (int i =0; i<n; i++)
    a[i]=rand()%230;


    for (int i=0; i<n;i++)
    printf("%d\n",a[i]);
         system("pause");
    mergesort(a,0,n-1);

    for (int i=0; i<n;i++)
    printf("%d\n",a[i]);

    system("pause");


}