Mergesort Implementation.. Counting number of inversions in an array

Question

I'm taking an online class on Algorithms and trying to implement a mergesort implementation of finding the number of inversions in a list of numbers. But, I cant figure what Im doing wrong with my implementation as the number of inversions returned is significantly lower than the number I get while doing a brute force approach. Ive placed my implementation of the mergesort approach below

 /**
   * 
  */

 package com.JavaReference;

 import java.io.BufferedReader;
import java.io.FileReader;
 import java.io.IOException;

public class ReadFile {


public static void main(String args[]){
    int count=0;
    Integer n[];


int i=0;
    try{
    n=OpenFile();
    int num[] = new int[n.length];

    for (i=0;i<n.length;i++){
        num[i]=n[i].intValue();
    //  System.out.println( "Num"+num[i]);
    }
    count=countInversions(num);


    }
    catch(IOException e){
        e.printStackTrace();
    }

    System.out.println(" The number of inversions"+count);


}




 public static Integer[] OpenFile()throws IOException{

    FileReader fr=new FileReader("C:/IntegerArray.txt");// to put in file name.

BufferedReader textR= new BufferedReader(fr);
int nLines=readLines();
System.out.println("Number of lines"+nLines);

Integer[] nData=new Integer[nLines];
for (int i=0; i < nLines; i++) {
    nData[ i ] = Integer.parseInt((textR.readLine()));

    }
textR.close();

return nData;


}

public static int readLines() throws IOException{


FileReader fr=new FileReader("C:/IntegerArray.txt");
BufferedReader br=new BufferedReader(fr);


int numLines=0;
//String aLine;

while(br.readLine()!=null){
    numLines++;
}
System.out.println("Number of lines readLines"+numLines);
return numLines;

}

public static int countInversions(int num[]){

int countLeft,countRight,countMerge;
int mid=num.length/2,k;


if (num.length<=1){

    return 0;// Number of inversions will be zero for an array of this size.
}

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


for (k=0;k<mid;k++){
    left[k]=num[k];
}

for (k=0;k<mid;k++){
    right[k]=num[mid+k];
}

countLeft=countInversions(left);
countRight=countInversions(right);

int[] result=new int[num.length];
countMerge=mergeAndCount(left,right,result);
/*
 * Assign it back to original array.
 */
for (k=0;k<num.length;k++){
    num[k]=result[k];
}

return(countLeft+countRight+countMerge);
}
private static int mergeAndCount(int left[],int right[],int result[]){
int count=0;
int a=0,b=0,i,k=0;
while((a<left.length)&&(b<right.length)){

    if(left[a]<right[b]){
        result[k]=left[a++];// No inversions in this case.

    }
    else{// There are inversions.

        result[k]=right[b++];
        count+=left.length-a;
    }
    k++;

    // When we finish iterating through a.

if(a==left.length){
    for (i=b;i<right.length;i++){
        result[k++]=right[b];

    }

    }
else{
    for (i=a;i<left.length;i++){

    }
}






}


return count;
  }
  }

I'm a beginner in Java and Algorithms so any insightful suggestions would be great!

Isn't this the problem from the Stanford online course. You should tag this as Homework. — nikhil, Mar 19 '12 at 06:08
I'm out right now, if no one posts an answer then I'll look into this. — nikhil, Mar 19 '12 at 06:25
http://stackoverflow.com/questions/337664/counting-inversions-in-an-array — nikhil, Mar 19 '12 at 06:27

score 6 · Accepted Answer · answered Mar 19 '12 at 07:38

I found two bugs:

In countInversions(), when num is split into left and right you assume right has m elements. When num.length is odd, however, it will be m + 1 elements. The solution is to use right.length instead of m.
In mergeAndCount(), handling of the bit where one subarray is empty and the other one still has some elements is not done correctly.

Side note:
There is absolutely no reason to use Integer in your program, except for the Integer.parseInt() method (which, by the way, returns an int).

Corrected code:

/**
*
*/

package com.JavaReference;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;

public class ReadFile {

    public static void main(String args[]){
        int count=0;
        Integer n[];

        int i=0;
        try{
            n=OpenFile();
            int num[] = new int[n.length];

            for (i=0;i<n.length;i++){
                num[i]=n[i].intValue();
                // System.out.println( "Num"+num[i]);
            }
            count=countInversions(num);

        }
        catch(IOException e){
            e.printStackTrace();
        }

        System.out.println(" The number of inversions"+count);

    }

