Class Inversions


  • public class Inversions
    extends 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 Θ(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 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 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​(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