Package edu.princeton.cs.algs4
Class Inversions
 Object

 edu.princeton.cs.algs4.Inversions

public class Inversions extends Object
TheInversions
class provides static methods to count the number of inversions in either an array of integers or comparables. An inversion in an arraya[]
is a pair of indiciesi
andj
such thati < j
anda[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, Kevin Wayne


Method Summary
All Methods Static Methods Concrete Methods Modifier and Type Method Description static long
count(int[] a)
Returns the number of inversions in the integer array.static <Key extends Comparable<Key>>
longcount(Key[] a)
Returns the number of inversions in the comparable array.static void
main(String[] args)
Reads a sequence of integers from standard input and prints the number of inversions to standard output.



Method Detail

count
public static long count(int[] a)
Returns the number of inversions in the integer array. The argument array is not modified. Parameters:
a
 the array Returns:
 the number of inversions in the array. An inversion is a pair of
indicies
i
andj
such thati < j
anda[i] > a[j]
.

count
public static <Key extends Comparable<Key>> long count(Key[] a)
Returns the number of inversions in the comparable array. The argument array is not modified. Type Parameters:
Key
 the inferred type of the elements in the array Parameters:
a
 the array Returns:
 the number of inversions in the array. An inversion is a pair of
indicies
i
andj
such thati < j
anda[i].compareTo(a[j]) > 0
.

main
public static void main(String[] args)
Reads a sequence of integers from standard input and prints the number of inversions to standard output. Parameters:
args
 the commandline arguments

