質問編集履歴
2
プログラムを変更
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -106,6 +106,144 @@
|
|
|
106
106
|
|
|
107
107
|
}
|
|
108
108
|
|
|
109
|
+
プログラム追記マージソート
|
|
110
|
+
|
|
111
|
+
#include <stdio.h>
|
|
112
|
+
|
|
113
|
+
#define N 10
|
|
114
|
+
|
|
115
|
+
|
|
116
|
+
|
|
117
|
+
void merge(int *A, int nA, int *B, int nB, int i, int *C)
|
|
118
|
+
|
|
119
|
+
/* 整列配列A[0],...,A[nA-1]とB[0],...,B[nB-1]を併合し整列配列
|
|
120
|
+
|
|
121
|
+
C[i],...,C[i+nA+nB-1]に入れる */
|
|
122
|
+
|
|
123
|
+
{
|
|
124
|
+
|
|
125
|
+
int iA, iB, iC; /* iAはAの添字、iBはBの添字、iCは合計 */
|
|
126
|
+
|
|
127
|
+
|
|
128
|
+
|
|
129
|
+
iA=iB=iC=0; /* 併合の開始 */
|
|
130
|
+
|
|
131
|
+
while(iC <= nA+nB-1)
|
|
132
|
+
|
|
133
|
+
{
|
|
134
|
+
|
|
135
|
+
if(iA>=nA) {C[i+iC]=B[iB]; iB=iB+1;} /* Aは既に空 */
|
|
136
|
+
|
|
137
|
+
else
|
|
138
|
+
|
|
139
|
+
{
|
|
140
|
+
|
|
141
|
+
if(iB>=nB) {C[i+iC]=A[iA]; iA=iA+1;} /* Bは既に空 */
|
|
142
|
+
|
|
143
|
+
else /* A[iA]とB[iB]の小さい方をCへ移す */
|
|
144
|
+
|
|
145
|
+
{
|
|
146
|
+
|
|
147
|
+
if(A[iA]<=B[iB]) {C[i+iC]=A[iA]; iA=iA+1;}
|
|
148
|
+
|
|
149
|
+
else {C[i+iC]=B[iB]; iB=iB+1;}
|
|
150
|
+
|
|
151
|
+
}
|
|
152
|
+
|
|
153
|
+
}
|
|
154
|
+
|
|
155
|
+
iC=iC+1;
|
|
156
|
+
|
|
157
|
+
}
|
|
158
|
+
|
|
159
|
+
return;
|
|
160
|
+
|
|
161
|
+
}
|
|
162
|
+
|
|
163
|
+
|
|
164
|
+
|
|
165
|
+
|
|
166
|
+
|
|
167
|
+
void mergesort(int *A, int i, int j)
|
|
168
|
+
|
|
169
|
+
/* 配列A[i],...,A[j]をマージソートにより整列 */
|
|
170
|
+
|
|
171
|
+
{
|
|
172
|
+
|
|
173
|
+
int k, n, n1, n2, mid;
|
|
174
|
+
|
|
175
|
+
int A1[N], A2[N];
|
|
176
|
+
|
|
177
|
+
|
|
178
|
+
|
|
179
|
+
n=j-i+1; /* 配列のサイズ */
|
|
180
|
+
|
|
181
|
+
if(n>1)
|
|
182
|
+
|
|
183
|
+
{
|
|
184
|
+
|
|
185
|
+
mid=i+(n-1)/2; /* 中央値により前後の部分配列へ分割 */
|
|
186
|
+
|
|
187
|
+
mergesort(A, i, mid); /* 前半の整列 */
|
|
188
|
+
|
|
189
|
+
mergesort(A, mid+1, j); /* 後半の整列 */
|
|
190
|
+
|
|
191
|
+
n1=mid-i+1;
|
|
192
|
+
|
|
193
|
+
for(k=i; k<=mid; k++) A1[k-i]=A[k]; /* A1は前半の部分配列 */
|
|
194
|
+
|
|
195
|
+
n2=j-mid;
|
|
196
|
+
|
|
197
|
+
for(k=mid+1; k<=j; k++) A2[k-mid-1]=A[k]; /* A2は後半の部分配列 */
|
|
198
|
+
|
|
199
|
+
merge(A1, n1, A2, n2, i, A); /* A1とA2の併合 */
|
|
200
|
+
|
|
201
|
+
}
|
|
202
|
+
|
|
203
|
+
return;
|
|
204
|
+
|
|
205
|
+
}
|
|
206
|
+
|
|
207
|
+
|
|
208
|
+
|
|
209
|
+
|
|
210
|
+
|
|
211
|
+
|
|
212
|
+
|
|
213
|
+
|
|
214
|
+
|
|
215
|
+
int main (void) {
|
|
216
|
+
|
|
217
|
+
int array[N] = { 2, 1, 8, 5, 4, 7, 9, 0, 6, 3 };
|
|
218
|
+
|
|
219
|
+
int i;
|
|
220
|
+
|
|
221
|
+
|
|
222
|
+
|
|
223
|
+
printf("print array \n");
|
|
224
|
+
|
|
225
|
+
for (i = 0; i < N; i++) { printf("%d ", array[i]); }
|
|
226
|
+
|
|
227
|
+
printf("\n");
|
|
228
|
+
|
|
229
|
+
|
|
230
|
+
|
|
231
|
+
mergesort(array, 0, N);
|
|
232
|
+
|
|
233
|
+
|
|
234
|
+
|
|
235
|
+
printf("print array \n");
|
|
236
|
+
|
|
237
|
+
for (i = 0; i < N; i++) { printf("%d ", array[i]); }
|
|
238
|
+
|
|
239
|
+
printf("\n");
|
|
240
|
+
|
|
241
|
+
|
|
242
|
+
|
|
243
|
+
return 0;
|
|
244
|
+
|
|
245
|
+
}
|
|
246
|
+
|
|
109
247
|
```
|
|
110
248
|
|
|
111
249
|
mergeSortedDataByCatheの部分には部分的に並べ替えられたdata配列についてcacheを用いて昇順にマージソートする
|
1
プログラムを変更
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -12,7 +12,15 @@
|
|
|
12
12
|
|
|
13
13
|
void mergeSortedDataByCathe(int *data,int *cache,int first,int last,int half){
|
|
14
14
|
|
|
15
|
-
|
|
15
|
+
int i,j,k;
|
|
16
|
+
|
|
17
|
+
for(i = first; i < half; i++) cache[i] = data[i];
|
|
18
|
+
|
|
19
|
+
for (j = last; i < last; i++) cache[i] = data[--j];
|
|
20
|
+
|
|
21
|
+
for (i--, j = first, k = first; k < last; k++)
|
|
22
|
+
|
|
23
|
+
data[k] = cache[j] < cache[i] ? cache[j++] : cache[i--];
|
|
16
24
|
|
|
17
25
|
}
|
|
18
26
|
|
|
@@ -24,7 +32,7 @@
|
|
|
24
32
|
|
|
25
33
|
|
|
26
34
|
|
|
27
|
-
if(first=
|
|
35
|
+
if(last-first<=1) return;
|
|
28
36
|
|
|
29
37
|
half=(first+last)/2;
|
|
30
38
|
|
|
@@ -32,7 +40,7 @@
|
|
|
32
40
|
|
|
33
41
|
mergeSort(data,cache,half,last);
|
|
34
42
|
|
|
35
|
-
mergeSortedDataByCathe(data,cache,first,last,half);
|
|
43
|
+
mergeSortedDataByCathe(data,cache,first,last,half);
|
|
36
44
|
|
|
37
45
|
}
|
|
38
46
|
|
|
@@ -46,25 +54,25 @@
|
|
|
46
54
|
|
|
47
55
|
if(argc!=3){
|
|
48
56
|
|
|
49
|
-
fprintf(stderr,"Usage: %s <maxsize> <filename>\n",argv[0]);
|
|
57
|
+
fprintf(stderr,"Usage: %s <maxsize> <filename>\n",argv[0]);
|
|
50
58
|
|
|
51
59
|
return 1;
|
|
52
60
|
|
|
53
61
|
}
|
|
54
62
|
|
|
63
|
+
|
|
64
|
+
|
|
55
65
|
maxsize=atoi(argv[1]);
|
|
56
|
-
|
|
57
|
-
printf("argc=%d",argc);
|
|
58
66
|
|
|
59
67
|
if((fp=fopen(argv[2],"r"))==NULL){
|
|
60
68
|
|
|
61
|
-
fprintf(stderr,"File %s is not found\n",argv[
|
|
69
|
+
fprintf(stderr,"File %s is not found\n",argv[2]);//標準エラー出力(printfと動きは同じ)
|
|
62
70
|
|
|
63
71
|
return 1;
|
|
64
72
|
|
|
65
73
|
}
|
|
66
74
|
|
|
67
|
-
if((data=
|
|
75
|
+
if((data=(int*)calloc(maxsize,sizeof(int)))==NULL){
|
|
68
76
|
|
|
69
77
|
fprintf(stderr,"Out of memory\n");
|
|
70
78
|
|
|
@@ -72,7 +80,7 @@
|
|
|
72
80
|
|
|
73
81
|
}
|
|
74
82
|
|
|
75
|
-
if((cache=
|
|
83
|
+
if((cache=(int*)calloc(maxsize,sizeof(int)))==NULL){
|
|
76
84
|
|
|
77
85
|
fprintf(stderr,"Out of memory\n");
|
|
78
86
|
|
|
@@ -86,7 +94,7 @@
|
|
|
86
94
|
|
|
87
95
|
}
|
|
88
96
|
|
|
89
|
-
|
|
97
|
+
mergeSort(data,cache,0,count);
|
|
90
98
|
|
|
91
99
|
for(i=0;i<count;i++){
|
|
92
100
|
|
|
@@ -109,3 +117,5 @@
|
|
|
109
117
|
よろしくお願いいたします。
|
|
110
118
|
|
|
111
119
|
コマンドライン引数などについては多少は理解しております。
|
|
120
|
+
|
|
121
|
+
質問のコード追記
|