/****************************************************************************** * Compilation: javac Inversions.java * Execution: java Inversions < input.txt * Dependencies: StdIn.java StdOut.java * * Read array of n integers and count number of inversions in n log n time. * ******************************************************************************/ /** * The {@code Inversions} class provides static methods to count the * number of inversions in either an array of integers or comparables. * An inversion in an array {@code a[]} is a pair of indicies {@code i} and * {@code j} such that {@code i < j} and {@code a[i] > a[j]}. *
* This implementation uses a generalization of mergesort. The count * operation takes Θ(n log n) time to count the * number of inversions in any array of length n (assuming * comparisons take constant time). *
* For additional documentation, see
* Section 2.2
* of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
*
* @author Robert Sedgewick
* @author Kevin Wayne
*/
public class Inversions {
// do not instantiate
private Inversions() { }
// merge and count
private static long merge(int[] a, int[] aux, int lo, int mid, int hi) {
long inversions = 0;
// copy to aux[]
for (int k = lo; k <= hi; k++) {
aux[k] = a[k];
}
// merge back to a[]
int i = lo, j = mid+1;
for (int k = lo; k <= hi; k++) {
if (i > mid) a[k] = aux[j++];
else if (j > hi) a[k] = aux[i++];
else if (aux[j] < aux[i]) { a[k] = aux[j++]; inversions += (mid - i + 1); }
else a[k] = aux[i++];
}
return inversions;
}
// return the number of inversions in the subarray b[lo..hi]
// side effect b[lo..hi] is rearranged in ascending order
private static long count(int[] a, int[] b, int[] aux, int lo, int hi) {
long inversions = 0;
if (hi <= lo) return 0;
int mid = lo + (hi - lo) / 2;
inversions += count(a, b, aux, lo, mid);
inversions += count(a, b, aux, mid+1, hi);
inversions += merge(b, aux, lo, mid, hi);
assert inversions == brute(a, lo, hi);
return inversions;
}
/**
* Returns the number of inversions in the integer array.
* The argument array is not modified.
* @param a the array
* @return the number of inversions in the array. An inversion is a pair of
* indicies {@code i} and {@code j} such that {@code i < j}
* and {@code a[i] > a[j]}.
*/
public static long count(int[] a) {
int[] b = new int[a.length];
int[] aux = new int[a.length];
for (int i = 0; i < a.length; i++)
b[i] = a[i];
long inversions = count(a, b, aux, 0, a.length - 1);
return inversions;
}
// merge and count (Comparable version)
private static