diff options
Diffstat (limited to 'AlgoDesignAndTechniqueEdxPython/sources/inversion_count.py')
-rw-r--r-- | AlgoDesignAndTechniqueEdxPython/sources/inversion_count.py | 38 |
1 files changed, 38 insertions, 0 deletions
diff --git a/AlgoDesignAndTechniqueEdxPython/sources/inversion_count.py b/AlgoDesignAndTechniqueEdxPython/sources/inversion_count.py new file mode 100644 index 0000000..cea3869 --- /dev/null +++ b/AlgoDesignAndTechniqueEdxPython/sources/inversion_count.py @@ -0,0 +1,38 @@ +# Uses python3 +import sys + +def mergeInversionCount(B, C, D): + count = 0 + while len(B) != 0 and len(C) != 0: + b = B[0] + c = C[0] + if b <= c: + D.append(b) + del B[0] + else: + count = count + len(B) + D.append(c) + del C[0] + D.extend(B) + D.extend(C) + return count + + +def getInversionCount(A, D): + numOfInversions = 0 + if len(A) == 1: + D.append(A[0]) + return 0 + m = int(len(A) / 2) + D1 = [] + numOfInversions = numOfInversions + getInversionCount(A[0:m], D1) + D2 = [] + numOfInversions = numOfInversions + getInversionCount(A[m:len(A)], D2) + mergeCount = mergeInversionCount(D1, D2, D) + return numOfInversions + mergeCount + +if __name__ == '__main__': + input = sys.stdin.read() + n, *a = list(map(int, input.split())) + b = n * [0] + print(getInversionCount(a, b))
\ No newline at end of file |