0

マージソートを実装する必要がある次の C++ コードがあります。部分的に機能していますが、何らかの理由でソートせずに無限ループを実行します。また、初期値ではなく、一部の値に 0.00 を出力します。(例: 入力値 9.12 1.59 出力 1.59 0.00) しかし、2 つ以上の要素がある場合は、それが無限ループであり、並べ替えを行わない場合です。追加の printf() は、割り当てを正しく行うために必要なので、分析では無視できます。助けてくれてありがとう!!

double max(double x, double y)
{
   return (x > y) ? x : y;
}

void sort_doubles(vector <double> &v, int print)
{
    int i;
    vector<double> tmp;
    tmp.resize(v.size());

    recursive_sort(v, tmp, 0, v.size(), print);
    printf("%16c",' ');
    for (i = 0; i < v.size(); i++) printf(" %.2lf",v.at(i));
    printf("\n");
}

void recursive_sort(vector<double> &v, vector<double> &temp, int start, int size, int print)
{
    int i,mid,left,right;
    double j;

    if (size == 1) return;

    i = 0;
    mid = start + (size/2);
    left = start;
    right = start + mid;

    printf("B: %5d %5d  ",start, size);
    for (i = 0; i < v.size(); i++) printf(" %.2lf", v.at(i));
    printf("\n");
    recursive_sort(v, temp, left, mid, print);
    recursive_sort(v, temp, left+mid, size-mid, print);

    for(i = 0; i < size; i++)
    {
        /* Check to see if any elements remain in the left array; if so,
         * we check if there are any elements left in the right array; if
         * so, we compare them.  Otherwise, we know that the merge must
         * use take the element from the left array */
        if(left < start + mid && (right == start+size || max(v[left], v[right]) == v[left]))
        {
            temp[i] = v[right];
            right++;
        }
        else
        {
            temp[i] = v[left];
            left++;
        }
    }
    /* Copy the sorted subarray back to the input */
    for(i = start; i < start+size; i++)
    {
        v[i] = temp[i];
    }
    printf("E: %5d %5d  ",start,size,' ');
    for (i = 0; i < v.size(); i++) printf(" %.2lf",v.at(i));
    printf("\n");
}
4

1 に答える 1

1

ついに思いついた！以下は、誰かがそれを必要とする場合に備えてのコードです。

double min(double x, double y)
{
    return (x < y) ? x : y;
}

void sort_doubles(vector <double> &v, int print)
{
    int i;
    vector<double> tmp;
    tmp.resize(v.size());

    recursive_sort(v, tmp, 0, v.size(), print);
    printf("%16c",' ');
    for (i = 0; i < v.size(); i++) printf(" %.2lf",v.at(i));
    printf("\n");
}

void recursive_sort(vector<double> &v, vector<double> &temp, int start, int size, int print)
{
    int i,mid,left,right;
    double j;

    if (size == 1) return;

    i = 0;
    mid = size/2;
    left = start;
    right = left+mid;

    printf("B: %5d %5d  ",start, size);
    for (i = 0; i < v.size(); i++) printf(" %.2lf", v.at(i));
    printf("\n");

    recursive_sort(v, temp, left, mid, print);
    recursive_sort(v, temp, left+mid, size-mid, print);

    for(i = 0; i < size; i++)
    {
        /* 
         * Check to see if any elements remain in the left array; if so,
         * we check if there are any elements left in the right array; if
         * so, compare them.  Otherwise, we know that the merge must
         * use take the element from the left array 
         */
        if(left < (start + mid) && (right == start+size || min(v.at(left), v.at(right)) == v.at(left)))
        {
            temp.at(i) = v.at(left);
            left++;
        }
        else
        {
            temp.at(i) = v.at(right);
            right++;
        }
    }

    //Copy the sorted subarray back to the input
    for(i = start; i < start+size; i++)
    {
        v.at(i) = temp.at(i-start);
    }

    printf("E: %5d %5d  ",start,size,' ');
    for (i = 0; i < v.size(); i++) printf(" %.2lf",v.at(i));
    printf("\n");
}
于 2012-10-20T05:56:38.877 に答える