divide_and_conquer.inversions

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

_count_cross_inversions(p, q)	Counts the inversions across two sorted arrays.
count_inversions_bf(arr)	Counts the number of inversions using a naive brute-force algorithm
count_inversions_recursive(arr)	Counts the number of inversions using a divide-and-conquer algorithm
main()

Module Contents

divide_and_conquer.inversions._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)

divide_and_conquer.inversions.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

divide_and_conquer.inversions.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)

divide_and_conquer.inversions.main()