マージソートの問題

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
morokosiQ

マージソートの問題

#1

投稿記事 by morokosiQ » 5年前

院試の過去問にあるマージソートの問題を解いてみたのですが、コンパイラをなかなか通りません。
どこが原因なのでしょうか、、?

http://i.imgur.com/6CVy88x.png (問題)

コード:

#include <stdio.h>

void mSort (int date[ ], int tmp[ ], int left, int right)
{
	if( right <= left ) return ;
	int mid = ( left + right)/2;
	 mSort ( date , tmp , left , mid);
	 mSort ( date , tmp , mid+1, left);

	merge( date , tmp, left , mid , right );
}

void merge( int date [ ], int tmp [ ], int left , int mid , int right) 
{
	int tmpNo = left;
	while( left<=mid && mid+1<=right)  /*左の数列が空でない && 右の数列が空でない*/
	{
		if( date[left] <= date[mid+1]) /*左列の先頭の要素 <= 右列の先頭の要素*/
		{
			tmp[tmpNo]=date[left];
			tmpNo = tmpNo + 1;
			left = left+1;
		}
		else
		{
			tmp[tmpNo] = date[mid + 1];
			tmpNo = tmpNo + 1;
			mid+1 = mid +1+1;
		}
	}
	if ( left >= mid) /*左列が空である*/
	{
		while( mid+1 < right)
		{
			tmp[tmpNo] = date[mid+1];
			tmpNo = tmpNo + 1;
			mid+1 = mid +1+1;
		}
	}
	else /*右列が空*/
	{
		while ( left < mid )
		{
			tmp[tmpNo]=date[left];
			tmpNo = tmpNo + 1;
			left = left+1;
		}
	}
}
			 	
int main(void)
{
	int date[ ] = {1,4,2,7,4,9,1,2,5,3,9,0,4,3,1,2}; /*適当に設定*/
	int tmp[ ];
	int left = 0;
	int right = 15;
	int i ;
	mSort (date , tmp , left , right);
	for (i=0 ; i < light ; i++)
		printf("x[%d] = %d\n", i , date[i]);
	return (0) ;
}


Rittai_3D
記事: 525
登録日時: 7年前

Re: マージソートの問題

#2

投稿記事 by Rittai_3D » 5年前

C言語でしょうか?
C言語は後方参照ができません。merge()をmSort()の前方で実装する、もしくは、プロトタイプ宣言を書けば解決できると思います。

すいません、勘違いでした。

エラーメッセージが書いていないので勘です。
最後に編集したユーザー Rittai_3D on 2015年7月22日(水) 20:50 [ 編集 1 回目 ]
初心者です

アバター
みけCAT
記事: 6274
登録日時: 9年前
住所: 千葉県
連絡を取る:

Re: マージソートの問題

#3

投稿記事 by みけCAT » 5年前

Wandboxのgcc 4.8.2でC89としてRunした結果のエラーメッセージです。

コード:

prog.c: In function 'mSort':
prog.c:10:2: warning: implicit declaration of function 'merge' [-Wimplicit-function-declaration]
  merge( date , tmp, left , mid , right );
  ^
prog.c: At top level:
prog.c:13:6: warning: conflicting types for 'merge' [enabled by default]
 void merge( int date [ ], int tmp [ ], int left , int mid , int right) 
      ^
prog.c:10:2: note: previous implicit declaration of 'merge' was here
  merge( date , tmp, left , mid , right );
  ^
prog.c: In function 'merge':
prog.c:28:10: error: lvalue required as left operand of assignment
    mid+1 = mid +1+1;
          ^
prog.c:37:10: error: lvalue required as left operand of assignment
    mid+1 = mid +1+1;
          ^
prog.c: In function 'main':
prog.c:54:6: error: array size missing in 'tmp'
  int tmp[ ];
      ^
prog.c:59:17: error: 'light' undeclared (first use in this function)
  for (i=0 ; i < light ; i++)
                 ^
prog.c:59:17: note: each undeclared identifier is reported only once for each function it appears in
  • 28行目と37行目のmid+1 = mid +1+1;という式は、(変数ではなく)値に代入しようとしているので不正です。
    mid = mid +1;の間違いではないでしょうか?
  • 54行目で、配列の要素数の指定がありません。
    例えばint tmp[ sizeof(date)/sizeof(date[0]) ];とするとよいでしょう。
  • 59行目で使用されている変数lightが宣言されていません。rightの間違いではないでしょうか?
