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
(p, q)
| 75 | |
| 76 | |
| 77 | def _count_cross_inversions(p, q): |
| 78 | """ |
| 79 | Counts the inversions across two sorted arrays. |
| 80 | And combine the two arrays into one sorted array |
| 81 | For all 1<= i<=len(P) and for all 1 <= j <= len(Q), |
| 82 | if P[i] > Q[j], then (i, j) is a cross inversion |
| 83 | Parameters |
| 84 | ---------- |
| 85 | P: array-like, sorted in non-decreasing order |
| 86 | Q: array-like, sorted in non-decreasing order |
| 87 | Returns |
| 88 | ------ |
| 89 | R: array-like, a sorted array of the elements of `P` and `Q` |
| 90 | num_inversion: int, the number of inversions across `P` and `Q` |
| 91 | Examples |
| 92 | -------- |
| 93 | >>> _count_cross_inversions([1, 2, 3], [0, 2, 5]) |
| 94 | ([0, 1, 2, 2, 3, 5], 4) |
| 95 | >>> _count_cross_inversions([1, 2, 3], [3, 4, 5]) |
| 96 | ([1, 2, 3, 3, 4, 5], 0) |
| 97 | """ |
| 98 | |
| 99 | r = [] |
| 100 | i = j = num_inversion = 0 |
| 101 | while i < len(p) and j < len(q): |
| 102 | if p[i] > q[j]: |
| 103 | # if P[1] > Q[j], then P[k] > Q[k] for all i < k <= len(P) |
| 104 | # These are all inversions. The claim emerges from the |
| 105 | # property that P is sorted. |
| 106 | num_inversion += len(p) - i |
| 107 | r.append(q[j]) |
| 108 | j += 1 |
| 109 | else: |
| 110 | r.append(p[i]) |
| 111 | i += 1 |
| 112 | |
| 113 | if i < len(p): |
| 114 | r.extend(p[i:]) |
| 115 | else: |
| 116 | r.extend(q[j:]) |
| 117 | |
| 118 | return r, num_inversion |
| 119 | |
| 120 | |
| 121 | def main(): |
no test coverage detected