こんにちはゲストさん。会員登録(無料)して質問・回答してみよう!

解決済みの質問

併合処理ソートについて

いつも大変お世話になっておりますm(_ _)m

アルゴリズム初心者なのですが、併合処理ソートをC言語で自作しています。しかし途中で行き詰ってしまい困っております。

私が作成したコードは以下になります。

void merge(int D[], int left, int mid, int right)
{
int x, y, i, M[50000];
x=left;
y=mid+1;
for(i=0; i<=right-left; i=i+1){
if((x != mid+1)&&(y != right+1))
{
if (D[x]<D[y]){
M[i]=D[x];
x=x+1;
}
else if (D[x]=D[y]){
M[i]=D[x];
x=x+1;
i=i+1;
M[i]=D[y];
y=y+1;
}
else {
M[i]=D[y];
y=y+1;
}
}

if(x == mid+1){
M[i]=D[y];
y=y+1;
}
if(y == right+1){
M[i]=D[x];
x=x+1;
}
}
for(i=left; i<=right-left; i=i+1){
D[i]=M[i];
}
}
void mergesort(int D[], int left, int right)
{

int mid;
if(left != right){
mid=(left+right)/2;
if(left < mid) mergesort(D,left,mid);
if(right > mid+1) mergesort(D,mid+1,right);
merge(D,left,mid,right);
}
}

入力は五桁程度の正の整数の昇順並び替えで、↑のコードの中には
入力と出力に関するコードは含んでいません。入力出力部分に誤りはないと思われます。

出力しても正しく昇順に並んでくれません。。。
どなたかご教授ご指導お願い致しますm(_ _)m

投稿日時 - 2009-08-02 23:10:27

QNo.5176997

すぐに回答ほしいです

質問者が選んだベストアンサー

■構文上の問題点
 【誤】
 else if (D[x]=D[y]){
 【正】
 else if (D[x]==D[y]){

■ロジック上の問題点
 次の処理に前にxまたはyが更新されて,この処理に入るがiが更新されない為,M[i]の値が上書きされて破壊されます。
 ☆continueとかelse句とかで解決出来ると思います。

 if(x == mid+1){
  M[i]=D[y];
  y=y+1;
 }
 if(y == right+1){
  M[i]=D[x];
  x=x+1;
 }

たぶん,まだ問題があるかもしれませんが,あとは小さい要素数でトレースしてロジックの完成度を確認してみては。

投稿日時 - 2009-08-03 05:28:44

お礼

皆さんありがとうございます。
お二人にご指摘して頂いたところを修正したところ、入力がそのまま出力されるようになりました。

修正したのは上から13行目からで、以下のように修正しました。

else if (D[x]==D[y]){
M[i]=D[x];
x=x+1;
i=i+1;
M[i]=D[y];
y=y+1;
}
else {
M[i]=D[y];
y=y+1;
}
}
if(x == mid+1){
M[i]=D[y];
y=y+1;
}
else{
M[i]=D[x];
x=x+1;
}
}

また何かございましたらよろしくお願いしますm(_ _)m

投稿日時 - 2009-08-03 11:00:35

ANo.2

このQ&Aは役に立ちましたか?

1人が「このQ&Aが役に立った」と投票しています

回答(2)

ANo.1

あきらかにおかしいところが 1ヶ所.
最後に M[] から D[] へ戻すところが間違ってます.

投稿日時 - 2009-08-03 00:01:44

あなたにオススメの質問