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 `ar
(arr)
| 41 | |
| 42 | |
| 43 | def count_inversions_recursive(arr): |
| 44 | """ |
| 45 | Counts the number of inversions using a divide-and-conquer algorithm |
| 46 | Parameters |
| 47 | ----------- |
| 48 | arr: array-like, the list containing the items for which the number |
| 49 | of inversions is desired. The elements of `arr` must be comparable. |
| 50 | Returns |
| 51 | ------- |
| 52 | C: a sorted copy of `arr`. |
| 53 | num_inversions: int, the total number of inversions in 'arr' |
| 54 | Examples |
| 55 | -------- |
| 56 | >>> count_inversions_recursive([1, 4, 2, 4, 1]) |
| 57 | ([1, 1, 2, 4, 4], 4) |
| 58 | >>> count_inversions_recursive([1, 1, 2, 4, 4]) |
| 59 | ([1, 1, 2, 4, 4], 0) |
| 60 | >>> count_inversions_recursive([]) |
| 61 | ([], 0) |
| 62 | """ |
| 63 | if len(arr) <= 1: |
| 64 | return arr, 0 |
| 65 | mid = len(arr) // 2 |
| 66 | p = arr[0:mid] |
| 67 | q = arr[mid:] |
| 68 | |
| 69 | a, inversion_p = count_inversions_recursive(p) |
| 70 | b, inversions_q = count_inversions_recursive(q) |
| 71 | c, cross_inversions = _count_cross_inversions(a, b) |
| 72 | |
| 73 | num_inversions = inversion_p + inversions_q + cross_inversions |
| 74 | return c, num_inversions |
| 75 | |
| 76 | |
| 77 | def _count_cross_inversions(p, q): |
no test coverage detected