summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--AlgoDesignAndTechniqueEdxPython/sources/sorting.py60
-rw-r--r--AlgoDesignAndTechniqueEdxPython/tests/SortingTest.py23
2 files changed, 83 insertions, 0 deletions
diff --git a/AlgoDesignAndTechniqueEdxPython/sources/sorting.py b/AlgoDesignAndTechniqueEdxPython/sources/sorting.py
new file mode 100644
index 0000000..5608c03
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxPython/sources/sorting.py
@@ -0,0 +1,60 @@
+# Uses python3
+import sys
+import random
+
+
+def partition3(a, l, r):
+ x = a[l]
+ j = l
+ dupCount = 0
+ biggerNumCount = 0
+
+ for i in range(l + 1, r + 1):
+ if a[i] < x:
+ t = a[i]
+ a[j] = t
+ t = a[i - biggerNumCount]
+ a[i] = t
+ a[i - biggerNumCount] = x
+ j = j + 1
+ continue
+ if a[i] == x:
+ t = a[j + dupCount + 1]
+ a[i] = t
+ a[j + dupCount + 1] = x
+ dupCount = dupCount + 1
+ continue
+ biggerNumCount = biggerNumCount + 1
+ return (j, j + dupCount)
+
+
+def partition2(a, l, r):
+ x = a[l]
+ j = l;
+ for i in range(l + 1, r + 1):
+ if a[i] <= x:
+ j += 1
+ a[i], a[j] = a[j], a[i]
+ a[l], a[j] = a[j], a[l]
+ return j
+
+
+def randomized_quick_sort(a, l, r):
+ if l >= r:
+ return
+ k = random.randint(l, r)
+ a[l], a[k] = a[k], a[l]
+ # use partition3
+# m = partition2(a, l, r)
+ (m1, m2) = partition3(a, l, r)
+ randomized_quick_sort(a, l, m1 - 1);
+ randomized_quick_sort(a, m2 + 1, r);
+
+
+if __name__ == '__main__':
+ input = sys.stdin.read()
+ n, *a = list(map(int, input.split()))
+ randomized_quick_sort(a, 0, n - 1)
+ for x in a:
+ print(x, end=' ')
+
diff --git a/AlgoDesignAndTechniqueEdxPython/tests/SortingTest.py b/AlgoDesignAndTechniqueEdxPython/tests/SortingTest.py
new file mode 100644
index 0000000..548940c
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxPython/tests/SortingTest.py
@@ -0,0 +1,23 @@
+'''
+Created on Nov 23, 2018
+
+@author: haidong
+'''
+import unittest
+
+from sources.sorting import randomized_quick_sort
+
+class Test(unittest.TestCase):
+
+
+ def testName(self):
+ a = [2, 3, 9, 2, 2]
+ result = [2, 2, 2, 3, 9]
+ randomized_quick_sort(a, 0, len(a) - 1)
+ self.assertEqual(result, a)
+ pass
+
+
+if __name__ == "__main__":
+ #import sys;sys.argv = ['', 'Test.testName']
+ unittest.main() \ No newline at end of file