2

Coursera のAlgorithms: Design and Analysisコース ( https://www.coursera.org/course/algo )の最初のプログラミングの宿題に取り組んでいます。マージソートを使用して反転をカウントする必要があります ( http://en.wikipedia.org/wiki/Inversion_(discrete_mathematics ) )。以前（学校で）マージソートに遭遇したので、これは比較的簡単だと思いました。

#include <iostream>
#include <fstream>

using namespace std;

int *half(int *array, int n, int start, int end)
{
    /*
     * Creates a new array which contains elements from ''array'' starting with ''start''
     * and ending with ''end - 1''.
     */

     int *new_array = new int[end-start];

     for(int i = start; i < end; i++)
     {
        new_array[i-start] = array[i];
     }

     return new_array;
}

int merge(int *array1, int n1, int *array2, int n2, int *new_array)
{
    /*
     *  Merges arrays 1 and 2 (with lengths n1 and n2) into a new_array, counting
     *  ''split inversions'' by the way.
     */
    int i = 0, j = 0, count = 0;

    for(int k = 0; k < n1 + n2; k++)
    {

         if(i >= n1)
        {
            new_array[k] = array2[j];
            j++;
            continue;
        }

         if(j >= n2)
        {

            new_array[k] = array1[i];
            i++;
            continue;
        }

        if( array1[i] <= array2[j] )
        {
            new_array[k] = array1[i];
            i++;
        }
        else
        {
            new_array[k] = array2[j];
            j++;
            count++;
        }
    }

    return count;
}

int mergesort(int *array, int n)
{

    if(n == 1) return 0; //base case

    int x, y, z;
    int odd;

    if(n%2 == 0) odd = 0;
    else odd = 1;

    int *half1 = new int [n/2];
    int *half2 = new int [n/2 + odd];

    half1 = half(array, n, 0, n/2);
    half2 = half(array, n, n/2, n);

    x = mergesort(half1, n/2);
    y = mergesort(half2, n/2 + odd);  //if n is odd, we add one
    z = merge(half1, n/2, half2, n/2 + odd, array); //we write a sorted array back in our starting array

    delete [] half1;
    delete [] half2;

    return x + y + z;
}

int main()
{
    int n;
    int *array = new int[n];

    cin >> n;

    for(int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        array[i] = x;
    }

    for(int i = 0; i < n; i++)
        cout << array[i] << " ";

    cout << endl;
    cout << "Number of inversions: " << mergesort(array, n) << endl;

    for(int i = 0; i < n; i++)
    cout << array[i] << " ";

    cout << endl;
    delete[] array;

    return 0;
}

それで、ここで何がそんなに奇妙ですか？最初に: 私にとっては、一部の配列では完全に機能しますが、他の配列ではクラッシュします (例は後述)。2 番目のこと: 私はコードを友人に送りました。友人は、私の場合は劇的にクラッシュする例でさえ、すべてが正常に機能していると言っていました。

したがって、例：

配列 [1 2 3 4 5 6 7] の場合、g++ はこれを生成します。

malloc.c:2451: sYSMALLOc: Assertion `(old_top == (((mbinptr) (((char *) &((av)->bins[((1) - 1) * 2])) - __builtin_offsetof (struct malloc_chunk, fd)))) && old_size == 0) || ((unsigned long) (old_size) >= (unsigned long)((((__builtin_offsetof (struct malloc_chunk, fd_nextsize))+((2 * (sizeof(size_t))) - 1)) & ~((2 * (sizeof(size_t))) - 1))) && ((old_top)->size & 0x1) && ((unsigned long)old_end & pagemask) == 0)' failed.
Aborted (core dumped)

gdb を使用して「バックトラック」すると、次のようになります。

#0  0x00007ffff7753445 in __GI_raise (sig=<optimized out>) at ../nptl/sysdeps/unix/sysv/linux/raise.c:64
#1  0x00007ffff7756bab in __GI_abort () at abort.c:91
#2  0x00007ffff779abed in __malloc_assert (assertion=<optimized out>, file=<optimized out>, line=<optimized out>, function=<optimized out>) at malloc.c:300
#3  0x00007ffff779e0f4 in sYSMALLOc (av=0x7ffff7ad3720, nb=32) at malloc.c:2448
#4  _int_malloc (av=0x7ffff7ad3720, bytes=12) at malloc.c:3892
#5  0x00007ffff779fa45 in __GI___libc_malloc (bytes=12) at malloc.c:2924
#6  0x00007ffff7b8fded in operator new(unsigned long) () from /usr/lib/x86_64-linux-gnu/libstdc++.so.6
#7  0x00007ffff7b8ff09 in operator new[](unsigned long) () from /usr/lib/x86_64-linux-gnu/libstdc++.so.6
#8  0x0000000000400b12 in mergesort (array=0x603010, n=7) at jedan.cpp:81
#9  0x0000000000400cfe in main () at jedan.cpp:120

配列 [1 2 3 4 5 6 7 8 9 10] に対して同様のことを行います (ただし、同じではありません!)。ここでも new および delete[] 関数に接続されています。誰かが役に立つと思ったら、後でここに投稿できますが、この投稿をあまり肥大化させたくありません. そして、私が試したほとんどの配列で機能します（サイズ<= 6の配列、およびかなり大きな数の配列で問題はありませんでした）。

昨日インストールしたUbuntu 12.04を使用しています...かなりきれいで新鮮です。ヘルプ？

PS変数名が少し変だと思ったら、ごめんなさい...コードを読みやすくするために母国語から翻訳しました。

4

3 に答える 3

5 
int n;
int *array = new int[n]; // Undefined behavior

nここでは初期化されていないため、「ランダムな」長さの割り当てが得られます。

運が悪くn、「大きな」ガベージ値を保持している場合、コードが機能しているように見える可能性があります。保持する値が小さい場合、最初の配列を埋めるときにヒープが破損する可能性があります。これにより、表示されているタイプのエラーが生成されます。

配賦cin >> n;前に行を移動します。array

補足: で行っている 2 つの割り当てmergesortがリークしていると思います (deleteで割り当てられたメモリのみを使用しています。コードを正しく読み取ればhalf、実際にはそれ自体を割り当てる必要はありません)。mergesort

于 2012-06-30T17:29:52.363 に答える
1

あなたはチェックしません

n==0

mergesort() ルーチンで。

その後、new[] は失敗します。

ところで、half() ルーチンの同じもの:

int *new_array = new int[end-start];

あなたはチェックしません

end == start
于 2012-06-30T17:30:51.930 に答える
1

配列の数量を指定していません:

int main()
{
    int n;
    int *array = new int[n];

    cin >> n;

プログラムの開始時に、 の値を指定していませんn。したがって、割り当てられるサイズは不明です。

cin >> n;配列の割り当ての前に移動することをお勧めします。

于 2012-06-30T17:31:55.813 に答える