    public static Integer[] OpenFile()throws IOException{

        FileReader fr=new FileReader("C:/IntegerArray.txt");// to put in file name.

        BufferedReader textR= new BufferedReader(fr);
        int nLines=readLines();
        System.out.println("Number of lines"+nLines);

        Integer[] nData=new Integer[nLines];
        for (int i=0; i < nLines; i++) {
            nData[ i ] = Integer.parseInt((textR.readLine()));

        }
        textR.close();

        return nData;

    }

    public static int readLines() throws IOException{

        FileReader fr=new FileReader("C:/IntegerArray.txt");
        BufferedReader br=new BufferedReader(fr);

        int numLines=0;
        //String aLine;

        while(br.readLine()!=null){
            numLines++;
        }
        System.out.println("Number of lines readLines"+numLines);
        return numLines;

    }

    public static int countInversions(int num[]){

        int countLeft,countRight,countMerge;
        int mid=num.length/2,k;

        if (num.length<=1){

            return 0;// Number of inversions will be zero for an array of this size.
        }

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

        for (k=0;k<mid;k++){
            left[k]=num[k];
        }

        // BUG 1: you can't assume right.length == m
        for (k=0;k<right.length;k++){
            right[k]=num[mid+k];
        }

        countLeft=countInversions(left);
        countRight=countInversions(right);

        int[] result=new int[num.length];
        countMerge=mergeAndCount(left,right,result);
        /*
        * Assign it back to original array.
        */
        for (k=0;k<num.length;k++){
            num[k]=result[k];
        }

        return(countLeft+countRight+countMerge);
    }
    private static int mergeAndCount(int left[],int right[],int result[]){
        int count=0;
        int a=0,b=0,i,k=0;
        while((a<left.length)&&(b<right.length)){

            if(left[a]<right[b]){
                result[k]=left[a++];// No inversions in this case.

            }
            else{// There are inversions.

                result[k]=right[b++];
                count+=left.length-a;
            }
            k++;
        }

        // BUG 2: Merging of leftovers should be done like this
        while (a < left.length)
        {
            result[k++] = left[a++];
        }
        while (b < right.length)
        {
            result[k++] = right[b++];
        }

        return count;
    }
}

