Manipulating a global array in a recursive function

Question

I'm working through an algorithms MOOC and have a small program that takes an array A of ints in arbitrary order, counts the number of inversions (an inversion being the number of pairs (i,j) of array indices with i<j and A[i] > A[j]).

Below is the code I've written. I'm trying to tackle it using a "divide and conquer" approach where we recursively split the input array into two halves, sort each half individually while counting the inversions and then merge the two halves.

The trick is I need to keep track of the number of inversions and sort the arrays, so I pass the original array around the various recursive calls as an argument to the function and pass the count of inversions as a return value.

The code executes correctly through the first set of recursive calls that successively divide and sort [1,5,3], however when I get to the 3rd invocation of mergeAndCountSplitInv it crashes at the line:

sortedArrayLeft = realloc(sortedArrayLeft, sizeof(int)*(rightLen + leftLen));

with the error:

malloc: *** error for object 0x100103abc: pointer being realloc'd was not allocated

I can't see where I'm not using malloc correctly and I've combed through this checking to see I'm doing the pointer arithmetic correctly and can't spot any errors, but clearly error(s) exist.

Any help is appreciated.

//  main.c
//  inversionInC

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

// function to help with debugging array/pointer arithmetic
void logArrayLenAndContents (char *arrayName, int arrayToPrint[], int arrayLen){
    printf("%s\n", arrayName);
    printf("len:%d\n", arrayLen);
    for (int idx = 0; idx < arrayLen; idx++) {
        printf("array[%d]: %d\n", idx, arrayToPrint[idx]);
    }
}

int mergeAndCountSplitInv(int sortedArrayLeft[], int leftLen, int sortedArrayRight[], int rightLen)
{
    printf("Calling mergeAndCount with sortedArrayLeft:\n");
    logArrayLenAndContents("left Array", sortedArrayLeft, leftLen);
    printf("...and sortedArrayRight:\n");
    logArrayLenAndContents("right Array", sortedArrayRight, rightLen);

    int i = 0;
    int j = 0;
    int k = 0;
    int v = 0; // num of split inversions

    int* outArray;
    outArray = malloc((leftLen + rightLen) * sizeof(int));

    while (i < leftLen && j < rightLen) {
        if (sortedArrayLeft[i] < sortedArrayRight[j]) {
            outArray[k] = sortedArrayLeft[i];
            i++;
        } else{
            outArray[k] = sortedArrayRight[j];
            v += leftLen - i;
            j++;
        }
        k++;
    }
    // if at the end of either array then append the remaining elements
    if (i < leftLen) {
        while (i < leftLen) {
            outArray[k] = sortedArrayLeft[i];
            i++;
            k++;
        }
    }

    if (j < rightLen) {
        while (j < rightLen) {
            outArray[k] = sortedArrayRight[j];
            j++;
            k++;
        }
    }

    printf("Wrapping up mergeAndCount where outArray contains:\n");
    logArrayLenAndContents("outArray", outArray, k);

    sortedArrayLeft = realloc(sortedArrayLeft, sizeof(int)*(rightLen + leftLen));
    return v;
}

int sortAndCount(int inArray[], int inLen){
    printf("Calling sortAndCount with:\n");
    logArrayLenAndContents("inArray", inArray, inLen);

    if (inLen < 2) {
        return 0;
    }

    int inArrayLenPart1 = ceil(inLen/2.0);
    int inArrayLenPart2 = inLen - inArrayLenPart1;

    int* rightArray = malloc(sizeof(int) * inArrayLenPart2);
    rightArray = &inArray[inArrayLenPart1];

    int x = sortAndCount(inArray, inArrayLenPart1);
    printf("sortAndCount returned x = %d\n\n", x);
    int y = sortAndCount(rightArray, inArrayLenPart2);
    printf("sortAndCount returned y = %d\n\n", y);

    int z = mergeAndCountSplitInv(inArray, inArrayLenPart1, rightArray, inArrayLenPart2);
    printf("mergeAndCount returned z = %d\n", z);
    return x+y+z;
}

int main(int argc, const char * argv[])
{
    static int* testArray;
    testArray = malloc(5 * sizeof(int));
    for (int i = 0; i<=4; i++) {
        testArray[0] = 1;
        testArray[1] = 5;
        testArray[2] = 3;
        testArray[3] = 2;
        testArray[4] = 4;
    }

    int x = sortAndCount(testArray, 5);
    printf("x = %d\n", x);
    return 0;
}

int* rightArray = malloc(sizeof(int) * inArrayLenPart2);rightArray = &inArray[inArrayLenPart1]; : wrong. rightArray rewrite by part of inArray. it's not malloced address(not return of malloc , So can't realloc). — BLUEPIXY
– BLUEPIXY, Commented May 19, 2014 at 14:58
Note: you're making this difficult. The logic of counting inversions is correct (distance of a right-parittion value from mid-left elements). But you should know you needn't realloc, or locally alloc merge-space. A non-in-place merge sort (which is all this really is) needs no more than N temp space for N elements, and a creative parameter passing algorithm and pointer arithmetic will do the job with one allocation at the onset. See it live, and best of luck. — WhozCraig
– WhozCraig, Commented May 19, 2014 at 15:35
@WhozCraig Btw, the way you handle the copying over of the remaining elements on lines 25 and 26 is beautifully clever. Thanks again for this. — Nick
– Nick, Commented May 23, 2014 at 16:08
@Nick Don't try it with anything besides a POD-type if you do it in C++. Use std::copy in that case (though if all you care about is inversion detection sorting a pointer array and leaving the vector of objects untouched is probably warranted in that case). Glad you got some use out of it. — WhozCraig
– WhozCraig, Commented May 23, 2014 at 17:28

Sergey Kalinichenko · Accepted Answer · 2014-05-19 14:59:38Z

3

This happens because the value of sortedArrayLeft gets lost as soon as the function returns. The realocated value does not make it to the caller, so inArray of the sortAndCount may be pointing to freed memory if realloc needs to reallocate and copy.

In order to fix this, pass a pointer to the pointer, letting sortedArrayLeft to propagate back to inArray of sortAndCount:

int mergeAndCountSplitInv(int **sortedArrayLeft, int leftLen, int sortedArrayRight[], int rightLen) {
    ...
    *sortedArrayLeft = realloc(*sortedArrayLeft, sizeof(int)*(rightLen + leftLen));
    return v;
}
...
int sortAndCount(int **inArray, int inLen) {
    ...
    int z = mergeAndCountSplitInv(inArray, inArrayLenPart1, rightArray, inArrayLenPart2);
}
...
int x = sortAndCount(&testArray, 5);

answered May 19, 2014 at 14:59

Sergey Kalinichenko

729k85 gold badges1.2k silver badges1.6k bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Manipulating a global array in a recursive function

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related