合并排序代码调试

Question

我正试图为合并排序编写代码。我没有得到正确的输出。我遵循这个伪码链接，下面是我的代码。我将未排序的数组传递给merge_sort函数，并递归调用merge函数来排序和组合子数组。我知道有更简单、更有效的方法来编写合并排序的代码，但我想自己尝试，否则我就学不到了。提前谢谢。

int* merge_sort(int* a,int size)
{
    //cout<<size;
    //cout<<"hi";
    if(size == 1)
    {
        //cout<<"less";
        //cout<<a[0];

        return a;

    }
    int* left;
    int* right;

        int middle = ceil(size/2);
        left = new int(middle);
        right = new int(middle);
        for(int i=0;i<middle;i++)
        {
            left[i]=a[i];
            //cout<<left[i];
        }
        cout<<"\t";

        for(int j=middle;j<size;j++)
        {
            right[j]=a[j];
            //cout<<right[j];
        }
        cout<<"\t";
        left = merge_sort(left,middle);
        //if(size==2)
            //cout<<left[0];

        right = merge_sort(right,middle);
        //if(size==2)
            //cout<<right[0];

        return merge(left,right,middle);


}




int* merge(int* l,int* r,int m)
    {
        int* result;
        result = new int(2*m); //to store the output
        int lsize=m;  // to keep track of left sub list
        int rsize=m;  // to keep track of right sub list
        int counter = 0;  // will use to index result
        //cout<<m;


        while(lsize>0 || rsize>0)
        {
            if(lsize>0 && rsize>0)
            {
                if(l[0]<=r[0])
                {
                    result[counter]=l[0];
                    counter++; //to store next value in result
                    lsize--;  
                    l=&l[1]; //decrementing the size of left array
                }
                else
                {
                    result[counter]=r[0];
                    counter++;
                    rsize--; 
                    r=&r[1]; //dec. size of right array
                }

            }
            else if(lsize>0)
            {
                result[counter]=l[0];
                counter++;
                lsize--;
                l=&l[1];
            }
            else if(rsize>0)
            {
                result[counter]=l[0];
                counter++;
                lsize--;
                l=&l[1];
            }

        }
            return result;
    }

Answer 1

你的代码：

int *left = new int(middle);

分配一个初始化为middle的整数。你需要：

int *left = new int [middle];

它分配一个middle整数数组。冲洗并重复进行int *right。实际上，你需要使用：

int *right = new int [size - middle];

这将为right数组获得正确的大小。然后，您必须为merge_sort()子数组修改对right的递归调用：

merge_sort(right, size - middle);

最后，您必须重写merge()以独立地获取左数组的大小和右数组的大小，因为它们可能大小不同。例如，如果对10个元素进行排序，则最终会调用合并两个5数组(这很好)，但在下一个级别，您需要合并一个包含2个元素的数组和一个由3个元素组成的数组(然后您就被排除了)。

result的分配也存在着()与[]的分配问题。还有其他一些尚未解决的问题。但这些都是朝着正确方向迈出的重要步骤。

正如在对这个问题的评论中提到的，您也有一个巨大的内存泄漏问题。更重要的是，修复并不简单，因为merge_sort()在不分配新内存的情况下进行早期退出，所以它并不像‘删除merge_sort()返回的内存’那么简单。

复制和粘贴是很棒的，直到您忘记正确地编辑粘贴的副本：

    else if (lsize > 0)
    {   
        result[counter] = l[0];
        counter++;
        lsize--;
        l = &l[1];
    }   
    else if (rsize > 0)
    {   
        result[counter] = l[0];
        counter++;
        lsize--;
        l = &l[1];
    } 

在第二个块中，您应该使用r和rsize。

这还不是整个故事..。

剩下的问题(除了内存管理，它仍然是100%的泄漏和问题)是：

    for(int j=middle;j<size;j++)
    {
        right[j]=a[j];
        //cout<<right[j];
    }

您正在将未分配的部分复制到right中。你需要的东西更像：

    for(int j = 0; j < size - middle; j++)
    {
        right[j] = a[j + middle];
        //cout<<right[j];
    }

只要始终在顶层对至少两个项进行排序，这段代码就能工作(如果对1项进行排序，则会释放未分配的空间--这是内存管理问题的一部分)。

#include <iostream>
using namespace std;

