CODEWITHSUNDEEP
java
nnanna
nnanna

Reputation: 287

having problems with inversion-counting Algorithm

I wrote an implementation of inversion-counting. This is an assignment being carried out in an online course. But the input i get isn't correct and according to what I have the program has a correct syntax. I dont just know were I went wrong The program below is my implementation

import java.io.*;

class CountInversions {
    //Create an array of length 1 and keep expanding as data comes in

    private int elements[];
    private int checker = 0;

    public CountInversions() {
        elements = new int[1];
        checker = 0;
    }

    private boolean isFull() {
        return checker == elements.length;
    }

    public int[] getElements() {
        return elements;
    }

    public void push(int value) {
        if (isFull()) {
            int newElements[] = new int[elements.length * 2];
            System.arraycopy(elements, 0, newElements, 0, elements.length);
            elements = newElements;
        }
        elements[checker++] = value;
    }

    public void readInputElements() throws IOException {
        //Read input from file and until the very last input
        try {
            File f = new File("IntegerArray.txt");
            FileReader fReader = new FileReader(f);
            BufferedReader br = new BufferedReader(fReader);
            String stringln;
            while ((stringln = br.readLine()) != null) {
                push(Integer.parseInt(stringln));
            }
            System.out.println(elements.length);
            fReader.close();
        } catch (Exception e) {//Catch exception if any
            System.err.println("Error: " + e.getMessage());
        } finally {
//            in.close
        }
    }  
        //Perform the count inversion algorithm
    public int countInversion(int array[],int length){
        int x,y,z;
        int mid = array.length/2 ;
        int k;
        if (length == 1){
            return 0;
        }else{
            //count Leftinversion and count Rightinversion respectively
            int left[] = new int[mid];
            int right[] = new int[array.length - mid];

            for(k = 0; k < left.length;k++){
                left[k] = array[k];
            }

            for(k = 0 ;k < right.length;k++){
                right[k] = array[mid + k];
            }
            x = countInversion(left, left.length);
            y = countInversion(right, right.length);
            int result[] = new int[array.length];
            z = mergeAndCount(left,right,result);

            //count splitInversion
            return x + y + z;
        }   
    }

    private int mergeAndCount(int[] left, int[] right, int[] result) {
        int count = 0;
        int i = 0, j = 0, k = 0;
        int m = left.length, n = right.length;
        while(i < m && j < n){
            if(left[i] < right[j]){
                result[k++] = left[i++];
            }else{
                result[k++] = right[j++];
                count += left.length - i;
            }
        }
        if(i < m){
            for (int p = i ;p < m ;p++){
                result[k++] = left[p];
            }
        }
        if(j < n){
            for (int p = j ;p < n ;p++){
                result[k++] = right[p];
            }
        }
        return count;
    }
}
class MainApp{
    public static void main(String args[]){
        int count = 0;
        CountInversions cIn = new CountInversions();
        try {
            cIn.readInputElements();
            count = cIn.countInversion(cIn.getElements(),cIn.getElements().length);
            System.out.println("Number of Inversios: " + count);

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

    }
}

Upvotes: 0

Views: 416

Answers (2)

Daniel Fischer
Daniel Fischer

Reputation: 183968

Your code works if the array length is a power of 2 (actually, I'm not sure whether if does, see second point below).

When reading the input, you double the array size when it's full, but you never resize it to the number of actually read items, which is stored in checker. So your array length is a power of 2, and if the number of ints read from the file is not a power of 2, you have a too long array with some trailing 0 elements corresponding to the places allocated but not filled from the file. Since you call countInversions with the length of the array and not with the number of read items, these 0s are sorted too, yielding some spurious inversions.

After reading the input, allocate a new array

int[] copy = new int[checker];
for(int i = 0; i < checker; ++i) {
    copy[i] = elements[i];
}
elements = copy;

copy the elements, and discard the old array with the wrong capacity.

Another problem in your algorithm is that you never change the original array because you allocate a new array for the merge result,

int result[] = new int[array.length];
z = mergeAndCount(left,right,result);

so you are merging unsorted arrays, which may also skew the inversion count. Since you copied the halves of the input array to new arrays for the recursive calls, you can without problem put the merge result in the passed-in array, so replace the above two lines with

z = mergeAndCount(left,right,array);

to get a method that actually sorts the array and counts the inversions.

Upvotes: 2

aretai
aretai

Reputation: 1641

This post is tackling the problem of count inversion with Java (except for file reading, which you have done OK) - Counting inversions in an array

Upvotes: 1

Related Questions