From 5d2513aabacbe939786e00979cdbd9960be65113 Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Fri, 23 Nov 2018 20:13:00 -0600
Subject: Improved QuickSort done!

Easy after the Java version is finished.---
 AlgoDesignAndTechniqueEdxPython/sources/sorting.py | 60 ++++++++++++++++++++++
 1 file changed, 60 insertions(+)
 create mode 100644 AlgoDesignAndTechniqueEdxPython/sources/sorting.py

(limited to 'AlgoDesignAndTechniqueEdxPython/sources')

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=' ')
+
-- 
cgit v1.2.3