CODEWITHSUNDEEP
cmallocrealloc
Husso
Husso

Reputation: 272

Debug assertion failed _crtisValidHeapPointer(block)

I'm trying to implement quick sort in c/c++ and I keep getting this error, "Debug assertion failed _crtisValidHeapPointer(block)" anytime I run the code.

My code is: 

void QuickSort(int *A, int size) {
if (size < 2) return;
int *L = NULL, *R = NULL, RSize = 0, LSize = 0;

R = (int *)malloc(sizeof(int));
L = (int *)malloc(sizeof(int));

for (int i = 0; i < size; i++) {
    if (A[size - 1] <= A[i]) 
        if( ((int *)realloc(R, (sizeof(int) * (RSize + 2) ))) != NULL )
            R[RSize++] = A[i];
    else 
        if ( ((int *)realloc(L, (sizeof(int) * (LSize + 2) ))) != NULL )
            L[LSize++] = A[i];
}

    QuickSort(L, LSize);
    QuickSort(R, RSize);
    Merge(A, L, R, LSize, RSize);
    free(L);
    free(R);
    return;
}

I know it has to do with the memory allocation of my arrays L and R, but I can't seem to figure out what the problem is exactly.

EDIT: Solution found

Code: 

void QuickSort(int *A, int size) {
if (size < 2) return;
int *L = NULL, *R = NULL, RSize = 0, LSize = 0;

for (int i = 0; i < size; i++) {
    if (A[size - 2] < A[i]) {
        if ((R = (int *)realloc(R, (sizeof(int) * (RSize + 1)))) != NULL) 
            R[RSize++] = A[i];
    }
    else {
        if ((L = (int *)realloc(L, (sizeof(int) * (LSize + 1)))) != NULL) 
            L[LSize++] = A[i];
    }
}
     QuickSort(L, LSize);
     QuickSort(R, RSize);
     Merge(A, L, R, LSize, RSize);
     free(L);
     free(R);
     return;
}

Upvotes: 0

Views: 9692

Answers (2)

Ryan Bemrose
Ryan Bemrose

Reputation: 9266

The problem is here:

if( ((int *)realloc(R, (sizeof(int) * (RSize + 2) ))) != NULL )
    R[RSize++] = A[i];

The realloc function returns the new array pointer, which is compared to NULL inside the if, and then discarded. Then the original (invalid) pointer is dereferenced, corrupting the heap.

To fix, be sure to assign the result of realloc to the pointer.

if( (R = (int *)realloc(R, (sizeof(int) * (RSize + 2) ))) != NULL )

You should also include some error checking to abort the loop, in case the allocation fails, in the form of an else statement to this if. As currently written, if realloc fails then the loop will continue to completion, skipping the array on each iteration, and then return a corrupted result.

Upvotes: 2

Zbynek Vyskovsky - kvr000
Zbynek Vyskovsky - kvr000

Reputation: 18845

Well, there is allocation only for single int to both variables L and R. But later in the code you assign many integers as the LSize and RSize is incremented. Well, I see realloc is called but the result is not assigned back to L and R so this causes issues.

Anyway the quicksort algorithm may very well work on the original array, there is no reason to allocate new temporary arrays for it.

Upvotes: 2

Related Questions