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;
}
}
/**
* @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