CODEWITHSUNDEEP
javaalgorithmsortingmergesort
Ryan
Ryan

Reputation: 135

Need help count inversions with merge sort

The following code counts inversions in an array nums (pairs i,j such that j>i && nums[i] > nums[j]) by merge sort.

Is it possible to use the same approach to count the number of special inversions like j>i && nums[i] > 2*nums[j]?

How should I modify this code?

public static void main (String args[])
{
    int[] nums = {9, 16, 1, 2, 3, 4, 5, 6};
    System.out.println("Strong Inversions: " + countInv(nums));         
}

public static int countInv(int nums[])
{  
    int mid = nums.length/2;
    int countL, countR, countMerge;

    if(nums.length <= 1)
    {
        return 0;
    }

    int left[] = new int[mid];
    int right[] = new int[nums.length - mid];

    for(int i = 0; i < mid; i++)
    {
        left[i] = nums[i];
    }

    for(int i = 0; i < nums.length - mid; i++)
    {
        right[i] = nums[mid+i];
    }

    countL = countInv (left);
    countR = countInv (right);

    int mergedResult[] = new int[nums.length];
    countMerge = mergeCount (left, right, mergedResult);

    for(int i = 0; i < nums.length; i++)
    {
        nums[i] = mergedResult[i];
    }

    return (countL + countR + countMerge);
}


public static int mergeCount (int left[], int right[], int merged[])
{
    int a = 0, b = 0, counter = 0, index=0;

    while ( ( a < left.length) && (b < right.length) )
    {
        if(left[a] <= right[b])
        {
            merged [index] = left[a++];
        }
        else 
        {   
            merged [index] = right[b++];
            counter += left.length - a;
        }
        index++;
    }

    if(a == left.length)
    {
        for (int i = b; i < right.length; i++)
        {
            merged [index++] = right[i];
        }
    }
    else
    {
        for (int i = a; i < left.length; i++)
        {
            merged [index++] = left[i];
        }
    }
    return counter;
}

I tried this

while ((a < left.length) && (b < right.length)) {
    if (left[a] <= right[b]) {
        merged[index] = left[a++];
    } else {
        if (left[a] > 2 * right[b]) {
            counter += left.length - a;
        }
        merged[index] = right[b++];
    }
    index++;
}

but there's a bug in the while loop, when left[a]<2*right[b] but left[a+n] maybe>2*right[b], for instance left array is {9,16} and right array is {5,6}, 9<2*5 but 16>2*5. My code just skip cases like this and the result number is less than it should be

Upvotes: 1

Views: 1071

Answers (2)

R2B2
R2B2

Reputation: 1597

    while ( ( a < left.length) && (b < right.length) ) {
        if(left[a] <= right[b]) {
            merged [index] = left[a++];
        } else {
            counter += updateCounter(right[b],a,left);
            merged [index] = right[b++];
        }
        index++;
        //Rest of the while loop
    }
    //Rest of the mergeCount function
}

public static int updateCounter(int toSwitch, int index, int[] array) {
    while(index < array.length) {
        if(array[index] >= 2*toSwitch)
            break;
        index++;
    }
    return array.length-index;
}

Not very efficient, but it should do the work. You initialise index with a, because elements lower than a will never will never meet the condition.

Upvotes: 0

David Eisenstat
David Eisenstat

Reputation: 65488

The while loop in mergeCount serves two functions: merge left and right into merged, and count the number of left–right inversions. For special inversions, the easiest thing would be to split the loop into two, counting the inversions first and then merging. The new trigger for counting inversions would be left[a] > 2*right[b].

The reason for having two loops is that counting special inversions needs to merge left with 2*right, and sorting needs to merge left with right. It might be possible to use three different indexes in a single loop, but the logic would be more complicated.

Upvotes: 2

Related Questions