Inversion count done!

It was easy, since I did the hard work of working it out in Java first.

2 files changed, 69 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
diff --git a/AlgoDesignAndTechniqueEdxPython/tests/inversion_countTest.py b/AlgoDesignAndTechniqueEdxPython/tests/inversion_countTest.py
new file mode 100644
index 0000000..b601952
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxPython/tests/inversion_countTest.py
@@ -0,0 +1,31 @@
+'''
+Created on Nov 28, 2018
+
+@author: haidong
+'''
+import unittest
+
+from sources.inversion_count import getInversionCount
+
+class Test(unittest.TestCase):
+
+
+    def testName(self):
+        a = [2, 3, 9, 2, 9]
+        D = []
+        self.assertEqual(2, getInversionCount(a, D))
+
+    def testName1(self):
+        a = [1, 1, 1, 1, 1]
+        D = []
+        self.assertEqual(0, getInversionCount(a, D))
+
+    def testName2(self):
+        a = [6, 5, 4, 3, 2, 1]
+        D = []
+        self.assertEqual(15, getInversionCount(a, D))
+
+
+if __name__ == "__main__":
+    #import sys;sys.argv = ['', 'Test.testName']
+    unittest.main()
\ No newline at end of file