マージソートの問題

[morokosiQ]

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

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]

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

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

エラーメッセージが書いていないので勘です。

[みけCAT]

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の間違いではないでしょうか？

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

C++ならエラーになりますが、C言語なら警告が出るだけでコンパイルは通るはずです。

[box]

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

そういう場合は、エラーメッセージを必ず提示していただきたいものです。
また、エラーメッセージが英語で書いてあることにめげないでいただきたいものです。

以下は独白
# コンパイ「ル」をなかなか通らない、という方が一般的であるような気がする。個人的には。

[morokosiQ]

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

コード:

#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]

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

• 8行目の第4引数が間違っている。leftではなくrightとするべき。
• 36行目の不等号が甘い。>=ではなく>とするべき。
• 38行目と47行目で1要素足りない。<ではなく<=とするべき。
• 54行目で1要素多い。<=ではなく<とするべき。
• 69行目で最後の要素を表示しない仕様は不自然。for (i=left ; i <= right ; i++)とするべきではないか？