Forums: » Register « |  Free Tools |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support |

New Free Tools on Dev Shed!

#1
July 2nd, 2013, 06:39 PM
 help_desk
Registered User

Join Date: Jul 2013
Posts: 14
Time spent in forums: 2 h 42 m 59 sec
Reputation Power: 0
Inversion in mergesort

Hello,
I am trying to implement the number of inversion in an array with entries {2,4,1,3,5}

On paper, this array will yield 3 inversions (2,1) (4,1) (4,3)

but with my code, it yields 5. where am I getting it wrong?

Code:
```int mergeSort(int arr[], int array_size)
{
int *temp = (int *)malloc(sizeof(int)*array_size);
return mergesort(arr, temp, 0, array_size - 1);
}

int mergesort(int arr[], int temp[], int left, int right)
{
int mid;
int  inv_count = 0;
if (right > left)
{

mid = (right + left)/2;
inv_count  = mergesort(arr, temp, left, mid);
inv_count += mergesort(arr, temp, mid+1, right);
inv_count += merge(arr, temp, left, mid+1, right);
}
return inv_count;

}

int merge(int arr[],  int temp[], int left, int mid, int right)
{
int i, j, k;
int inv_count = 0;

i = left; /* i is index for left subarray*/
j = mid;  /* i is index for right subarray*/
k = left; /* i is index for resultant merged subarray*/
while ((i <= mid - 1) && (j <= right))
{
if (arr[i] <= arr[j])
{
temp[k++] = arr[i++];
}
else
{
temp[k++] = arr[j++];
inv_count = inv_count + (mid - i);
}
}

/* Copy the remaining elements of left subarray
(if there are any) to temp*/
while (i <= mid - 1)
temp[k++] = arr[i++];

/* Copy the remaining elements of right subarray
(if there are any) to temp*/
while (j <= right)
temp[k++] = arr[j++];

/*Copy back the merged elements to original array*/
for (i=left; i <= right; i++)
arr[i] = temp[i];

return inv_count;
}```

#2
July 2nd, 2013, 07:38 PM
 b49P23TIvg
Contributing User

Join Date: Aug 2011
Posts: 4,169
Time spent in forums: 1 Month 3 Weeks 2 Days 10 h 13 m
Reputation Power: 455
Your program works as you expect.
Code:
```#if 0
-*- mode: compilation; default-directory: "/tmp/" -*-
Compilation started at Tue Jul  2 19:34:39

a=./c && make -k \$a && \$a
cc -Wall -g c.c -o c
2  4  1  3  5
INVERSIONS: 3
1  2  3  4  5

Compilation finished at Tue Jul  2 19:34:39
#endif

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

#define DIM(A) (sizeof((A))/sizeof(*(A)))

int merge(int arr[],  int temp[], int left, int mid, int right) {
int i, j, k;
int inv_count = 0;
i = left; /* i is index for left subarray*/
j = mid;  /* i is index for right subarray*/
k = left; /* i is index for resultant merged subarray*/
while ((i <= mid - 1) && (j <= right))
if (arr[i] <= arr[j])
temp[k++] = arr[i++];
else {
temp[k++] = arr[j++];
inv_count = inv_count + (mid - i);
}
/* Copy the remaining elements of left subarray (if there are any) to temp*/
while (i <= mid - 1)
temp[k++] = arr[i++];
/* Copy the remaining elements of right subarray (if there are any) to temp*/
while (j <= right)
temp[k++] = arr[j++];
/*Copy back the merged elements to original array*/
for (i=left; i <= right; i++)
arr[i] = temp[i];
return inv_count;
}

int mergesort(int arr[], int temp[], int left, int right) {
int mid;
int  inv_count = 0;
if (right > left) {
mid = (right + left)/2;
inv_count  = mergesort(arr, temp, left, mid);
inv_count += mergesort(arr, temp, mid+1, right);
inv_count += merge(arr, temp, left, mid+1, right);
}
return inv_count;
}

int mergeSort(int arr[], int array_size) {
int *temp = (int *)malloc(sizeof(int)*array_size);
return mergesort(arr, temp, 0, array_size - 1);
}

void display(int*a,int n) {
int i;
for (i = 0; i < n; ++i)
printf("%3d",a[i]);
putchar('\n');
}

int a[] = {2,4,1,3,5};

int main() {
display(a, DIM(a));
printf("INVERSIONS: %d\n",mergeSort(a,DIM(a)));
display(a, DIM(a));
return 0;
}```
__________________
[code]Code tags[/code] are essential for python code!

#3
July 3rd, 2013, 03:51 AM
 help_desk
Registered User

Join Date: Jul 2013
Posts: 14
Time spent in forums: 2 h 42 m 59 sec
Reputation Power: 0
How about if you test it over this set of .txt file? What is the number of inversion that you got? Here is a link to the .txt file: http://txtup.net/HaGYX. I got an overflow and I tried using long long on the inv_counter but that didn't solve the problem either..

#4
July 3rd, 2013, 11:20 AM
 dwise1_aol
Contributing User

Join Date: Jan 2003
Location: USA
Posts: 6,865
Time spent in forums: 3 Months 1 Day 7 h 36 m 3 sec
Reputation Power: 2199
The largest value in that file is 99973, well within the range of long or even of a 32-bit int.

I took your program completely as-is, compiled it and got no errors or warnings, and ran it against your own data file. this is what I got:
Quote:
 C:TEST\help_desk>gcc -Wall mergesort.c C:TEST\help_desk>a 2 4 1 3 5 INVERSIONS: 3 1 2 3 4 5 C:TEST\help_desk>

Why are you the only one who is always having problems with the exact-same code and data that we can use without a problem?

What compiler and OS are you using? I just used MinGW gcc version 2.95.3-6 (mingw special) under WinXP Pro.

Last edited by dwise1_aol : July 3rd, 2013 at 11:22 AM.

#5
July 4th, 2013, 10:43 PM
 b49P23TIvg
Contributing User

Join Date: Aug 2011
Posts: 4,169
Time spent in forums: 1 Month 3 Weeks 2 Days 10 h 13 m
Reputation Power: 455
Quote:
 Why are you the only one who is always having problems with the exact-same code and data that we can use without a problem?

A pertinent question. It was I who was dumb enough to complete the program. This may be part of the answer.

 Viewing: Dev Shed Forums > Programming Languages > C Programming > Inversion in mergesort