Tuesday, 3 April 2012

Inversion using mergesort

public class ListInversionFinder {

    /**
     * @param args
     */
    public static void main(String[] args) throws Exception{
        List<Long> input = TextFileReader.read();
        System.out.println(" INPUT ");
        for(long l : input){
            System.out.print(l + ", ");
        }
        System.out.println();
        long count = splitMerge(input, 0, input.size());
        System.out.println(" OUTPUT ");
        for(long l : input){
            System.out.print(l + ", ");
        }
        System.out.println();
        System.out.println("Inversion Count :: " + count);
    }

    public static long splitMerge(List data, int start, int length){
        long inversionCount = 0;
        if(length > 1) {
            int l = length/2;
            int l1 = length - l;
            long c = splitMerge(data, start, l);
            long c1 = splitMerge(data, start + l, l1);
            long count = merge(data, start, l, l1);
            inversionCount =  c + c1 + count;
        }
        return inversionCount;
    }

    private static long merge(List<Long> data, int start, int l, int l1){
        List<Long> temp = new ArrayList(l+l1);
        int i = 0;
        int j = 0 ;
        int k = 0;
        long inversionCount = 0;
        while(i < l && j < l1){
            if(data.get(start + i) <= data.get(start + l + j)){
                temp.add(k, data.get(start + i));
                i++;
            }
            else if(data.get(start + l + j) < data.get(start + i)){
                temp.add(k, data.get(start + l + j));
                j++;
                inversionCount = inversionCount + 1 + (l-(i+1));
            }
            k++;
        }
        while(j < l1){
            temp.add(k, data.get(start + l + j));
            j++;
            k++;
        }
        while(i < l){
            temp.add(k, data.get(start + i));
            i++;
            k++;
        }
        for(int m=0;m < temp.size();m++){
            int pos = start + m;
            data.set(pos, temp.get(m));
        }
        return inversionCount;
    }

}

No comments:

Post a Comment