#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2013
    Posts
    14
    Rep Power
    0

    Unhappy 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. #2
  3. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,703
    Rep Power
    480
    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 and Makefiles!
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2013
    Posts
    14
    Rep 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..
  6. #4
  7. Contributing User
    Devshed Supreme Being (6500+ posts)

    Join Date
    Jan 2003
    Location
    USA
    Posts
    7,089
    Rep Power
    2222
    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:
    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.

    And, no, we cannot read your mind for that information.
    Last edited by dwise1_aol; July 3rd, 2013 at 10:22 AM.
  8. #5
  9. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,703
    Rep Power
    480
    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.
    [code]Code tags[/code] are essential for python code and Makefiles!

IMN logo majestic logo threadwatch logo seochat tools logo