kazuma-s score 5132
2019/07/17 09:14 投稿
| > これらを部分的に修正していきたいと思っておりますので、 |
| 元の質問のコードにはまだ誰も指摘していない間違いがあるのですが、 |
| もう解決済みですか？ |
| 質問を編集して、解決したコードを追記してください。 |
| 2つ目の Y[i++] = Y2[j++]; は Y[i++] = Y1[j++]; でしょう。 |
| > プログラム全体の方針等は目を瞑っていただければと思います。 |
| 目を瞑りたくないなあ。 |
| 再帰呼出しで、ローカルに大きな配列を確保し続けると、 |
| スタックオーバーフローが起きやすくなりますよ。 |
| スタックオーバーフローが起きやすくなりますよ。 |
| ### 追記 |
| 最初に1回 msort の中で必要な領域を確保しておけば、 |
| 再帰呼出しの merge_sort ではそれを使うだけのコードを書いてみました。 |
| ```C |
| #include <stdio.h> // printf, putchar |
| #include <stdlib.h> // malloc, free |
| #define N 8 |
| void show(int x[], int n) |
| { |
| for (int i = 0; i < n; i++) printf(" %d", x[i]); |
| putchar('\n'); |
| } |
| void merge(int x[], int m, int y[], int n, int t[]) |
| { |
| int i = 0, j = 0, k = 0; |
| while (j < m && k < n) t[i++] = (x[j] < y[k]) ? x[j++] : y[k++]; |
| while (j < m) t[i++] = x[j++]; |
| while (k < n) t[i++] = y[k++]; |
| } |
| void merge_sort(int x[], int n, int t[]) |
| { |
| if (n < 2) return; |
| int n1 = n / 2, n2 = n - n1; |
| merge_sort(x, n1, t); |
| merge_sort(x + n1, n2, t); |
| merge(x, n1, x + n1, n2, t); |
| for (int i = 0; i < n; i++) x[i] = t[i]; |
| } |
| void msort(int x[], int n, int y[]) |
| { |
| int *t = malloc(sizeof(int) * n * 2); |
| if (!t) { puts("out of memory"); return; } |
| for (int i = 0; i < n; i++) t[i] = x[i]; |
| merge_sort(t, n, t + n); |
| for (int i = 0; i < n; i++) y[i] = t[i]; |
| free(t); |
| } |
| int main() |
| { |
| int x[N] = { 18, 37, 21, 14, 7, 12, 19, 6 }, y[N]; |
| show(x, N); |
| msort(x, N, y); |
| show(y, N); |
| } |
| ``` |
