Function count_inversions_bf

divide_and_conquer/inversions.py:12–40

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

(arr)

def 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
    """

    num_inversions = 0
    n = len(arr)

    for i in range(n - 1):
        for j in range(i + 1, n):
            if arr[i] > arr[j]:
                num_inversions += 1

    return num_inversions


def count_inversions_recursive(arr):