Counting Inversions in Java

Given array A[1… n], for every i < j, find all inversion pairs such that A[i] > A[j]
(i, j form an inversion if A[i] > A[j])

Example
2 4 1 3 5
The sequence 2, 4, 1, 3, 5 has three inversions (2,1), (4,1), (4,3).

Problem

Find the number of inversions in the file given (every row has a single integer between 1 and 100,000) . Assume your array is from 1 to 100,000 and ith row of the file gives you the ith entry of the array.

Code– O(n log n)

 

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

public class Inversions {
	public static void main(String args[]) throws IOException {

		BufferedReader bfr = new BufferedReader(new FileReader("input.txt"));
		int n = 100000;
		int[] A = new int[n];
		String str = bfr.readLine();
		int i = 0;
		while (str != null) {
			A[i] = Integer.parseInt(str);
			i++;
			str = bfr.readLine();
		}

		Pair a = sortAndCount(A);
		System.out.println(a.x);
	}

	private static Pair sortAndCount(int[] a) {
		if (a.length == 1) {
			return new Pair(a, 0);
		} else {
			int[] leftArray = new int[a.length / 2];
			System.arraycopy(a, 0, leftArray, 0, leftArray.length);
			int[] rightArray = new int[a.length - leftArray.length];
			System.arraycopy(a, leftArray.length, rightArray, 0,
					rightArray.length);
			Pair x = sortAndCount(leftArray);

			Pair y = sortAndCount(rightArray);
			Pair z = MergeAndCountSplitInv(x.Array, y.Array, a.length);

			return new Pair(z.Array, x.x + y.x + z.x);
		}

	}

	private static Pair MergeAndCountSplitInv(int[] B, int[] C, int n) {
		long total = 0;
		int[] D = new int[n];
		int i = 0;
		int j = 0;
		for (int k = 0; k < n; k++) {
			if (j == C.length || i != B.length && B[i] < C[j]) {
				D[k] = B[i];
				i++;
			} else if (i == B.length || j != C.length && C[j] < B[i]) {
				D[k] = C[j];
				j++;
				total += B.length - i;
			}
		}
		return new Pair(D, total);
	}
}

class Pair {
	Pair(int[] A, long l) {
		this.Array = A;
		this.x = l;
	}

	public int[] Array;
	public long x;
}


Download Input File
Output : 2407905288

One thought on “Counting Inversions in Java”

  1. I have a error: Main.java:5: error: class Inversions is public, should be declared in a file named Inversions.java
    public class Inversions {

Leave a Reply

Your email address will not be published. Required fields are marked *