回答編集履歴

2

追加コードについてもの問題点の指摘と cache の意味と mergeSortedDataByCache関数の説明を追加

2021/07/30 14:31

投稿

kazuma-s
kazuma-s

スコア8224

test CHANGED
@@ -100,8 +100,106 @@
100
100
 
101
101
  sort { 1 2 2 3 3 8 8 9 9 }
102
102
 
103
- ````
103
+ ```
104
+
105
+
104
106
 
105
107
  ソートされていますよね。
106
108
 
107
109
  変数の値の変化を見るとはこういうことです。
110
+
111
+
112
+
113
+ **追記2**
114
+
115
+ 質問の最後に「質問のコード追記」とあるのに、コードがない、
116
+
117
+ と思ったら、元のコードに追記したんですね。
118
+
119
+ そんなことをされたら、四角い枠の右上の + ボタンでコードをコピペ
120
+
121
+ しようとしたとき、要らないコードの削除が必要になります。
122
+
123
+ 別のコードとして追記してもらいたかった。
124
+
125
+ また「コード」や「プログラム追記マージソート」という文字列も
126
+
127
+ 枠の外に書くようにしてください。
128
+
129
+
130
+
131
+ その追記マージソートですが、問題があります。
132
+
133
+ `#define N 10` の 10 を別の値にしてみてください。
134
+
135
+ もちろん `int array[N] = { ... };` のデータも変更します。
136
+
137
+ 実行結果には変な数値が現れたりしませんか?
138
+
139
+
140
+
141
+ `void mergesort(int *A, int i, int j)` の j はソートしたい配列の
142
+
143
+ 最後の要素の添字です。
144
+
145
+ しかし、main の呼び出し元では `mergesort(array, 0, N);` と
146
+
147
+ 配列の最後の要素の次の添字 N を渡しています。
148
+
149
+ これは `N-1` にしないといけないでしょう。
150
+
151
+ N を渡すと、配列の範囲外の要素をアクセスし、未定義動作となります。
152
+
153
+
154
+
155
+ 次に、関数 mergesort は内部で `int A1[N], A2[N];` という配列を確保しています。
156
+
157
+ mergesort は再帰呼出しをしますから、呼び出しごとにスタック上に配列が
158
+
159
+ どんどん確保され、N が大きい場合、その確保に失敗する恐れがあります。
160
+
161
+
162
+
163
+ この問題を回避するために、main で確保した A1[N] と A2[N] をポインタで
164
+
165
+ 渡してやれば、mergesort は新たな領域を確保する必要がなくなります。
166
+
167
+
168
+
169
+ cache を使うほうのマージソートはそれを行っているのです。
170
+
171
+ A1 と A2 には分割されたデータが入るので 2つは要りません。
172
+
173
+ 1つの cache の中を使えばすみます。
174
+
175
+
176
+
177
+ では、
178
+
179
+ `void mergeSortedDataByCathe(int *data,int *cache,int first,int last,int half)`
180
+
181
+ の説明をします。
182
+
183
+
184
+
185
+ ここで渡されるデータは、main の配列 data の添字が first から half-1 までと
186
+
187
+ half から last-1 までの 2つの領域です。
188
+
189
+ この 2つのデータは既にソートされています。
190
+
191
+ それらをマージして、data の first から last-1 までに入れて返します。
192
+
193
+
194
+
195
+ 前半部分は cache の first から half-1 までにそのままコピーしますが、
196
+
197
+ 後半部分は cache の half から last までに data の後半部分を逆順に入れます。
198
+
199
+ すると 3つめの for文でマージするときに、2つのソート済みデータの末尾を
200
+
201
+ 気にする必要がなくなります。
202
+
203
+ 先に末尾に達したほうの添字は、もう一方の末尾の添字になるので、
204
+
205
+ 残りのデータは問題なく data に収容されます。

1

デバッグ表示を追加

2021/07/30 14:31

投稿

kazuma-s
kazuma-s

スコア8224

test CHANGED
@@ -17,3 +17,91 @@
17
17
  コンパイルエラーは自分で修正してください。
18
18
 
19
19
  他も修正しないと動きません。
20
+
21
+
22
+
23
+ **追記**
24
+
25
+ デバッグ用に printf を追加した mergeSortedDataByCahce です。
26
+
27
+ ```C
28
+
29
+ void mergeSortedDataByCathe(int *data,int *cache,int first,int last,int half){
30
+
31
+ int i, j, k;
32
+
33
+
34
+
35
+ printf("[%d %d %d] {", first, half, last);
36
+
37
+ for (i = first; i < half; i++) printf(" %d", data[i]);
38
+
39
+ printf(" |");
40
+
41
+ for (; i < last; i++) printf(" %d", data[i]);
42
+
43
+ printf(" }\n");
44
+
45
+
46
+
47
+ for (i = first; i < half; i++) cache[i] = data[i];
48
+
49
+ for (j = last; i < last; i++) cache[i] = data[--j];
50
+
51
+ for (i--, j = first, k = first; k < last; k++)
52
+
53
+ data[k] = cache[j] < cache[i] ? cache[j++] : cache[i--];
54
+
55
+
56
+
57
+ printf("sort {");
58
+
59
+ for (i = first; i < last; i++) printf(" %d", data[i]);
60
+
61
+ printf(" }\n");
62
+
63
+ }
64
+
65
+ ```
66
+
67
+ これで `3 8 3 8 9 2 9 2 1` をソートすると、次のようになりました。
68
+
69
+ ```text
70
+
71
+ [0 1 2] { 3 | 8 }
72
+
73
+ sort { 3 8 }
74
+
75
+ [2 3 4] { 3 | 8 }
76
+
77
+ sort { 3 8 }
78
+
79
+ [0 2 4] { 3 8 | 3 8 }
80
+
81
+ sort { 3 3 8 8 }
82
+
83
+ [4 5 6] { 9 | 2 }
84
+
85
+ sort { 2 9 }
86
+
87
+ [7 8 9] { 2 | 1 }
88
+
89
+ sort { 1 2 }
90
+
91
+ [6 7 9] { 9 | 1 2 }
92
+
93
+ sort { 1 2 9 }
94
+
95
+ [4 6 9] { 2 9 | 1 2 9 }
96
+
97
+ sort { 1 2 2 9 9 }
98
+
99
+ [0 4 9] { 3 3 8 8 | 1 2 2 9 9 }
100
+
101
+ sort { 1 2 2 3 3 8 8 9 9 }
102
+
103
+ ````
104
+
105
+ ソートされていますよね。
106
+
107
+ 変数の値の変化を見るとはこういうことです。