teratail header banner
teratail header banner
質問するログイン新規登録

回答編集履歴

1

コードの追加

2019/07/17 00:14

投稿

kazuma-s
kazuma-s

スコア8222

answer CHANGED
@@ -10,4 +10,56 @@
10
10
 
11
11
  目を瞑りたくないなあ。
12
12
  再帰呼出しで、ローカルに大きな配列を確保し続けると、
13
- スタックオーバーフローが起きやすくなりますよ。
13
+ スタックオーバーフローが起きやすくなりますよ。
14
+ ### 追記
15
+ 最初に1回 msort の中で必要な領域を確保しておけば、
16
+ 再帰呼出しの merge_sort ではそれを使うだけのコードを書いてみました。
17
+ ```C
18
+ #include <stdio.h> // printf, putchar
19
+ #include <stdlib.h> // malloc, free
20
+
21
+ #define N 8
22
+
23
+ void show(int x[], int n)
24
+ {
25
+ for (int i = 0; i < n; i++) printf(" %d", x[i]);
26
+ putchar('\n');
27
+ }
28
+
29
+ void merge(int x[], int m, int y[], int n, int t[])
30
+ {
31
+ int i = 0, j = 0, k = 0;
32
+ while (j < m && k < n) t[i++] = (x[j] < y[k]) ? x[j++] : y[k++];
33
+ while (j < m) t[i++] = x[j++];
34
+ while (k < n) t[i++] = y[k++];
35
+ }
36
+
37
+ void merge_sort(int x[], int n, int t[])
38
+ {
39
+ if (n < 2) return;
40
+ int n1 = n / 2, n2 = n - n1;
41
+ merge_sort(x, n1, t);
42
+ merge_sort(x + n1, n2, t);
43
+ merge(x, n1, x + n1, n2, t);
44
+ for (int i = 0; i < n; i++) x[i] = t[i];
45
+ }
46
+
47
+ void msort(int x[], int n, int y[])
48
+ {
49
+ int *t = malloc(sizeof(int) * n * 2);
50
+ if (!t) { puts("out of memory"); return; }
51
+ for (int i = 0; i < n; i++) t[i] = x[i];
52
+ merge_sort(t, n, t + n);
53
+ for (int i = 0; i < n; i++) y[i] = t[i];
54
+ free(t);
55
+ }
56
+
57
+ int main()
58
+ {
59
+ int x[N] = { 18, 37, 21, 14, 7, 12, 19, 6 }, y[N];
60
+ show(x, N);
61
+ msort(x, N, y);
62
+ show(y, N);
63
+ }
64
+
65
+ ```