Results 1 to 2 of 2

Math Help - Using MergeSort to count Inversions

  1. #1
    Newbie
    Joined
    Feb 2007
    Posts
    16

    Using MergeSort to count Inversions

    Hey folks!

    I'm trying to count inversions in a list using MergeSort. I've got MergeSort functioning properly, but can't figure out how and when to update the Inversion count in Merge. Here's my code:

    Code:
    int SortAndCount(int arr_list[], int leftSize, int rightSize)
    {
            int invLeft=0, invRight=0, invBoth=0;
    
            if(leftSize < rightSize)
            {
                    int middleValue = (leftSize+rightSize) / 2;
                    invLeft = SortAndCount(arr_list, leftSize, middleValue);
                    invRight = SortAndCount(arr_list, middleValue+1, rightSize);
                    invBoth = MergeAndCount(arr_list, leftSize, rightSize);
    
            }
            return invLeft + invRight + invBoth;
    }
    
    int MergeAndCount(int arr_List[], int leftSize, int rightSize)
    {
            int newSize = rightSize - leftSize + 1;
            int middleValue = (rightSize + leftSize) /2;
            int Inversions=0, totalInv=0;
    
            int *tempArray = new int[newSize];
            int posistion=0;
            int i, j, placement=0;
    
            for(i=leftSize; i<=middleValue; i++, posistion++)
            {
                    tempArray[posistion]=arr_List[i];
            }
            for(i=rightSize; i >= middleValue+1; i--, posistion++)
            {
                    tempArray[posistion]=arr_List[i];
            }
            for(i=0,j=newSize-1, placement=leftSize; i<=j; placement++)
            {
                    if(tempArray[i]<=tempArray[j])
                    {
                            arr_List[placement]=tempArray[i];
    
                            i++;
    
                    } else {
    
                            Inversions = Inversions + ( i - j);
                            arr_List[placement] = tempArray[j];
                            j--;
    
                    }
    
            }
            delete[] tempArray;
            return Inversions;
    }
    I know that Inversions must be incremented by the amount of items remaining in the first list, when the number in the second list is smaller then the second list, but I cannot get out the correct answer.

    Any help is appreicated! Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    I do not know if this helps, but there is a another way to count inversions. Through Premutation Groups.
    The degree of a premutation determines if an inversion is even or odd.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Number of inversions
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: November 14th 2010, 12:04 PM
  2. Inversions
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 31st 2010, 02:12 PM
  3. Proof regarding inversions
    Posted in the Geometry Forum
    Replies: 0
    Last Post: March 11th 2010, 02:12 PM
  4. Another IRV question... Inversions
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: February 25th 2009, 03:49 PM
  5. Inversions of a permutation
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 29th 2008, 01:22 PM

Search Tags


/mathhelpforum @mathhelpforum