Inversions in a matrix

Question

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

static void merge(int *array, int start, int mid, int end, int *count){
    int *leftarray = (int *)calloc(sizeof(int), mid-start+2);
    int *rightarray = (int *)calloc(sizeof(int), end-mid+2);
    int i,j = 0,k=0;
    for (i = start; i <= mid; i++){
        leftarray[j++] = array[i];
    }
    leftarray[j] = 2147483647;
    j = 0;
    for (i = mid + 1; i <= end; i++){
        rightarray[j++] = array[i];
    }
        rightarray[j] = 2147483647;
        j = 0;
        for (i = start; i <= end; i++){
            if (leftarray[j] <= rightarray[k]){
                array[i] = leftarray[j];
                j++;
            }
            else {
                array[i] = rightarray[k];
                k++;
                if (i != end){
                    *count += mid + 1 - start - j;
                }
            }

        }
}

static void display(int *array, int size){
    for (int i = 0; i<size; i++){
        printf("%d ", array[i]);
    }
    printf("\n");
}

static void mergeSort(int *array, int start, int end, int *count){
    if (start >= end){
        return;
    }
    int mid = (start + end) / 2;
    mergeSort(array, start, mid, count);
    mergeSort(array, mid + 1, end, count);
    merge(array, start, mid, end, count);
}
int mergesort() {
int n;
long long int count = 0;
//scanf("%d", &n);
int * array = (int *)calloc(sizeof(int), 100005);
int number = 199999;
for (int i = 0; i < 100000; i++){
    array[i] = number--;
}
/*for (int i=0; i<n; i++){
    scanf("%d", &array[i]);
}*/
mergeSort(array, 0, 100000 - 1, &count);
/*display(array, n);*/
printf("%d\n", count);
return 0;
}

int main(){
    mergesort();
    return 0;
}

I am trying to solve this problem from geeksforgeeks (https://www.geeksforgeeks.org/counting-inversions/) and implemented the following code but it gives wrong result for the above input values the reverse sorted array from 199999 to 100000 instead of getting result as 4999950000 i am getting some other result i tried debugging but it was useless can anyone tell me where did i go wrong

[Don't cast the result of `malloc` family in C](https://stackoverflow.com/q/605845/995714). And why don't you free the memory after use? — phuclv, Aug 21 '18 at 16:57
thanks for the suggestion @phuclv also are you able to spot the logical error in the code why am i getting the wrong answer — Rock star, Aug 21 '18 at 17:07

score 3 · Answer 1 · answered Aug 21 '18 at 17:01

3

You declare count as long long int count = 0; but then you pass it around &count as if it were only an int *. Try fixing the functions where you pass &count to take a long long int *.

I think the result you're getting is 704982704

answered Aug 21 '18 at 17:01

cleblanc

3,678
1
13
16

ya that's the answer i am getting which is wrong.The answer should be 4999950000 – Rock star Aug 21 '18 at 17:04

score 0 · Answer 2 · edited Aug 21 '18 at 22:28

0

I think you should use long int, because you are using values that are greater than the size of an int.

edited Aug 21 '18 at 22:28

Robert Columbia

6,313
15
32
40

answered Aug 21 '18 at 16:53

Gaurav Pawar

1
2

1

this isn't an answer. And long may have the same size as int, for example in 32-bit systems and on 64-bit Windows – phuclv Aug 21 '18 at 16:58

Inversions in a matrix

2 Answers2