マージソートを行うプログラム

Question

前提・実現したいこと

C言語でマージソートを行うプログラムを書いています。
以下に書いたプログラムを示します。

#include <stdio.h>

#define N 8

void show_addr(int X[], int n)    /*アドレスを表示*/
{
  int i;
  for(i = 0; i < n; i++)
    printf("%p ", X + i);
  puts("");
}

void show(int X[], int n)    /*配列内容を表示*/
{
  int i;
  for(i = 0; i < n; i++)
    printf("%d ", X[i]);
  puts("");
}

void merge(int Y1[], int n1, int Y2[], int n2, int Y[])    /*整列済みの二つの配列を併合*/
{
  int i = 0, j = 0, k = 0;

  while(j < n1 && k < n2){
    if(Y1[j] <= Y2[k])
      Y[i++] = Y1[j++];
    else
      Y[i++] = Y2[k++];
  }

  if(j == n1){
    while(k < n2)
      Y[i++] = Y2[k++];
  }
  else{
    while(j < n1)
      Y[i++] = Y2[j++];
  }
}

void msort(int X[], int n, int Y[])    /*マージソート*/
{
  int n1 = n / 2, n2 = n - n1, i = 0;
  int X1[n1], X2[n2], Y1[n1], Y2[n2];

  if(n == 1)
    Y[0] = X[0];

  else{
    while(i < n1)
      X1[i] = X[i++];
    while(i < n)
      X2[i] = X[i++];

    msort(X1, n1, Y1);
    msort(X2, n2, Y2);

    merge(Y1, n1, Y2, n2, Y);
  }
}

int main()
{
  int X[N] = {18, 37, 21, 14, 7, 12, 19, 6}, Y[N];

  show_addr(X, N);
  show_addr(Y, N);
  show(X, N);

  msort(X, N, Y);
  show(Y, N);

  return 0;
}

関数msortは引数にソートする配列、配列の大きさ、ソート済みの格納先を受け取ります。
(大きさnの配列X[]をソートしてY[]に格納します。)

発生している問題・エラーメッセージ

上のプログラムを実行すると以下のようなエラーメッセージが出力されます。

gcc -Wall -pedantic -o mergesort.out mergesort.c
mergesort.c: 関数 ‘show_addr’ 内:
mergesort.c:9:5: 警告: 書式 ‘%p’ は引数の型が ‘void *’ であると予期されますが、第 2 引数の型は ‘int *’ です [-Wformat=]
     printf("%p ", X + i);
     ^
mergesort.c: 関数 ‘msort’ 内:
mergesort.c:45:3: 警告: ISO C90 は可変長の配列 ‘X1’ を禁止しています [-Wvla]
   int X1[n1], X2[n2], Y1[n1], Y2[n2];
   ^
mergesort.c:45:3: 警告: ISO C90 は可変長の配列 ‘X2’ を禁止しています [-Wvla]
mergesort.c:45:3: 警告: ISO C90 は可変長の配列 ‘Y1’ を禁止しています [-Wvla]
mergesort.c:45:3: 警告: ISO C90 は可変長の配列 ‘Y2’ を禁止しています [-Wvla]
mergesort.c:52:18: 警告: ‘i’ に関する演算は定義されていません [-Wsequence-point]
       X1[i] = X[i++];
                  ^
mergesort.c:54:18: 警告: ‘i’ に関する演算は定義されていません [-Wsequence-point]
       X2[i] = X[i++];
                  ^

まず、アドレスの表示について、手元の参考書ではこのプログラムと同じく『%p』を用いているのですが、なぜうまくいかないのでしょうか。
『printf("%p ", X + i);』を『printf("%p ", (void *)(X + i));』とキャストするとエラーメッセージは消えましたが、前者ではダメな理由がわかりません。

二つ目に、関数msort内の作業用配列についてエラーメッセージが出ていますが、ここでの宣言は可変長配列なのでしょうか。
n1、n2は定数だと思います。(これらをNにするとエラーメッセージは消えました)

最後に『‘i’ に関する演算は定義されていません』というエラーメッセージがありますが、これについては全くわかりません。
iを宣言し忘れではありませんし、どう変更すればよいのでしょうか。

これらを部分的に修正していきたいと思っておりますので、プログラム全体の方針等は目を瞑っていただければと思います。

ご回答よろしくお願いします。

Answer 1

mergesort.c:9:5: 警告: 書式 ‘%p’ は引数の型が ‘void *’ であると予期されますが、第 2 引数の型は ‘int *’ です [-Wformat=]

よーく読め。それはエラー(error)じゃない。警告(warning)だ。
ダメなんじゃない、「ひょっとしたらあなたの意図とは異なる挙動を示すかもよ」と警告している。

Comments

[aiueo12345]

ご回答ありがとうございます。
別に間違ってはいないということだったのですね。

[episteme]

間違ってる「かもしれない」です。

Answer 2

まず、アドレスの表示について、手元の参考書ではこのプログラムと同じく『%p』を用いているのですが、なぜうまくいかないのでしょうか。

%pはvoidポインタの値を表示する書式指定のため、-Wallを付けたことでポインタの型が違うと警告されています。

二つ目に、関数msort内の作業用配列についてエラーメッセージが出ていますが、ここでの宣言は可変長配列なのでしょうか。

n1、n2は定数だと思います。(これらをNにするとエラーメッセージは消えました)

n1、n2はint変数です。
オプションに-std=c99か-std=c11をつければ可変長配列を使用できます。

最後に『‘i’ に関する演算は定義されていません』というエラーメッセージがありますが、これについては全くわかりません。

      X1[i] = X[i++];
      X2[i] = X[i++];

iとi++どちらが先に評価されるか不定です。
以下に解説があります。
EXP30-C. 副作用が発生する式の評価順序に依存しない

Comments

[aiueo12345]

ご回答ありがとうございます。
一つ目については修正しなくても問題ないのですね。

二つ目について、配列の大きさは定数でなければならず、変数だったためエラーとなったのですね。
可変長の配列を扱えるオプションについては初めて知りました。試してみます。

三つめはそういうことだったのですね。
一つの式で複数のiを用いる場合はインクリメントを別にしなければいけないのですね。
大変勉強になりました。

Answer 3

2つ目についてのみ答えるとC言語においては
配列の要素数は定数式を与える事になっており
定数式とは、定数のみ(+#defineで定義した定数を含む)からなる式であり、
変数や、const変数が混じってはダメとなっております。
(さすがに厳しかったのか、C++では定数式で初期化されたconst変数を混ぜてもよくなりました。)

Comments

[aiueo12345]

ご回答ありがとうございます。
確かに不便に感じます。Cでもconstは許してほしいですね。(今回はconst関係ないですが)
今回は他の解答者様に教えていただいたオプションを使用することで上手くいきました。

Answer 4

これらを部分的に修正していきたいと思っておりますので、

元の質問のコードにはまだ誰も指摘していない間違いがあるのですが、
もう解決済みですか？
質問を編集して、解決したコードを追記してください。

2つ目の Y[i++] = Y2[j++]; は Y[i++] = Y1[j++]; でしょう。

プログラム全体の方針等は目を瞑っていただければと思います。

目を瞑りたくないなあ。
再帰呼出しで、ローカルに大きな配列を確保し続けると、
スタックオーバーフローが起きやすくなりますよ。

追記

最初に1回 msort の中で必要な領域を確保しておけば、
再帰呼出しの merge_sort ではそれを使うだけのコードを書いてみました。

#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);
}