2009/07/09 14:15

머지소트(merge sort) 구현

개발환경
Gentoo Linux 2.6.20-r8
gcc 4.1.2

  1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #include<time.h>
5
6 void make_data(int *, int);
7 void print_arr(int *, int);
8 void my_merge_sort(int *, int, int);
9 void my_merge(int *, int, int);
10
11 int main(int argc, char **argv)
12 {
13 int n;
14 int *arr;
15 srand((unsigned int)time(NULL));
16 printf("How many data you want to make? ");
17 scanf("%d", &n);
18
19 if( n < 0 || n > 100)
20 {
21 return 0;
22 }
23 arr = (int *)malloc(sizeof(int)*n);
24 make_data(arr, n);
25
26 printf("before merge sort\n");
27 print_arr(arr, n);
28 my_merge_sort(arr, 0, n-1);
29
30 printf("after merge sort\n");
31 print_arr(arr, n);
32 free(arr);
33 return 0;
34 }
35
36 void make_data(int *arr, int n)
37 {
38 int i;
39 for(i = 0 ; i != n ; i++)
40 {
41 *(arr+i) = rand() % 100;
42 }
43 }
44
45 void print_arr(int *arr, int n)
46 {
47 int i;
48 for(i = 0 ; i != n ; i++)
49 {
50 printf("%d\t", *(arr+i));
51 }
52 printf("\n");
53 }
54 void my_merge_sort(int *arr, int start, int end)
55 {
56 if(start < end)
57 {
58 my_merge_sort( (arr+start), 0, (end-start)/2);
59 my_merge_sort( (arr+start), (end-start)/2+1, end-start);
60 my_merge( (arr+start), 0, end-start);
61 }
62
63 }
64
65 void my_merge(int *arr, int start, int end)
66 {
67 int i, j, k;
68 int *temp;
69 temp = (int *)malloc(sizeof(int)*(end-start+1));
70
71 i = 0;
72 j = start;
73 k = end/2 +1;
74 while( j <= end/2 && k <= end)
75 {
76 if( *(arr+j) < *(arr+k) )
77 {
78 *(temp+i) = *(arr+j);
79 i++;
80 j++;
81 }
82 else
83 {
84 *(temp+i) = *(arr+k);
85 i++;
86 k++;
87 }
88 }
89
90 for( ; i <= end-start ; i++)
91 {
92 if( j > end/2 )
93 {
94 *(temp+i) = *(arr+k);
95 k++;
96 }
97 else
98 {
99 *(temp+i) = *(arr+j);
100 j++;
101 }
102 }
103 memcpy(arr, temp, sizeof(int)*(end - start + 1));
104 free(temp);
105 }



출처 - http://exsuperstar.net -
저작자 표시 비영리 동일 조건 변경 허락
Trackback 1 Comment 0


티스토리 툴바