0

In the code below, I initialized L, R and array like this:

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

for (i = 1; i <= n1; i++){
    L[i] = A[p + i - 1];
}

for (j = 1; j <= n2; j++){
    R[j] = A[q + j];
}


int *array = (int *) malloc(sizeof(int) * n);

...
for (c = 0; c < n; c++){
    scanf("%d", &array[c]);
}

but got a segfault. Could you tell me what's wrong with this initialization please?

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

void merge(int *A, int p, int q, int r)
{
    int n = r - p + 1; /* number of elements in array A */
    int n1 = q - p + 1;
    int n2 = r - q;
    printf("n2 = %d\n",n2);
    int  i, j, k;

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

    for (i = 1; i <= n1; i++){
        L[i] = A[p + i - 1];
    }

    for (j = 1; j <= n2; j++){
        R[j] = A[q + j];
    }

    L[n1+1] = INT_MAX;
    R[n2+1] = INT_MAX;

    i = 1;
    j = 1;

    printf("p = %d\n",p);
    printf("r = %d\n",r);

    for (k = p; k <= r; k++){
        printf("k=%d\n",k);
        if (L[i] <= R[j]){
            A[k] = L[i];
            i += 1;
        }

        else{
            A[k] = R[j];
            j += 1;
        }
    }

    free(L);
    free(R);
}

void merge_sort(int *A, int p, int r)
{
    int i;
/*  for (i=0; i<=r-p;i++){
        printf("%d\n",A[i]);
    }*/
    int q;
    if (p < r){
    /*  printf("merge_sort p = %d\n",p);
        printf("merge_sort r = %d\n",r);*/
        q = (p + r)/2;
/*      printf("q = %f\n",q);*/
        merge_sort(A, p, q);
        merge_sort(A, q+1, r);
/*      printf("done\n");*/
        merge(A, p, q, r);
    }
}


int main()
{
    int x, c;
    int n;
    int *array = (int *) malloc(sizeof(int) * n);
    printf("Enter number of elements\n");
    scanf("%d",&n);

    printf("Enter %d elements\n",n);

    for (c = 0; c < n; c++){
        scanf("%d", &array[c]);
    }

    merge_sort(array, 0, n-1);

    for (c = 0; c < n; c++){
        printf("%d\n", array[c]);
    }

    free(array);
    return 0;
}
Community
  • 1
  • 1
bigTree
  • 2,103
  • 6
  • 29
  • 45
  • 3
    `for (i = 1; i <= n1; i++){` --> `for (i = 0; i < n1; i++){` : Arrays in C is `0` origin. when `int *L = (int *) malloc(sizeof(int) * n1);` : {index | 0 <= index < n1} , `L[n1+1] = INT_MAX;` : access of out of range – BLUEPIXY Jul 24 '14 at 23:23
  • 1
    @BLUEPIXY, seems an answer to me. – David Ranieri Jul 24 '14 at 23:27
  • 1
    Just some side notes... There is no need to typecast the returned value from malloc in C (and many feel that doing so will [work against you](http://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc)). Also, you should check if your call to `malloc()` was successful. For example, `if (L == NULL) printf("malloc failed");` and then handle the failure. – embedded_guy Jul 24 '14 at 23:35
  • @embedded_guy great thanks. I had a problem with the initialization of array because n was not defined... – bigTree Jul 24 '14 at 23:44

3 Answers3

2

You malloc memory for n1 and n2 ints in L and R, respectively. This makes it valid to write indices L[0] through L[n1 - 1] and R[0] through R[n2 - 1], inclusive, but your loops write to L[n1] and R[n2] due to the conditions being i<=n1 and j<=n2. Change the start to 0 for each loop and remove the =s from each end condition.

(It is also a good idea to check your other code for the same error, i.e., remember that 0 is the first index and it counts towards the length of the array.)

Arkku
  • 41,011
  • 10
  • 62
  • 84
1

First index of each array is always 0.

array: int tab[3];
elements: tab[0], tab[1], tab[2]

There is no element tab[3] (seg fault).

It is interesting that your loop in main(...) function is written correct, but 2 other in merge(...) have different idea to iterate through array.

Dakorn
  • 883
  • 6
  • 11
1

You might want to take a look at memset()