質問編集履歴
2
プログラムを変更
title
CHANGED
|
File without changes
|
body
CHANGED
|
@@ -52,6 +52,75 @@
|
|
|
52
52
|
}
|
|
53
53
|
return 0;
|
|
54
54
|
}
|
|
55
|
+
プログラム追記マージソート
|
|
56
|
+
#include <stdio.h>
|
|
57
|
+
#define N 10
|
|
58
|
+
|
|
59
|
+
void merge(int *A, int nA, int *B, int nB, int i, int *C)
|
|
60
|
+
/* 整列配列A[0],...,A[nA-1]とB[0],...,B[nB-1]を併合し整列配列
|
|
61
|
+
C[i],...,C[i+nA+nB-1]に入れる */
|
|
62
|
+
{
|
|
63
|
+
int iA, iB, iC; /* iAはAの添字、iBはBの添字、iCは合計 */
|
|
64
|
+
|
|
65
|
+
iA=iB=iC=0; /* 併合の開始 */
|
|
66
|
+
while(iC <= nA+nB-1)
|
|
67
|
+
{
|
|
68
|
+
if(iA>=nA) {C[i+iC]=B[iB]; iB=iB+1;} /* Aは既に空 */
|
|
69
|
+
else
|
|
70
|
+
{
|
|
71
|
+
if(iB>=nB) {C[i+iC]=A[iA]; iA=iA+1;} /* Bは既に空 */
|
|
72
|
+
else /* A[iA]とB[iB]の小さい方をCへ移す */
|
|
73
|
+
{
|
|
74
|
+
if(A[iA]<=B[iB]) {C[i+iC]=A[iA]; iA=iA+1;}
|
|
75
|
+
else {C[i+iC]=B[iB]; iB=iB+1;}
|
|
76
|
+
}
|
|
77
|
+
}
|
|
78
|
+
iC=iC+1;
|
|
79
|
+
}
|
|
80
|
+
return;
|
|
81
|
+
}
|
|
82
|
+
|
|
83
|
+
|
|
84
|
+
void mergesort(int *A, int i, int j)
|
|
85
|
+
/* 配列A[i],...,A[j]をマージソートにより整列 */
|
|
86
|
+
{
|
|
87
|
+
int k, n, n1, n2, mid;
|
|
88
|
+
int A1[N], A2[N];
|
|
89
|
+
|
|
90
|
+
n=j-i+1; /* 配列のサイズ */
|
|
91
|
+
if(n>1)
|
|
92
|
+
{
|
|
93
|
+
mid=i+(n-1)/2; /* 中央値により前後の部分配列へ分割 */
|
|
94
|
+
mergesort(A, i, mid); /* 前半の整列 */
|
|
95
|
+
mergesort(A, mid+1, j); /* 後半の整列 */
|
|
96
|
+
n1=mid-i+1;
|
|
97
|
+
for(k=i; k<=mid; k++) A1[k-i]=A[k]; /* A1は前半の部分配列 */
|
|
98
|
+
n2=j-mid;
|
|
99
|
+
for(k=mid+1; k<=j; k++) A2[k-mid-1]=A[k]; /* A2は後半の部分配列 */
|
|
100
|
+
merge(A1, n1, A2, n2, i, A); /* A1とA2の併合 */
|
|
101
|
+
}
|
|
102
|
+
return;
|
|
103
|
+
}
|
|
104
|
+
|
|
105
|
+
|
|
106
|
+
|
|
107
|
+
|
|
108
|
+
int main (void) {
|
|
109
|
+
int array[N] = { 2, 1, 8, 5, 4, 7, 9, 0, 6, 3 };
|
|
110
|
+
int i;
|
|
111
|
+
|
|
112
|
+
printf("print array \n");
|
|
113
|
+
for (i = 0; i < N; i++) { printf("%d ", array[i]); }
|
|
114
|
+
printf("\n");
|
|
115
|
+
|
|
116
|
+
mergesort(array, 0, N);
|
|
117
|
+
|
|
118
|
+
printf("print array \n");
|
|
119
|
+
for (i = 0; i < N; i++) { printf("%d ", array[i]); }
|
|
120
|
+
printf("\n");
|
|
121
|
+
|
|
122
|
+
return 0;
|
|
123
|
+
}
|
|
55
124
|
```
|
|
56
125
|
mergeSortedDataByCatheの部分には部分的に並べ替えられたdata配列についてcacheを用いて昇順にマージソートする
|
|
57
126
|
プログラムとdata=とcache=になっている部分に何を代入すればよいかがわかりません。
|
1
プログラムを変更
title
CHANGED
|
File without changes
|
body
CHANGED
|
@@ -5,44 +5,48 @@
|
|
|
5
5
|
#include <string.h>
|
|
6
6
|
|
|
7
7
|
void mergeSortedDataByCathe(int *data,int *cache,int first,int last,int half){
|
|
8
|
-
|
|
8
|
+
int i,j,k;
|
|
9
|
+
for(i = first; i < half; i++) cache[i] = data[i];
|
|
10
|
+
for (j = last; i < last; i++) cache[i] = data[--j];
|
|
11
|
+
for (i--, j = first, k = first; k < last; k++)
|
|
12
|
+
data[k] = cache[j] < cache[i] ? cache[j++] : cache[i--];
|
|
9
13
|
}
|
|
10
14
|
|
|
11
15
|
void mergeSort(int *data,int *cache,int first,int last){
|
|
12
16
|
int half;
|
|
13
17
|
|
|
14
|
-
if(first=
|
|
18
|
+
if(last-first<=1) return;
|
|
15
19
|
half=(first+last)/2;
|
|
16
20
|
mergeSort(data,cache,first,half);
|
|
17
21
|
mergeSort(data,cache,half,last);
|
|
18
|
-
mergeSortedDataByCathe(data,cache,first,last,half);
|
|
22
|
+
mergeSortedDataByCathe(data,cache,first,last,half);
|
|
19
23
|
}
|
|
20
24
|
int main(int argc,char*argv[]){
|
|
21
25
|
int i,count,maxsize,*data,*cache;
|
|
22
26
|
FILE *fp;
|
|
23
27
|
|
|
24
28
|
if(argc!=3){
|
|
25
|
-
fprintf(stderr,"Usage: %s <maxsize> <filename>\n",argv[0]);
|
|
29
|
+
fprintf(stderr,"Usage: %s <maxsize> <filename>\n",argv[0]);
|
|
26
30
|
return 1;
|
|
27
31
|
}
|
|
32
|
+
|
|
28
33
|
maxsize=atoi(argv[1]);
|
|
29
|
-
printf("argc=%d",argc);
|
|
30
34
|
if((fp=fopen(argv[2],"r"))==NULL){
|
|
31
|
-
fprintf(stderr,"File %s is not found\n",argv[
|
|
35
|
+
fprintf(stderr,"File %s is not found\n",argv[2]);//標準エラー出力(printfと動きは同じ)
|
|
32
36
|
return 1;
|
|
33
37
|
}
|
|
34
|
-
if((data=
|
|
38
|
+
if((data=(int*)calloc(maxsize,sizeof(int)))==NULL){
|
|
35
39
|
fprintf(stderr,"Out of memory\n");
|
|
36
40
|
return 1;
|
|
37
41
|
}
|
|
38
|
-
if((cache=
|
|
42
|
+
if((cache=(int*)calloc(maxsize,sizeof(int)))==NULL){
|
|
39
43
|
fprintf(stderr,"Out of memory\n");
|
|
40
44
|
return 1;
|
|
41
45
|
}
|
|
42
46
|
for(count=0;count<maxsize;count++){
|
|
43
47
|
if(fscanf(fp,"%d",&data[count])==EOF) break;
|
|
44
48
|
}
|
|
45
|
-
|
|
49
|
+
mergeSort(data,cache,0,count);
|
|
46
50
|
for(i=0;i<count;i++){
|
|
47
51
|
printf("%d\n",data[i]);
|
|
48
52
|
}
|
|
@@ -53,4 +57,5 @@
|
|
|
53
57
|
プログラムとdata=とcache=になっている部分に何を代入すればよいかがわかりません。
|
|
54
58
|
とても難しい質問だと思いますが自分では解決できなかったのでもしよろしければ教えていただけると幸いです
|
|
55
59
|
よろしくお願いいたします。
|
|
56
|
-
コマンドライン引数などについては多少は理解しております。
|
|
60
|
+
コマンドライン引数などについては多少は理解しております。
|
|
61
|
+
質問のコード追記
|