divide_and_conquer.inversions
=============================

.. py:module:: divide_and_conquer.inversions

.. autoapi-nested-parse::

   Given an array-like data structure A[1..n], how many pairs
   (i, j) for all 1 <= i < j <= n such that A[i] > A[j]? These pairs are
   called inversions. Counting the number of such inversions in an array-like
   object is the important. Among other things, counting inversions can help
   us determine how close a given array is to being sorted.
   In this implementation, I provide two algorithms, a divide-and-conquer
   algorithm which runs in nlogn and the brute-force n^2 algorithm.



Functions
---------

.. autoapisummary::

   divide_and_conquer.inversions._count_cross_inversions
   divide_and_conquer.inversions.count_inversions_bf
   divide_and_conquer.inversions.count_inversions_recursive
   divide_and_conquer.inversions.main


Module Contents
---------------

.. py:function:: _count_cross_inversions(p, q)

   Counts the inversions across two sorted arrays.
   And combine the two arrays into one sorted array
   For all 1<= i<=len(P) and for all 1 <= j <= len(Q),
   if P[i] > Q[j], then (i, j) is a cross inversion
   Parameters
   ----------
   P: array-like, sorted in non-decreasing order
   Q: array-like, sorted in non-decreasing order
   Returns
   ------
   R: array-like, a sorted array of the elements of `P` and `Q`
   num_inversion: int, the number of inversions across `P` and `Q`
   Examples
   --------
   >>> _count_cross_inversions([1, 2, 3], [0, 2, 5])
   ([0, 1, 2, 2, 3, 5], 4)
   >>> _count_cross_inversions([1, 2, 3], [3, 4, 5])
   ([1, 2, 3, 3, 4, 5], 0)


.. py:function:: count_inversions_bf(arr)

   Counts the number of inversions using a naive brute-force algorithm
   Parameters
   ----------
   arr: arr: array-like, the list containing the items for which the number
   of inversions is desired. The elements of `arr` must be comparable.
   Returns
   -------
   num_inversions: The total number of inversions in `arr`
   Examples
   ---------
    >>> count_inversions_bf([1, 4, 2, 4, 1])
    4
    >>> count_inversions_bf([1, 1, 2, 4, 4])
    0
    >>> count_inversions_bf([])
    0


.. py:function:: count_inversions_recursive(arr)

   Counts the number of inversions using a divide-and-conquer algorithm
   Parameters
   -----------
   arr: array-like, the list containing the items for which the number
   of inversions is desired. The elements of `arr` must be comparable.
   Returns
   -------
   C: a sorted copy of `arr`.
   num_inversions: int, the total number of inversions in 'arr'
   Examples
   --------
   >>> count_inversions_recursive([1, 4, 2, 4, 1])
   ([1, 1, 2, 4, 4], 4)
   >>> count_inversions_recursive([1, 1, 2, 4, 4])
   ([1, 1, 2, 4, 4], 0)
   >>> count_inversions_recursive([])
   ([], 0)


.. py:function:: main()