併合処理ソートについて

質問

いつも大変お世話になっております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

回答No.2

goosyu · ベストアンサー

■構文上の問題点
　【誤】
　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;
　}

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

お礼

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

修正したのは上から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

回答No.1

Tacosan

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