Triggered a Breakpoint?

[BlueChinchillaEatingDorito]

I'm currently tasked to implement an algorithm for Merge sort in this C++ Computing Course I'm taking right now. When I run the built executable, I get "____.exe has triggered a breakpoint." and is pointing to this in malloc.c

 

__forceinline void * __cdecl _heap_alloc (size_t size)

{

    if (_crtheap == 0) {
        _FF_MSGBANNER();    /* write run-time error banner */

        _NMSG_WRITE(_RT_CRT_NOTINIT);  /* write message */
        __crtExitProcess(255);  /* normally _exit(255) */
    }

    return HeapAlloc(_crtheap, 0, size ? size : 1);
}

 

I'm pretty sure it has to do with the way I'm allocating my dynamic arrays for merging as it's one of the last items on the call stack. My implementation for creating the dynamic array is as follows. Am I doing this right? I'm using template<class T>  as this has to work for strings, integers, and floats. 

 

int R_side = mid - low;
int L_side = high - (mid+1);
int copy_count;
T* R_arr;
T* L_arr;
    
R_arr = new T[R_side];
T_arr = new T[L_side];

 

Many thanks!

[fizzlesticks]

33 minutes ago, BlueChinchillaEatingDorito said:

T_arr = new T[L_side];

Is that supposed to be L_arr? 

Would help if you posted the full function.

[BlueChinchillaEatingDorito]

2 minutes ago, fizzlesticks said:

Is that supposed to be L_arr? 

Would help if you posted the full function.

Made a typo as I was formatting it on here. Whoops.

Disclaimer: I know this is probably implemented in the terrible manner, but I'm still a beginner so bare with me.

Spoiler

template <class T>
int Mergesort(T arr[], int n)
{
    int counter = 0;
    if( arr != NULL )
    {
        int mid = floor((n-1)/2);
        MergesortHelper( arr, 0, mid, n, counter);
        MergesortHelper( arr, mid+1, (n-1), n, counter);
    }
    return counter;
}

 

template <class T>
void MergesortHelper(T arr[], int low, int high, int n, int& counter)
{
    if (low < high)
    {
        int mid = low + floor((high - low)/2);
        MergesortHelper( arr, low, mid, n, counter);
        MergesortHelper( arr, mid+1, (n-1), n, counter);
        Merge( arr, low, mid, high, n, counter);
    }
    else
    {
        return;
    }
}

 

template <class T>
void Merge(T arr[], int low, int mid, int high, int n, int& counter)
{
    if ( arr == NULL )
    {
        return;
    }

 //make two temp arrays for Right and Left side, then merge
    int R_side = mid - low;
    int L_side = high - (mid+1);
    int copy_count;
    T* R_arr;
    T* L_arr;
    
    R_arr = new T[R_side];
    copy_count = 0;
    for ( int i = low; i <= mid; i++ )
    {
        R_arr[copy_count] = arr;
        copy_count++;
    }

    L_arr = new T[L_side];
    copy_count = 0;
    for ( int i = mid+1; i <= high; i++ )
    {
        R_arr = arr;
        copy_count++;
    }

 

    SelectionSort( R_arr, R_side);
    SelectionSort( L_arr, L_side);

    int copy_count_L = 0;
    int copy_count_R = 0;
    for ( int i = low; i <= high; i ++ )
    {
        if (R_arr[copy_count_R] < L_arr[copy_count_L])
        {
            arr = R_arr[copy_count_R];
            copy_count_R++;
        }
        else
        {
            arr = L_arr[copy_count_L];
            copy_count_L++;
        }
    }
}

 

[BlueChinchillaEatingDorito]

It's also not complete, I'm just testing up to this point to see if it works. I still have to implement the condition where if one of the sub arrays (R and L) are empty then it'll just straight copy the rest of the other. 

[fizzlesticks]

Well I can't get it to throw that error but the code certainly has quite a few issues.

 

int R_side = mid - low;
    int L_side = high - (mid+1);
    int copy_count;
    T* R_arr;
    T* L_arr;
    
    R_arr = new T[R_side];
    L_arr = new T[L_side];

In this section, when low=0 and high=1 R_side and L_side will end up being 0 which depending on your compiler may be causing the issue when you try to create an new array of size 0. Later in the code you both read and write outside the bounds of those arrays which could also be the problem. 

 

R_arr[copy_count] = arr

Is trying to assign a T[] into an array of T. I'd expect that should be R_arr[copy_count] = arr; 

Your code shouldn't even compile with that line there.

 

R_arr = arr;

I think should be L_arr[copy_count] = arr;

 

And of course you're never deleting any of the arrays you create.

That's a start at least.

 

[Nineshadow]

This is an implementation of merge sort I did quite some long time ago when I was learning sorting algorithms.

template<class t>
void merge(t *ar, int p , int q, int r){
    t lowHalf[q-p+1];
    t highHalf[r-q];
    int i, j, k = p;
    for(i=0; k<=q; i++,k++) lowHalf[i] = ar[k];
    for(j =0; k<=r; j++,k++) highHalf[j] = ar[k];
    k = p;    i = 0;    j = 0;
    while((i < q-p+1) && (j < r-q))    {
        if(lowHalf[i] <= highHalf[j])
        {
            ar[k] = lowHalf[i++];
        }
        else
        {
            ar[k] = highHalf[j++];
        }
        k++;
    }
    while(i < q-p+1)    {
        ar[k++] = lowHalf[i++];
    }
    while(j < r-q)    {
        ar[k++] = highHalf[j++];
        }
}
template<class t>
void mergeSort(t *ar, int p, int r){
    if(p < r)    {
        int q = (p + r)/2;
        mergeSort(ar,p,q);
        mergeSort(ar,q+1,r);
        merge(ar, p, q ,r);   
        }
}

 

[BlueChinchillaEatingDorito]

6 hours ago, Nineshadow said:

-snip-

Visual Studio is so finicky. I remember my professor said the compiler does not like variables when initialing the size of an array.

[fizzlesticks]

1 hour ago, BlueChinchillaEatingDorito said:

Visual Studio is so finicky. I remember my professor said the compiler does not like variables when initialing the size of an array.

Variable length arrays aren't in the C++ standard so most compilers don't support it. It is however in the C standard so some compilers like G++ allow it anyway.

[Nineshadow]

7 minutes ago, fizzlesticks said:

Variable length arrays aren't in the C++ standard so most compilers don't support it. It is however in the C standard so some compilers like G++ allow it anyway.

Yeah.

If your compiler doesn't let you do it then just use dynamically allocated arrays.

[BlueChinchillaEatingDorito]

On ‎2016‎-‎02‎-‎21 at 0:40 PM, Nineshadow said:

Yeah.

If your compiler doesn't let you do it then just use dynamically allocated arrays.

 int L_side = mid - low +1;
 int R_side = high - mid +1;
 
 T* L_arr;
 T* R_arr;

 

 L_arr = new T[L_side];
 R_arr = new T[R_side];

 

It's not allowing me to do this. I've checked with my friend who also took this course and said there shouldn't be an issue. It compiles and runs will encounter a bad::alloc during execution. Trying to access the array will result in an access violation, encounter a breakpoint, then corrupt the heap. Really at a loss right now.