1

マージソートのコードを書こうとしています。正しい出力が得られません。私はこの疑似コードリンクをたどっています。以下は私のコードです。ソートされていない配列をmerge_sort関数に渡し、マージ関数を再帰的に呼び出して、サブ配列をソートして結合します。マージソートのコードを書くより簡単で効率的な方法があることは知っていますが、自分で試してみたいと思います。 . 前もって感謝します。

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;
    }
4

1 に答える 1

3

あなたのコード:

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 つの配列をマージする呼び出しが発生しますが (これは問題ありません)、次のレベルでは、2 個の要素の配列と 3 個の要素の配列をマージする必要があります (そして、ホースされています）。

の割り当てにresultも()vs[]割り当ての問題があります。そして、まだ解決されていない問題がいくつかあります。しかし、これらは正しい方向への重要なステップです。

質問へのコメントで述べたように、記念碑的なメモリリークの問題もあります。さらに、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];
    }

これらのブロックの 2 番目にrandを使用する必要があると思います。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];
    }

このコードは、常に最上位で少なくとも 2 つのアイテムを並べ替える限り機能します (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ていれば、それも役に立ったかもしれません (残念ながら、Mac OS X 10.8.x では動作しません)。

メモリ管理を含め、コードを改善する方法はまだたくさんあります。おそらく、入力配列を結果配列として使用するために渡すのが最も簡単であることがわかるでしょうmerge()(そのコードでのメモリ割り当てを回避します)。これにより、メモリ管理の負担が軽減されます。

デバッグ コードを削除するときはdump_array()、プログラム内で関数を呼び出して、main()配列イメージの並べ替えの前後を取得する必要があります。

テンプレート関数に変換され、リークのないコード

merge()特に関数では、コードをかなり単純化しました。また、何よりも好奇心の問題として、それを一連のテンプレート関数に変換し、4 つの異なる配列型 ( int、double、std::string、char) で使用しました。デバッグの量は劇的に削減され、メインのデバッグは-DTRACE_ENABLED現在コンパイルされていることを条件としています。

コードに漏れがなくなりました。valgrindLinux ボックス (仮想マシン) では、例外がない場合はクリーンな状態になります。ただし、例外に対して安全であるとは限りません。実際、 と をそのまま使用する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;
}
于 2013-09-21T04:35:51.143 に答える