namespace {

int *merge(int *l, int m, int *r, int n);

void dump_array(int *a, int size)
{
    int i;
    cout << size << ": ";
    for (i = 0; i < size; i++)
    {
        cout << ' ' << a[i];
        if (i % 10 == 9)
            cout << '\n';
    }
    if (i % 10 != 0)
        cout << '\n';
}

};

int *merge_sort(int *a, int size)
{
    cout << "-->> merge_sort:\n";
    dump_array(a, size);
    if (size <= 1)
    {
        cout << "<<-- merge_sort: early return\n";
        return a;
    }

    int middle = size/2;
    int *left = new int[middle];
    int *right = new int[size - middle];
    cout << middle << ": ";
    for (int i = 0; i < middle; i++)
    {
        left[i] = a[i];
        cout << ' ' << left[i];
    }
    cout << "\n";

    cout << (size - middle) << ": ";
    for (int j = 0; j < size - middle; j++)
    {
        right[j] = a[j + middle];
        cout << ' ' << right[j];
    }
    cout << "\n";
    cout << "MSL:\n";
    int *nleft = merge_sort(left, middle);
    cout << "NL: ";
    dump_array(nleft, middle);
    cout << "OL: ";
    dump_array(left, middle);
    cout << "OR: ";
    dump_array(right, size - middle);
    cout << "MSR:\n";
    int *nright = merge_sort(right, size - middle);
    cout << "NR: ";
    dump_array(nright, size - middle);
    cout << "NL: ";
    dump_array(nleft, middle);
    cout << "OL: ";
    dump_array(left, middle);
    cout << "OR: ";
    dump_array(right, size - middle);
    int *result =  merge(nleft, middle, nright, size - middle);
    cout << "<<-- merge_sort:\n";
    dump_array(result, size);
    return result;
}

namespace {

int *merge(int *l, int m, int *r, int n)
{
    int *result = new int[m + n];
    int lsize = m;
    int rsize = n;
    int counter = 0;
    cout << "-->> merge: (" << m << "," << n << ")\n";
    dump_array(l, m);
    dump_array(r, n);

    while (lsize > 0 || rsize > 0)
    {
        if (lsize > 0 && rsize > 0)
        {
            if (l[0] <= r[0])
            {
                result[counter] = l[0];
                cout << "C: " << counter << "; L = " << l[0] << "; LS = " << lsize << '\n';
                counter++;
                lsize--;
                l++;
            }
            else
            {
                result[counter] = r[0];
                cout << "C: " << counter << "; R = " << r[0] << "; RS = " << rsize << '\n';
                counter++;
                rsize--;
                r++;
            }
        }
        else if (lsize > 0)
        {
            result[counter] = l[0];
            cout << "C: " << counter << "; L = " << l[0] << "; LS = " << lsize << '\n';
            counter++;
            lsize--;
            l++;
        }
        else if (rsize > 0)
        {
            result[counter] = r[0];
            cout << "C: " << counter << "; R = " << r[0] << "; RS = " << rsize << '\n';
            counter++;
            rsize--;
            r++;
        }
    }
    cout << "<<-- merge:\n";
    dump_array(result, m+n);
    return result;
}

};

int main()
{
    for (int i = 2; i <= 10; i++)
    {
        int array1[] = { 9, 3, 5, 7, 1, 8, 0, 6, 2, 4 };
        cout << "\nMerge array of size " << i << "\n\n";
        int *result = merge_sort(array1, i);
        delete[] result;
    }
    return 0;
}

这是调试负载的代码。这是我为了获得这个结果而达到的水平。我也许可以用调试器。如果我在一台valgrind工作的机器上工作，它可能也会有所帮助(遗憾的是，它不能在MacOSX10.8.x上工作)。

仍然有很多很多方法来改进代码--包括内存管理。您可能会发现将输入数组传递给merge()作为结果数组最简单(避免在该代码中分配内存)。这将减少内存管理负担。

当删除调试代码时，需要调用main()程序中的main()函数来获取排序前后的数组图像。

转换为模板函数和无泄漏代码

我简化了一些代码，特别是在merge()函数中。此外，更多的是出于好奇，将其转换为一组模板函数，然后将它们与4种不同的数组类型(int、double、std::string、char)一起使用。调试的数量已经大大减少，主要调试取决于现在使用-DTRACE_ENABLED进行编译。