Thank you for the reply! I was able to understand the first bug you pointed out and still trying to figure out how the merging of leftovers happens, however I get an answer that's different from the one I get through brute force(both are of the same order though).Kinda weird :S — seeker, Mar 19 '12 at 08:43
@KodeSeeker When the big while loop ends, either `a == left.length` or `b == right.length`. One sublist will be completely 'used up', while the other will still have some unprocessed elements. These leftover elements will not affect `count`, so they are simply appended to `result`. Instead of doing a check to see which array has the leftover elements, I simply add any remaining elements in both arrays. Each time one of the two while loops is going to be redundant because you'll never have leftovers in both sublists at the same time. — tom, Mar 19 '12 at 09:33
@KodeSeeker Regarding the incorrect output: I suspect the input file has duplicates. The current implementation treats equal items as inverted. If you want equal items to be considered sorted, change the line `if(left[a] < right[b]) {` to `if(left[a] <= right[b]) {`. — tom, Mar 19 '12 at 09:34
either ways doesnt the brute force approach give all possible inversions since it is exhaustive ? For instance in this case , while applying brute force I get 1887062008 inversions , whereas while applying the merge and sort approach I get 1898139648 inversions , and no I dont think there are any duplicate questions since , the o/p remained same while using both the < and <= conditions. — seeker, Mar 19 '12 at 10:15
I have tested the code using randomized input and my own bruteforce. So far all the outputs have been the same. Could you please post the case which gives you different results? (maybe use a [pastebin](http://pastebin.com/)) — tom, Mar 19 '12 at 10:27
Here's the code for the brute-force approach :http://pastebin.com/ihKDj8Ti and this one is for the mergesort appraoch :http://pastebin.com/VmQau8xv — seeker, Mar 19 '12 at 12:40
Your brute force approach gives the correct solution just change the count and counter to long. — nikhil, Mar 19 '12 at 15:02
@KodeSeeker You copy-pasted incorrectly. The two tiny while loops at the end of mergeAndCount() need to be separate, not one inside the other. — tom, Mar 19 '12 at 19:33
@tom: Indeed, thanks a lot ! My bad. Quite embarrassing actually. — seeker, Mar 20 '12 at 04:48
@tom : The implementation works well on small implementations, but Im facing another weird(atleast for me) issue here . Ive posted it here http://stackoverflow.com/questions/9781804/mergesort-implementation-to-find-number-of-inversions-not-working-when-trying-to — seeker, Mar 20 '12 at 05:36
in the count inversion method there is a for loop at the end of the method which 'assigns it back to the original array'. i tried this implemenation without that and it was giving wrong answer for some of the inputs but when i had that for loop the output is correct. I wonder why that for loop is necessary as it just populates the array and in no way should effect the result..Any ideas. ?? — mu_sa, Jun 23 '12 at 11:09
@LivingThing: In simple mergesort the array is split into two halves, each half is sorted recursively, and then the two sorted halves are merged. After calling mergesort on an array the array must become sorted, otherwise the merging can't work. This algorithm is based on the same principles as mergesort, and relies on the side effect that after calling `countInversions()` on an array the array becomes sorted. — tom, Jul 10 '12 at 02:37
The `result` array in `countInversions()` is slightly redundant. The eight lines from `int[] result=new int[num.length];` to the end of the for-loop can be replaced by the single line `countMerge=mergeAndCount(left,right,num);` which will put the sorted items straight back into the array `num`. When the recursive calls are made (`countLeft=countInversions(left)` and `countRight=countInversions(right);`) it is crucial that `left` and `right` become sorted, otherwise `mergeAndCount()` won't work. — tom, Jul 10 '12 at 02:57

score 1 · Answer 2 · answered Oct 18 '13 at 14:10

The way I see it, counting the number of inversions in an array is finding a way to sort the array in an ascending order. Following that thought, here is my solution:

int countInversionArray(int[] A) {
    if(A.length<=1) return 0;
    int solution = 0;

    for(int i=1;i<A.length;i++){
        int j = i;
        while(j+2<A.length && A[j] > A[j+1]){
            invert2(j,j+1,A);
            solution++;
            j++;
        }
        j=i;
        while(j>0 && A[j] < A[j-1]){
            invert2(j,j-1,A);
            solution++;
            j--;
        }
    }

    return solution;
}

private void invert2(int index1, int index2, int[] A){
    int temp = A[index1];
    A[index1] = A[index2];
    A[index2] = temp;
}

score 1 · Answer 3 · answered May 12 '14 at 07:06

1

I found a rigth solution in Robert Sedgewick book "Algorithms on java language"

Read here about merge
See java code for counting of inversion

answered May 12 '14 at 07:06

isxaker

8,446
12
60
87

score 0 · Answer 4 · answered Oct 04 '13 at 15:59

You can try this In-Place Mergesort implemention on java. But minimum 1 temporary data container is needed (ArrayList in this case). Also counts inversions.

///

Sorter.java

public interface Sorter {

    public void sort(Object[] data);

    public void sort(Object[] data, int startIndex, int len);

}

MergeSorter implementation class (others like QuickSorter, BubbleSorter or InsertionSorter may be implemented on Sorter interface)

MergeSorter.java

import java.util.List;
import java.util.ArrayList;

public class MergeSorter implements Sorter {

    private List<Comparable> dataList;
    int num_inversion;

    public MergeSorter() {
        dataList = new ArrayList<Comparable> (500);
        num_inversion = 0;
    }

    public void sort(Object[] data) {
        sort(data, 0, data.length);
    }

    public int counting() {
        return num_inversion;
    }

    public void sort(Object[] data, int start, int len) {
        if (len <= 1) return;
        else {
            int midlen = len / 2;

            sort(data, start, midlen);
            sort(data, midlen + start, len - midlen);
            merge(data, start, midlen, midlen + start, len - midlen);
        }
    }

    private void merge(Object[] data, int start1, int len1, int start2, int len2) {
        dataList.clear();

        int len = len1 + len2;

        // X is left array pointer
        // Y is right array pointer

        int x = start1, y = start2;
        int end1 = len1 + start1 - 1;
        int end2 = len2 + start2 - 1;

        while (x <= end1 && y <= end2) {

            Comparable obj1 = (Comparable) data[x];
            Comparable obj2 = (Comparable) data[y];

            Comparable<?> smallobject = null;
            if (obj1.compareTo(obj2) < 0) {
                smallobject = obj1;
                x++;
            }
            else {
                smallobject = obj2;
                y++;
                num_inversion += (end1 - x + 1);
            }

            dataList.add(smallobject);
        }

        while (x <= end1) {
            dataList.add((Comparable)data[x++]);
        }
        while (y <= end2) {
            dataList.add((Comparable)data[y++]);
        }

        for (int n = start1, i = 0; n <= end2; n++, i++) {
            data[n] = dataList.get(i);
        }

    }
}

For testing, create a driver class and type the main method

public static void main(String[] args) {

    Object[] data = ...............
    Sorter sorter = new MergeSorter();
    sorter.sort(data)

    for (Object x : data) {
        System.out.println(x);
    }
    System.out.println("Counting invertion: " + ((MergeSorter)sorter).counting());
}

Mergesort Implementation.. Counting number of inversions in an array

4 Answers4