CODEWITHSUNDEEP
javaalgorithm
Sumeet
Sumeet

Reputation: 8292

Inversion Count using Divide And Conquer

I am trying to implement a program that counts number of inversions, But it is not working for big input size(100,000).

The unsorted numbers are picked from a txt file. The program works for small input size like 10 or 15 or even 20.

But When I copy the input from this link:http://spark-public.s3.amazonaws.com/algo1/programming_prob/IntegerArray.txt the program just keeps running for several seconds without producing any output.

I have used the divide and conquer algorithm based on merge sort and Implemented in BlueJ.

Here is the code.

import java.util.*;
import java.io.*;
class INVERSION
{
 private static LinkedList<Integer>arr;
 private static Scanner s;
 private static long count=0;
 public static void count_inv(int low,int high)
 {
     if(high<=low)
      return ;
     else
     {
         int mid= low + (high-low)/2;
         count_inv(low,mid);
         count_inv(mid+1,high);
         split_inv(low,high);

     }
 }
 public static void split_inv(int low,int high)
 {
     int mid=low+ (high-low)/2;
     int i=low,j=mid+1;
     int k=0;
     int []aa=new int[high-low+1];
     while(i<=mid&&j<=high)
     {
         if(arr.get(i)<=arr.get(j))
          aa[k++]=arr.get(i++);
         else {count+=mid-i+1; aa[k++]=arr.get(j++);}
     }
     while(i<=mid)
      aa[k++]=arr.get(i++);
     while(j<=high)
      aa[k++]=arr.get(j++);
     for(int e:aa)
      arr.set(low++,e);

 }
 public static void main(String []args)throws IOException
 {
  BufferedReader br=new BufferedReader(new FileReader("JJ.txt"));
  arr=new LinkedList<Integer>();
  String s="";
  while((s=br.readLine())!=null)
   arr.add(Integer.parseInt(s));                
  count_inv(0,arr.size()-1);
  System.out.println("the number of inversions is "+count);   
 }
}

Upvotes: 1

Views: 851

Answers (1)

Peter de Rivaz
Peter de Rivaz

Reputation: 33509

I think the problem might be that you are using a LinkedList.

This will have O(n) access time for random access.

You do O(nlogn) accesses, so overall your time will be O(n^2logn).

Try using just a normal array, or some other data structure with O(1) access time such as ArrayList.

Upvotes: 1

Related Questions