summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorHaidong Ji2018-11-28 20:08:23 -0600
committerHaidong Ji2018-11-28 20:08:23 -0600
commit886e0deedbaf1a53bbd6c37fac4337b80d30cae8 (patch)
treef384c169db73976d986e97527451383a9ea359ad
parent5d2513aabacbe939786e00979cdbd9960be65113 (diff)
Inversion count done!
It was easy, since I did the hard work of working it out in Java first.
-rw-r--r--AlgoDesignAndTechniqueEdxPython/sources/inversion_count.py38
-rw-r--r--AlgoDesignAndTechniqueEdxPython/tests/inversion_countTest.py31
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