Rittai_3D さんが書きました:C言語でしょうか?
C言語は後方参照ができません。merge()をmSort()の前方で実装する、もしくは、プロトタイプ宣言を書けば解決できると思います。
C++ならエラーになりますが、C言語なら警告が出るだけでコンパイルは通るはずです。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

box
記事: 1746
登録日時: 9年前

Re: マージソートの問題

#4

投稿記事 by box » 5年前

morokosiQ さんが書きました:院試の過去問にあるマージソートの問題を解いてみたのですが、コンパイラをなかなか通りません。
どこが原因なのでしょうか、、?
そういう場合は、エラーメッセージを必ず提示していただきたいものです。
また、エラーメッセージが英語で書いてあることにめげないでいただきたいものです。

以下は独白
# コンパイ「ル」をなかなか通らない、という方が一般的であるような気がする。個人的には。
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。

morokosiQ

Re: マージソートの問題

#5

投稿記事 by morokosiQ » 5年前

ご指摘頂いた箇所を直したらコンパイラを通ったのですが、昇順に並んでくれません。どこに不具合があるのでしょうか

コード:

#include <stdio.h>

void mSort (int date[ ], int tmp[ ], int left, int right)
{
	if( right <= left ) return ;
	int mid = ( left + right)/2;
	 mSort ( date , tmp , left , mid);
	 mSort ( date , tmp , mid+1, left);

	merge( date , tmp, left , mid , right );
}
	 	

void merge( int date [ ], int tmp [ ], int left , int mid , int right) 
{
	int tmpNo = left;
        int nextmid = mid+1;
        int i ;
       int  num_elements = right - left + 1; /* 配列の要素数 */

	while( left<=mid && nextmid<=right)  /*左の数列が空でない && 右の数列が空でない*/
	{
		if( date[left] <= date[nextmid]) /*左列の先頭の要素 <= 右列の先頭の要素*/
		{
			tmp[tmpNo]=date[left];
			tmpNo = tmpNo + 1;
			left = left+1;
		}
		else
		{
			tmp[tmpNo] = date[nextmid];
			tmpNo = tmpNo + 1;
			nextmid = nextmid+1;
		}
	}
	if ( left >= mid) /*左列が空である*/
	{
		while( nextmid < right)
		{
			tmp[tmpNo] = date[nextmid];
			tmpNo = tmpNo + 1;
			nextmid = nextmid +1;
		}
	}
	else /*右列が空*/
	{
		while ( left < mid )
		{
			tmp[tmpNo]=date[left];
			tmpNo = tmpNo + 1;
			left = left+1;
		}
	}
        for (i=0; i <= num_elements; i++)
        {
        date[right] = tmp[right];
        right = right - 1;
        }
}

int main(void)
{
	int date[ ] = {4,2,5,4,3,2,7,8}; /*適当に設定*/
	int tmp[sizeof(date)/sizeof(date[0]) ];
	int left = 0;
	int right = 7;
	int i ;
	mSort (date , tmp , left , right);
	for (i=0 ; i < right ; i++)
		printf("x[%d] = %d\n", i , date[i]);
	return (0) ;
}

アバター
みけCAT
記事: 6274
登録日時: 9年前
住所: 千葉県
連絡を取る:

Re: マージソートの問題

#6

投稿記事 by みけCAT » 5年前

morokosiQ さんが書きました:ご指摘頂いた箇所を直したらコンパイラを通ったのですが、昇順に並んでくれません。どこに不具合があるのでしょうか
  • 8行目の第4引数が間違っている。leftではなくrightとするべき。
  • 36行目の不等号が甘い。>=ではなく>とするべき。
  • 38行目と47行目で1要素足りない。<ではなく<=とするべき。
  • 54行目で1要素多い。<=ではなく<とするべき。
  • 69行目で最後の要素を表示しない仕様は不自然。for (i=left ; i <= right ; i++)とするべきではないか?
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

閉鎖

“C言語何でも質問掲示板” へ戻る