edu.princeton.cs.algs4

Class Inversions

java.lang.Object

edu.princeton.cs.algs4.Inversions

public class Inversions
extends java.lang.Object

The Inversions class provides static methods to count the number of inversions in either an array of integers or comparables. An inversion in an array a[] is a pair of indicies i and j such that i < j and a[i] > a[j].

This implementation uses a generalization of mergesort. The count operation takes time proportional to n log n, where n is the number of keys in the array.

For additional documentation, see Section 2.2 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

Method Summary

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

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

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 and j such that i < j and a[i] > a[j].

count

public static <Key extends java.lang.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 and j such that i < j and a[i].compareTo(a[j]) > 0.

main

public static void main(java.lang.String[] args)

Reads a sequence of integers from standard input and prints the number of inversions to standard output.

Parameters:

args - the command-line arguments