代码现在是无泄漏的；在没有例外的情况下，Linux盒(虚拟机)上的valgrind给了它一张干净的健康证明。但这并不能保证异常安全。事实上，考虑到new和delete的赤裸裸的使用，几乎可以保证不会出现异常安全。我已经把namespace控件放在了适当的位置，但我还远远不相信它真的是正确的--实际上，我认为它不太好。(我也很好奇是否有人对如何在namespace {…中布局代码有任何看法};块；似乎奇怪的不是缩进一组大括号内的所有内容，而是…)

#include <iostream>
using namespace std;

namespace {

#if !defined(TRACE_ENABLED)
#define TRACE_ENABLED 0
#endif

enum { ENABLE_TRACE = TRACE_ENABLED };

template <typename T>
void merge(T *l, int m, T *r, int n, T *result);

template <typename T>
void dump_array(const char *tag, T *a, int size)
{
    int i;
    cout << tag << ": (" << size << ") ";
    for (i = 0; i < size; i++)
    {
        cout << "  " << a[i];
        if (i % 10 == 9)
            cout << '\n';
    }
    if (i % 10 != 0)
        cout << '\n';
}

};

template <typename T>
void merge_sort(T *a, int size)
{
    if (size <= 1)
        return;

    if (ENABLE_TRACE)
        dump_array("-->> merge_sort", a, size);
    int middle = size/2;
    T *left = new T[middle];
    T *right = new T[size - middle];

    for (int i = 0; i < middle; i++)
        left[i] = a[i];

    for (int j = 0; j < size - middle; j++)
        right[j] = a[j + middle];

    merge_sort(left, middle);
    merge_sort(right, size - middle);
    merge(left, middle, right, size - middle, a);
    delete [] left;
    delete [] right;
    if (ENABLE_TRACE)
        dump_array("<<-- merge_sort", a, size);
}

namespace {

template <typename T>
void merge(T *l, int m, T *r, int n, T *result)
{
    T *l_end = l + m;
    T *r_end = r + n;
    T *out = result;
    if (ENABLE_TRACE)
    {
        cout << "-->> merge: (" << m << "," << n << ")\n";
        dump_array("L", l, m);
        dump_array("R", r, n);
    }

    while (l < l_end && r < r_end)
    {
        if (*l <= *r)
            *out++ = *l++;
        else
            *out++ = *r++;
    }
    while (l < l_end)
        *out++ = *l++;
    while (r < r_end)
        *out++ = *r++;

    if (ENABLE_TRACE)
        dump_array("<<-- merge", result, m+n);
}

};

#include <string>

int main()
{

    for (size_t i = 1; i <= 10; i++)
    {
        int array1[] = { 9, 3, 5, 7, 1, 8, 0, 6, 2, 4 };
        if (i <= sizeof(array1)/sizeof(array1[0]))
        {
            cout << "\nMerge array of type int of size " << i << "\n\n";
            dump_array("Original", array1, i);
            merge_sort(array1, i);
            dump_array("PostSort", array1, i);
        }
    }

    for (size_t i = 1; i <= 10; i++)
    {
        double array2[] = { 9.9, 3.1, 5.2, 7.3, 1.4, 8.5, 0.6, 6.7, 2.8, 4.9 };
        if (i <= sizeof(array2)/sizeof(array2[0]))
        {
            cout << "\nMerge array of type double of size " << i << "\n\n";
            dump_array("Original", array2, i);
            merge_sort(array2, i);
            dump_array("PostSort", array2, i);
        }
    }

    for (size_t i = 1; i <= 10; i++)
    {
        std::string array3[] = { "nine", "three", "five", "seven", "one", "eight", "zero", "six", "two", "four" };
        if (i <= sizeof(array3)/sizeof(array3[0]))
        {
            cout << "\nMerge array type std::string of size " << i << "\n\n";
            dump_array("Original", array3, i);
            merge_sort(array3, i);
            dump_array("PostSort", array3, i);
        }
    }

    for (size_t i = 1; i <= 10; i++)
    {
        char array4[] = "jdfhbiagce";
        if (i <= sizeof(array4)/sizeof(array4[0]))
        {
            cout << "\nMerge array type char of size " << i << "\n\n";
            dump_array("Original", array4, i);
            merge_sort(array4, i);
            dump_array("PostSort", array4, i);
        }
    }

    return 0;
}