0

マージソート用に作成したコードを以下に示します。問題は、入力を与えると出力が3 2 1 5 0になることです。何がうまくいかないのですか？

#include <iostream>
#include <cmath>
using namespace std;

int d[100];

void merge(int a[], int b[], int c[], int n)
{
int n2=floor(n/2);
int i=0, j=0, k=0;
while(i<n2 && j<(n-n2))
{
    if(b[i]<c[j])
    {
        d[k++]=b[i++];
    }
    else if(b[i]>c[j])
    {
        d[k++]=c[j++];
    }
}
    if(i==n2)
    {
        if(j<(n-n2))
        {
            d[k++]=c[j++];
        }
    }
    if(i<n2)
    {
        d[k++]=b[i++];
    }
}


void mergesort(int a[], int n)
{
int n2=floor(n/2);
int b[50],c[50];
int i,j=0,k=0;
for(i=0;i<n2;i++)
{
    b[i]=a[k++];
}
while(k<n)
{
    c[j++]=a[k++];
}
merge(a,b,c,n);
}

int main()
{
int a[]={5,4,3,2,1};
int n=5;
mergesort(a,n);
for(int i=0;i<n;i++)
{
    cout<<d[i]<<endl;
}
}
4

5 に答える 5

4

主な問題は、マージに渡された配列 (b と c) がソートされていないことです。その他の問題は、アルゴリズムが再帰的ではないことと、マージが常に b と c のすべての数値を a に入れるとは限らないことです。

コードへの最小限の変更で動作するように見えるバージョンは次のようになります

void merge(int a[], int b[], int c[], int n)
{
  int n2=floor(n/2);
  int i=0, j=0, k=0;
  while(k<n)
  {
    if((j == (n-n2) || b[i]<c[j]) && i < n2)
    {
      a[k++]=b[i++];
    }
    else
    {
      a[k++]=c[j++];
    }
  }
}


void mergesort(int a[], int n)
{
  int n2=floor(n/2);
  int b[50],c[50];
  int i,j=0,k=0;
  for(i=0;i<n2;i++)
  {
    b[i]=a[k++];
  }
  while(k<n)
  {
    c[j++]=a[k++];
  }
  if(n2 > 1) {
    mergesort(b, n2);
  }
  if(n - n2 > 1) {
    mergesort(c, n - n2);
  }
  merge(a,b,c,n);
}

int main()
{
  int a[]={5,4,3,2,1};
  int n=5;
  mergesort(a,n);
  for(int i=0;i<n;i++)
  {
    cout<<a[i]<<endl;
  }
}
于 2013-07-31T07:18:39.383 に答える
2

各サブ範囲をソートするために、再帰的に merge_sort を呼び出して、サブ範囲が 1 つになるまで並べ替えてから、これらをマージするのが一般的です。

ではmergesort、bの最初の n/2 値a、つまり 5 と 4 cを取ります。残りの値 3,2,1 を取ります。

次に、呼び出しますmerge（ところで、なぜこれに渡すa[]のですか？使用されていません）最初のループ

while(i<n2 && j<(n-n2))

これはn2 = 2、同様の理由n-n2 = 5-2 = 3 で、最初に 3 を置き、b[0]>c[0]=3次から 2を置きb[1]>c[1]=2、1 を置きます。d[2]再帰しないため、これらはソートされません。次に、n2 より小さい i = 0 で while ループを終了します。あなたはただ言う

if(i<n2)

したがって、b の最初のもの、つまり 5 をコピーするだけです。

dあなたがグローバルにしたので、これはすべて3、2、1、5、および0を与えます。

于 2013-07-31T07:41:40.630 に答える
0

Philip の言うとおりです。コードには再帰はまったくありません。

ただし、さらにいくつかのエラーがあります。Philip のあとがきと同じように、注釈を付けました。

#include <iostream>
#include <cmath>
using namespace std;

int d[100];

void merge(int a[], int b[], int c[], int n)
{
    int n2=floor(n/2);
    int i=0, j=0, k=0;
    while(i<n2 && j<(n-n2))
    {
        if(b[i]<c[j])
        {
            d[k++]=b[i++];
        }
        else if(b[i]>c[j])
        {
            d[k++]=c[j++];
        }
        /***************************************************/
        /* What if b[i] == c[j] here?                      */
        /* Your code will drop into an infinity loop.      */
        /***************************************************/
    }
    if(i==n2)
    {
        if(j<(n-n2))
        /****************************************************/
        /* Use **while** here?                              */
        /* Because there may be more than one elements left */
        /* in c[].                                          */
        /****************************************************/
        {
            d[k++]=c[j++];
        }
    }
    if(i<n2)
    /***************************************************/
    /* Use **while** here? - With the same reason      */
    /***************************************************/
    {
        d[k++]=b[i++];
    }
}


void mergesort(int a[], int n)
{
    int n2=floor(n/2);
    int b[50],c[50];
    int i,j=0,k=0;
    for(i=0;i<n2;i++)
    {
        b[i]=a[k++];
    }
    while(k<n)
    {
        c[j++]=a[k++];
    }
    merge(a,b,c,n);
}

int main()
{
    int a[]={5,4,3,2,1};
    int n=5;
    mergesort(a,n);
    for(int i=0;i<n;i++)
    {
        cout<<d[i]<<endl;
    }
}
于 2013-07-31T08:52:41.423 に答える