質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

88.03%

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

解決済

回答 4

投稿

  • 評価
  • クリップ 0
  • VIEW 1,451

score 21

前提・実現したいこと

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を宣言し忘れではありませんし、どう変更すればよいのでしょうか。

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

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

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 4

+3

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/07/15 16:22

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

    キャンセル

  • 2019/07/16 04:32

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

    キャンセル

checkベストアンサー

+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. 副作用が発生する式の評価順序に依存しない

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/07/15 16:28

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

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

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

    キャンセル

+1

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/07/15 16:58

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

    キャンセル

0

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

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

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

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 88.03%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る